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