1 | % (c) 2009-2019 Lehrstuhl fuer Softwaretechnik und Programmiersprachen, | |
2 | % Heinrich Heine Universitaet Duesseldorf | |
3 | % This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html) | |
4 | ||
5 | ||
6 | :- module(state_space_dijkstra,[find_shortest_path_from_to/4, | |
7 | find_shortest_path_from_to_found_predicate/4, | |
8 | set_target_id/1, set_found_predicate/2]). | |
9 | ||
10 | :- use_module(tools). | |
11 | :- use_module(module_information). | |
12 | :- module_info(group,animator). | |
13 | :- module_info(description,'Tools for finding shortest paths between visited states.'). | |
14 | ||
15 | % can find the shortest path from a given node to | |
16 | % any node satisfying a genering "found_predicate" | |
17 | ||
18 | :- use_module(state_space). | |
19 | :- use_module(library(heaps)). | |
20 | :- use_module(library(lists)). | |
21 | ||
22 | ||
23 | :- dynamic found_predicate/1. % a predicate that should return true if we have found a target node | |
24 | :- dynamic mark_id/3. | |
25 | ||
26 | set_target_id(TargetID) :- | |
27 | retractall(found_predicate(_)), | |
28 | assert(found_predicate(TargetID)). | |
29 | ||
30 | set_found_predicate(ID,COND) :- | |
31 | retractall(found_predicate(_)), | |
32 | assert((found_predicate(ID) :- COND)). | |
33 | ||
34 | % find_shortest_path_from_to(FromStateID,ToStateID,-ResOpIDPath,-ResStateIDL) | |
35 | find_shortest_path_from_to(From,To,ResOpIDPath,ResIDL) :- | |
36 | set_target_id(To), | |
37 | find_shortest_path_from_to_found_predicate(From,ResOpIDPath,ResIDL,_). | |
38 | find_shortest_path_from_to_found_predicate(From,ResPath,ResIDL,TargetID) :- | |
39 | retractall(mark_id(_,_,_)), | |
40 | empty_heap(H), | |
41 | add_to_heap(H,0,node(From,null,null),NH), | |
42 | dijkstra(NH,RP,RI,TargetID,10), | |
43 | reverse(RP,ResPath), reverse(RI,ResIDL). | |
44 | ||
45 | :- use_module(debug). | |
46 | ||
47 | dijkstra(Heap,ResOpIDPath,ResIDList,TargetID,Cnt) :- | |
48 | (Cnt>0 -> C1 is Cnt-1 ; C1=1000, printsilent('.'),flush_output(user)), | |
49 | get_from_heap(Heap,Dist,node(ID,PrevID,TransID),NewHeap),!, | |
50 | (found_predicate(ID) -> TargetID=ID, %print(extracting_path(ID)),nl, | |
51 | assert(mark_id(ID,PrevID,TransID)), | |
52 | nls, | |
53 | extract_path(ID,ResIDList,ResOpIDPath) %,print(res(ResIDList)),nl | |
54 | ; treat_node(ID,PrevID,TransID,Dist,NewHeap,NewHeap1), | |
55 | dijkstra(NewHeap1,ResOpIDPath,ResIDList,TargetID,C1) | |
56 | ). | |
57 | dijkstra(_,_,_,_,_) :- | |
58 | print('NO PATH EXISTS TO A NODE WITH found_predicate TRUE ! '),nl, | |
59 | fail. | |
60 | ||
61 | extract_path(ID,StateIDL,Path) :- | |
62 | mark_id(ID,PrevID,TransID), | |
63 | (PrevID=null -> StateIDL=[], Path=[] | |
64 | ; % any_transition(PrevID,TransID,ID), % not necessary ? | |
65 | % here we could choose a transition with minimal changes from previous transition | |
66 | StateIDL=[ID|TI],Path=[TransID|TP], | |
67 | extract_path(PrevID,TI,TP)). | |
68 | ||
69 | treat_node(ID,_,_,_,H,RH) :- mark_id(ID,_,_),!,RH=H. % node already treated | |
70 | treat_node(ID,PrevID,TransID,Dist,H,RH) :- assert(mark_id(ID,PrevID,TransID)), | |
71 | findall(node(NewID,ID,NewTransID), | |
72 | any_transition(ID,NewTransID,NewID), Succs), | |
73 | D1 is Dist+1, | |
74 | add_nodes(Succs,D1,H,RH). | |
75 | ||
76 | add_nodes([],_,H,H). | |
77 | add_nodes([N|T],Prio,H,RH) :- add_to_heap(H,Prio,N,H1), | |
78 | add_nodes(T,Prio,H1,RH). | |
79 | ||
80 | % use_module(state_space_dijkstra), find_shortest_path_to(root,22,P,I) |