3
4:- module(graph, [
5 generate_undirected_unweighted_graph/2,
6 generate_undirected_weighted_graph/2,
7 generate_unweighted_graph/2,
8 generate_weighted_graph/2,
9 find_path_unweighted/4,
10 find_path_weighted/5,
11 generate_kn/2,
12 generate_kn_weighted/4,
13 generate_kn_from_vertices/2,
14 cycle_unweighted/3,
15 cycle_weighted/4,
16 is_connected/1,
17 node_degree/3,
18 node_degree_list/2,
19 generate_empty_unweighted_graph/3,
20 generate_empty_weighted_graph/3,
21 is_graph_node/2,
22 is_isolated_node/2,
23 is_graph_edge/2,
24 get_adjacent_nodes/3,
25 graph_reverse_edges/2,
26 spanning_tree/2,
27 mst_prim/3,
28 merge_graphs/3
29]).
30
35generate_undirected_unweighted_graph(ListOfEdges,graph(VSorted,ListOfEdgesSorted)):-
36 findall(X,(member(edge(X,_),ListOfEdges)),VX),
37 findall(Y,(member(edge(_,Y),ListOfEdges)),VY),
38 append(VX,VY,V),
39 sort(V,VSorted),
40 sort(ListOfEdges,ListOfEdgesSorted).
41
46generate_undirected_weighted_graph(ListOfEdges,graph(VSorted,ListOfEdgesSorted)):-
47 findall(X,(member(edge(X,_,_),ListOfEdges)),VX),
48 findall(Y,(member(edge(_,Y,_),ListOfEdges)),VY),
49 append(VX,VY,V),
50 sort(V,VSorted),
51 sort(ListOfEdges,ListOfEdgesSorted).
52
56generate_unweighted_graph(ListOfEdges,graph(VSorted,ListOfEdges)):-
57 findall(X,(member(edge(X,_),ListOfEdges)),VX),
58 findall(Y,(member(edge(_,Y),ListOfEdges)),VY),
59 append(VX,VY,V),
60 sort(V,VSorted).
61
62
66generate_weighted_graph(ListOfEdges,graph(VSorted,ListOfEdges)):-
67 findall(X,(member(edge(X,_,_),ListOfEdges)),VX),
68 findall(Y,(member(edge(_,Y,_),ListOfEdges)),VY),
69 append(VX,VY,V),
70 sort(V,VSorted).
71
72
75find_path_unweighted(graph(Vertices,Edges),V1,V2,Path):-
76 member(V1,Vertices),
77 member(V2,Vertices),
78 find_path_unweighted_(V1,V2,Edges,[V1],Path).
79
80find_path_unweighted_(V,V,_,L,L).
81find_path_unweighted_(V1,V2,Edges,L,Path):-
82 83 member(edge(V1,V2),Edges),
84 append(L,[V2],Path).
85find_path_unweighted_(V1,V2,Edges,L,Path):-
86 87 member(edge(V1,VX),Edges),
88 VX \== V2,
89 \+member(VX,L),
90 append(L,[VX],L1),
91 find_path_unweighted_(VX,V2,Edges,L1,Path).
92
93connected(V1,V2,Edges):-
94 member(edge(V1,V2),Edges);
95 member(edge(V2,V1),Edges).
96
97connected_w(V1,V2,Edges,C):-
98 member(edge(V1,V2,C),Edges);
99 member(edge(V2,V1,C),Edges).
100
103find_path_weighted(graph(Vertices,Edges),V1,V2,Path,Cost):-
104 member(V1,Vertices),
105 member(V2,Vertices),
106 find_path_weighted_(V1,V2,Edges,[V1],Path,0,Cost).
107
108find_path_weighted_(V,V,_,L,L,C,C).
109find_path_weighted_(V1,V2,Edges,L,Path,CurrC,TotalC):-
110 111 member(edge(V1,V2,Cost),Edges),
112 append(L,[V2],Path),
113 TotalC is CurrC + Cost.
114find_path_weighted_(V1,V2,Edges,L,Path,CurrC,TotalC):-
115 116 member(edge(V1,VX,Cost),Edges),
117 VX \== V2,
118 \+member(VX,L),
119 append(L,[VX],L1),
120 Curr1 is CurrC + Cost,
121 find_path_weighted_(VX,V2,Edges,L1,Path,Curr1,TotalC).
122
123
127generate_kn(Size,graph(LV,Comb)):-
128 129 numlist(1,Size,LV),
130 find_all_combinations(LV,[],Comb).
131
132find_all_combinations([_],C,C):- !.
133find_all_combinations([H|T],CT,CO):-
134 find_combinations(H,T,C),
135 append(CT,C,C1),
136 find_all_combinations(T,C1,CO).
137
138find_combinations(_,[],[]):- !.
139find_combinations(E,[H|T],[edge(E,H)|TE]):-
140 find_combinations(E,T,TE).
141
142
146generate_kn_weighted(Size,MinValue,MaxValue,graph(LV,Comb)):-
147 numlist(1,Size,LV),
148 find_all_combinations_weighted(LV,MinValue,MaxValue,[],Comb).
149
150find_all_combinations_weighted([_],_,_,C,C):- !.
151find_all_combinations_weighted([H|T],Min,Max,CT,CO):-
152 find_combinations_weighted(H,T,Min,Max,C),
153 append(CT,C,C1),
154 find_all_combinations_weighted(T,Min,Max,C1,CO).
155
156find_combinations_weighted(_,[],_,_,[]):- !.
157find_combinations_weighted(E,[H|T],Min,Max,[edge(E,H,V)|TE]):-
158 random(Min,Max,V),
159 find_combinations_weighted(E,T,Min,Max,TE).
160
161
164generate_kn_from_vertices(LV,graph(LV,Comb)):-
165 find_all_combinations(LV,[],Comb).
166
167
170cycle_unweighted(Graph,V,C):-
171 find_path_unweighted(Graph,V,V,C),
172 length(C,N),
173 N > 3.
174
175
178cycle_weighted(Graph,V,Cycle,Cost):-
179 find_path_weighted(Graph,V,V,Cycle,Cost),
180 length(Cycle,N),
181 N > 3.
182
183
188is_connected(graph(LV,Edges)):-
189 (memberchk(edge(_,_),(Edges)) ->
190 exist_path(LV,Edges,0);
191 exist_path(LV,Edges,1)).
192
193exist_path([_],_,_):-!.
194exist_path([H|T],E,V):-
195 exist_path_(H,T,E,V),
196 exist_path(T,E,V).
197
198exist_path_(_,[],_,_):-!.
199exist_path_(H,[H1|T1],E,V):-
200 (V = 0 ->
201 connected(H,H1,E);
202 connected_w(H,H1,E,_)),!,
203 exist_path_(H,T1,E,V).
204
205
208node_degree(graph(LN,Edges),Node,Deg):-
209 member(Node,LN),
210 (memberchk(edge(_,_),Edges) ->
211 (findall(X,(member(edge(X,Node),Edges)),VX),
212 findall(Y,(member(edge(Node,Y),Edges)),VY))
213 ;
214 (findall(X,(member(edge(X,Node,_),Edges)),VX),
215 findall(Y,(member(edge(Node,Y,_),Edges)),VY))
216 ),
217 length(VX,NX),
218 length(VY,NY),
219 Deg is NX+NY.
220
221
224node_degree_list(graph(LV,Edges),L):-
225 node_degree_list_(LV,LV,Edges,[],L).
226
227node_degree_list_([],_,_,L,Sorted):-
228 sort(0,@>=,L,Sorted). 229node_degree_list_([H|T],LV,Edges,LT,L):-
230 node_degree(graph(LV,Edges),H,Deg),
231 A = [Deg,H],
232 append(LT,[A],LT1),
233 node_degree_list_(T,LV,Edges,LT1,L).
234
235
238generate_empty_unweighted_graph(NumNodes,NumEdges,graph(LN,Edges)):-
239 NumNodes > 0,
240 NumEdges < NumNodes*(NumNodes - 1),
241 length(LN,NumNodes),
242 length(Edges,NumEdges),
243 maplist(=(edge(_,_)),Edges).
244
247generate_empty_weighted_graph(NumNodes,NumEdges,graph(LN,Edges)):-
248 NumNodes > 0,
249 NumEdges < NumNodes*(NumNodes - 1),
250 length(LN,NumNodes),
251 length(Edges,NumEdges),
252 maplist(=(edge(_,_,_)),Edges).
253
257is_graph_node(graph(LN,_),N):-
258 member(N,LN).
259
260
264is_isolated_node(graph(LN,Edges),N):-
265 member(N,LN),
266 my_not_member(N,Edges).
267
269my_not_member(_,[]).
270my_not_member(A,[E|Edges]):-
271 (E = edge(NA,NB) ; E = edge(NA,NB,_)),
272 A \= NA,
273 A \= NB,
274 my_not_member(A,Edges).
275
279is_graph_edge(graph(_,Edges),E):-
280 member(E,Edges).
281
285get_adjacent_nodes(graph(LN,Edges),Node,List):-
286 member(Node,LN),
287 (memberchk(edge(_,_),Edges) ->
288 (findall(X,(member(edge(Node,X),Edges)),VX),
289 findall(Y,(member(edge(Y,Node),Edges)),VY))
290 ;
291 (findall(X,(member(edge(Node,X,_),Edges)),VX),
292 findall(Y,(member(edge(Y,Node,_),Edges)),VY))
293 ),
294 append(VX,VY,VT),
295 sort(VT,List).
296
297
300graph_reverse_edges(graph(LN,Edges),graph(LN,RevEdges)):-
301 reverse_edges_(Edges,RevEdges).
302reverse_edges_([],[]).
303reverse_edges_([edge(X,Y,V)|T],[edge(Y,X,V)|T1]):-!,
304 reverse_edges_(T,T1).
305reverse_edges_([edge(X,Y)|T],[edge(Y,X)|T1]):-
306 reverse_edges_(T,T1).
307
308
310spanning_tree(graph([N|T],Edges),graph([N|T],TreeEdges)) :-
311 generate_spanning_tree(T,Edges,TreeEdgesUnsorted),
312 sort(TreeEdgesUnsorted,TreeEdges).
313
314generate_spanning_tree([],_,[]).
315generate_spanning_tree(Curr,Edges,[Edge|T]) :-
316 select(Edge,Edges,Edges1), 317 get_vertices(Edge,X,Y), 318 is_connected_to_tree(X,Y,Curr), 319 delete(Curr,X,Curr1), 320 delete(Curr1,Y,Curr2),
321 generate_spanning_tree(Curr2,Edges1,T).
322
323get_vertices(edge(X,Y),X,Y).
324get_vertices(edge(X,Y,_),X,Y).
325
326is_connected_to_tree(X,Y,Ns):-
327 memberchk(X,Ns),
328 \+ memberchk(Y,Ns), !.
329is_connected_to_tree(X,Y,Ns):-
330 memberchk(Y,Ns),
331 \+ memberchk(X,Ns).
332
333
336mst_prim(graph([H|T],Edges),graph([H|T],TreeEdges),Cost):-
337 predsort(compare_edges_value,Edges,SortedEdges),
338 generate_spanning_tree(T,SortedEdges,TreeEdgesUnsorted),!, 339 sort(TreeEdgesUnsorted,TreeEdges),
340 sum_cost(TreeEdges,0,Cost).
341
342compare_edges_value(O,edge(X1,Y1,C1),edge(X2,Y2,C2)):-
343 compare(O,C1+X1+Y1,C2+X2+Y2).
344
345sum_cost([],C,C).
346sum_cost([edge(_,_,C)|T],CT,Tot):-
347 CT1 is CT+C,
348 sum_cost(T,CT1,Tot).
349
353merge_graphs(graph(L1,Edges1),graph(L2,Edges2),graph(L,Edges)):-
354 append(L1,L2,LT),
355 sort(LT,L),
356 append(Edges1,Edges2,EdgesT),
357 sort(EdgesT,Edges)