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