1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
/* Minimum spanning tree algorithm: example of a greedy algorithm.
* Given a set of nodes N, and edges E with each edge defined as
* {cost,node1,node2} in the list of edges Edges, return a list of
* edges such that every node is in the network and the network has
* the lowest cost possible.
*
* It can be proven that a greedy algorithm works in this case: at each
* step take the cheapest edge that adds one node to the network.
*/
EdgeCompare(edge1,edge2):= (edge1[1] < edge2[1]);
MinimumSpanningTree(NrNodes_IsPositiveInteger,Edges_IsList) <--
[
Local(CurrentNetwork,Result,Failed);
Failed := False;
/* Sort the edges by cost (cheapest first) */
Edges := BubbleSort(Edges,"EdgeCompare"); /* TODO Use Sort if defined */
/* Consume the first edge, it adds two nodes to the network. */
CurrentNetwork := FlatCopy(Tail(Edges[1]));
Result := {Edges[1]};
Edges := Tail(Edges);
/* Loop, trying to add every node once to the network */
While((Length(CurrentNetwork) < NrNodes) And Failed = False)
[
Local(EdgeFound,NodeAdded,Traverser);
EdgeFound := 0;
Traverser:=1;
/* Loop over all edges, searching for the cheapest edge that adds a node to
the
* current network.
*/
While(EdgeFound = 0 And Traverser <= Length(Edges))
[
Local(CurrentEdge);
/* See if the current edge adds exactly one node to the currently
cheapest network */
CurrentEdge := Edges[Traverser];
/* If not both nodes are already in the network */
if (Not(Contains(CurrentNetwork,CurrentEdge[2]) And
Contains(CurrentNetwork,CurrentEdge[3])))
[
/* If the first node is already in the network, this edge adds the
second */
if (Contains(CurrentNetwork,CurrentEdge[2]))
[
EdgeFound := Traverser;
NodeAdded := CurrentEdge[3];
];
/* If the second node is already in the network, this edge adds the
first */
if (Contains(CurrentNetwork,CurrentEdge[3]))
[
EdgeFound := Traverser;
NodeAdded := CurrentEdge[2];
];
];
Traverser ++;
];
/* If no edge was found, there is no tree connecting all the nodes to the
network. */
if (EdgeFound = 0)
[
Failed := True;
Result := {};
]
else
[
/* Add the cheapest found edge */
DestructiveAppend(CurrentNetwork,NodeAdded);
DestructiveAppend(Result,Edges[EdgeFound]);
DestructiveDelete(Edges, EdgeFound);
];
];
/* Result contains the list of edges that are the minimum spanning tree of
this
* network plus edges
*/
Result;
];
TreeCost(Edges_IsList) <-- Sum(MapSingle("Head",Edges));
/* Check minimum spanning tree algorithm */
Verify(TreeCost(MinimumSpanningTree(5,
{
{10,"Ayal","Diogo"},
{5,"Diogo","Gus"},
{15,"Diogo","Neil"},
{7,"Ayal","Neil"},
{17,"Gus","Edwin"},
{15,"Diogo","Edwin"},
{25,"Neil","Edwin"},
{18,"Ayal","Diogo"}
}
)),37);
|
