1 | % (c) 2009-2022 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 | :- module(avl_ugraphs,[avl_set_to_ugraph/2, | |
6 | ugraph_to_avl_set/2, | |
7 | avl_transitive_closure/2, | |
8 | avl_scc_sets/2]). | |
9 | ||
10 | % | |
11 | ||
12 | :- use_module(probsrc(module_information)). | |
13 | :- module_info(group,external_functions). | |
14 | :- module_info(description,'A module to interface ProB\'s avl_set relations with the SICStus ugraph library (unweighted graphs).'). | |
15 | ||
16 | ||
17 | :- use_module(library(avl)). | |
18 | :- use_module(library(lists)). | |
19 | :- use_module(library(ugraphs),[vertices_edges_to_ugraph/3, | |
20 | transitive_closure/2, edges/2, | |
21 | reduce/2, vertices/2]). | |
22 | ||
23 | pair_to_minus((A,B),A-B). | |
24 | %pair_to_minus((A,B),CA-CB) :- convert_val(A,CA), convert_val(B,CB). | |
25 | minus_to_pair(A-B,(A,B)-true). | |
26 | %minus_to_pair(A-B,(CA,CB)-true) :- reconvert_val(A,CA), reconvert_val(B,CB). | |
27 | ||
28 | %convert_val(int(X),R) :- !, R=X. | |
29 | %convert_val(R,R). | |
30 | %reconvert_val(X,R) :- number(X),!, R=int(X). | |
31 | %reconvert_val(R,R). | |
32 | ||
33 | % closure1(%x.(x:1..2000|x*x)) is much slower with this than with the version in custom-explicit sets (1 secs vs 10ms) | |
34 | % closure1(%x.(x:1..1000|x*x) \/ %x.(x:1..2000|x+x) \/ %x.(x:1..1000|x/2)): 9.3 seconds vs 2 seconds | |
35 | % others like closure1(nxt \/ nxt~) for TrackUp.mch are faster (110ms vs 380ms) | |
36 | ||
37 | avl_set_to_ugraph(A,UGraph) :- | |
38 | avl_domain(A,AList), | |
39 | maplist(pair_to_minus,AList,InEdges), | |
40 | vertices_edges_to_ugraph([],InEdges,UGraph). | |
41 | ||
42 | ugraph_to_avl_set(UGraph,Res) :- | |
43 | edges(UGraph,Edges), | |
44 | maplist(minus_to_pair,Edges,Res). | |
45 | ||
46 | ||
47 | avl_transitive_closure(A,Res) :- % print(start1),debug:nl_time, | |
48 | avl_set_to_ugraph(A,UGraph), | |
49 | transitive_closure(UGraph,TUG), %print(tc(TUG)),debug:nl_time, | |
50 | edges(TUG,Edges), %print(edg(Edges)),debug:nl_time, | |
51 | maplist(minus_to_pair,Edges,ListRes), | |
52 | sort(ListRes,SListRes), %print(sl(SListRes)),debug:nl_time, | |
53 | ord_list_to_avl(SListRes,Res). % could be empty | |
54 | %print(stop1),debug:nl_time,fail. | |
55 | ||
56 | %Note: result could be empty, use: construct_avl_set on Res | |
57 | ||
58 | :- use_module(probsrc(custom_explicit_sets),[convert_to_avl/2]). | |
59 | ||
60 | % compute strongly connected components, returning a set of sets of vertices | |
61 | avl_scc_sets(A,Res) :- %print(start_scc),debug:nl_time, | |
62 | avl_set_to_ugraph(A,UGraph), | |
63 | reduce(UGraph,SCCGraph), | |
64 | vertices(SCCGraph,VList), %print(vl(VList)),nl, | |
65 | %print(stop_scc),debug:nl_time, | |
66 | %maplist(convert_to_avl,V,SCCList), | |
67 | convert_to_avl(VList,avl_set(Res)). % could be empty | |
68 | ||
69 | /* TO DO: | |
70 | ||
71 | reduce(+Graph, -Reduced) | |
72 | is true if Reduced is the reduced graph for Graph. The vertices of the reduced | |
73 | graph are the strongly connected components of Graph. There is an edge in | |
74 | Reduced from u to v iff there is an edge in Graph from one of the vertices in u | |
75 | to one of the vertices in v. A strongly connected component is a maximal set | |
76 | of vertices where each vertex has a path to every other vertex. Algorithm from | |
77 | "Algorithms" by Sedgewick, page 482, Tarjan’s algorithm. | |
78 | ||
79 | | ?- vertices_edges_to_ugraph([a,b,c],[a-b,b-c,c-b,b-d],G), reduce(G,G2), edges(G2,Edges). | |
80 | G = [a-[b],b-[c,d],c-[b],d-[]], | |
81 | G2 = [[a]-[[b,c]],[b,c]-[[d]],[d]-[]], | |
82 | Edges = [[a]-[b,c],[b,c]-[d]] ? | |
83 | ||
84 | reachable(+Vertex, +Graph, -Reachable) | |
85 | is given a Graph and a Vertex of that Graph, and returns the set of vertices | |
86 | that are Reachable from that Vertex. Takes O(N^2) time. | |
87 | ||
88 | random_ugraph(+P, +N, -Graph) | |
89 | where P is a probability, unifies Graph with a random graph of N vertices where | |
90 | each possible edge is included with probability P. | |
91 | ||
92 | */ |