1% LOOP49
2:- module(yoyo2).
3
4getbug :-
5	writeln('\nCheck that you are in "module(yoyo2).", then'),
6	writeln('to start the program type "mcs([arc(1,2,0), arc(1,3,5), arc(2,3,0)], Tree)."\n').
7
8bug :-
9	nl,
10	explanation.
11
12explanation :-
13writeln(' \n\
14The problem is that subset/2 is used in a generating way \n\
15but this is not possible. \n\
16\n\
17GOAL:	 mcs([arc(1,2,0), arc(1,3,5), arc(2,3,0)], Tree). \n\
18CORRECT: Tree = [arc(1,2,0), arc(2,3,0)] \n\
19BUGGY:   endless loop (failure-driven endless recursion). \n').
20
21
22% ============================================================================
23/*
24 p. 230  ex. 9.15
25
26 Finding a minimum-cost spanning tree of a graph.
27
28 This program is only a variation of the program for finding
29 an arbitrary spanning tree in a graph, given on p. 231.
30 In addition I changed the representation of the graph.
31*/
32
33% mcs : minimum-cost spanning tree
34
35mcs(Graph,Tree) :-
36	spanning_tree(Graph,Tree),
37	not (spanning_tree(Graph,Othertree),
38	     cheaper(Othertree,Tree)).
39
40spanning_tree(Graph,Tree) :-
41	subset(Tree, Graph),
42	tree(Tree),
43	covers(Tree,Graph).
44
45tree(Graph) :-
46	connected(Graph),
47	not hasacycle(Graph).
48
49connected(Graph) :-
50	node_of(Graph, [], Nodes),
51	not (member(A, Nodes),
52	     member(B, Nodes),
53	     not path_in_graph(A,B,Graph,_)).
54
55node_of([], Set, Set).
56node_of([arc(X, Y, _)|G], Accu, Res) :-
57	add_to(X, Y, Accu, NewAccu),
58	node_of(G, NewAccu, Res).
59
60add_to(X, Y, L, L) :-
61	member(X, L),
62	member(Y, L),
63	!.
64add_to(X, Y, L, [X|L]) :-
65	member(Y, L),
66	!.
67add_to(X, Y, L, [Y|L]) :-
68	member(X, L),
69	!.
70add_to(X, Y, L, [X, Y|L]).
71
72hasacycle(Graph) :-
73	!,
74	fail.
75hasacycle(Graph) :-
76	node_of(Graph, [], Nodes),
77	member(A, Nodes),
78	member(B, Nodes),
79	adjacent(A,B,Graph),
80	(	adjacent(B,A,Graph)
81	;
82		path_in_graph(B,A,Graph,[X,Y,Z|Rest])
83	).
84
85covers(Graph1,Graph2) :-
86	not (node(A,Graph2),
87	     not node(A,Graph1)).
88
89cheaper(Graph1,Graph2) :-
90	sumcosts(Graph1,Sum1),
91	sumcosts(Graph2,Sum2),
92	Sum1 < Sum2.
93
94sumcosts([],0).
95sumcosts([X|Rest],Sum) :-
96	sumcosts(Rest,Sum1),
97	X = arc(P1,P2,Costs),
98	Sum is Sum1 + Costs.
99
100subset([], L).
101subset([X|Xs], L) :-
102	member(X, L),
103	subset(Xs, L).
104
105% Representation of the graph with costs attached to the arcs:
106% List of objects 'arc(Point1,Point2,Costs)'
107
108node(A,Graph) :-
109	member(X,Graph),
110	( X = arc(A,_,_)
111	;
112	X = arc(_,A,_)
113	).
114
115adjacent(A,B,Graph) :-
116	member(X,Graph),
117	X = arc(A,B,_),
118	!.
119
120path_in_graph(A,Z,Graph,Path) :-
121	path_in_graph1(A,[Z],Graph,Path).
122
123path_in_graph1(A,[A|Path1],_,[A|Path1]) :-
124	!.
125path_in_graph1(A,[Y|Path1],Graph,Path) :-
126	( adjacent(X,Y,Graph)
127	;
128	adjacent(Y,X,Graph)
129	),
130	not member(X,Path1),			% no cycle
131	path_in_graph1(A,[X,Y|Path1],Graph,Path).
132
133member(X,[X|Rest]).
134member(X,[Y|Rest]) :-
135	member(X,Rest).
136
137