# Kruskal's algorithm for the MST.
# Written by Eli Olinick, Southern Methodist University, Texas. Modified John F. Raffensperger, 7 March 2006.
# This script does not call a solver, so it can solve for instances that use more variables than Student CPlex allows.

param N; # Number of nodes.
set Nodes := {1..N};
set Arcs := {i in Nodes, j in Nodes: i < j};
param Tourlength;

param x {i in Nodes, j in Nodes: i < j} default 0; # This is needed only to produce the SVG graph, with the makesvg.run script.
param xcoord {Nodes};
param ycoord {Nodes};

# No model file needed, but you do need the data.
data ..\data\20points.txt;
param length {(i,j) in Arcs} := sqrt((xcoord[i] - xcoord[j])^2 + (ycoord[i] - ycoord[j])^2);

set InTree within Arcs default {};	# The set of edges in the MST
set Unscanned within Arcs;		# The set of edges which have not been inspected.
set Best_Edges within Arcs;	# The set of minimum-cost edges in Unscanned

# Kruskals works by building short arcs into connected components, which eventually are connected to form the whole tree.
# If component[i]=t, then component t of InTree contains node i. If component[i] = 0, then the edges in InTree do not yet span i.
param component {Nodes} default 0;	

let Unscanned := Arcs;

repeat while card(InTree) < card(Nodes) - 1
{	let Best_Edges := {(i,j) in Unscanned: length[i,j] = min{(u,v) in Unscanned} length[u,v]};
	let Unscanned := Unscanned diff Best_Edges;
	
	for {(i,j) in Best_Edges}
	{	if component[i] = 0 then
		{	if component[j] = 0 then
			{	# Case 1: neither vertex is in the tree. Start a new component with (i,j).
				let component[i] := max{v in Nodes} component[v] + 1;
				let component[j] := component[i];
				let InTree := InTree union {(i,j)};
			}
			else
			{	# Case 2: j is in the tree, but i isn't. Add (i,j) to the component containing j.
				let component[i] := component[j];
				let InTree := InTree union  {(i,j)};
		}	}
		else
		{	if component[j] = 0 then
			{	# Case 3: i is in the tree, but j isn't. Add (i,j) to the component containing i.
				let component[j] := component[i];
				let InTree := InTree union  {(i,j)};
			}
			else
			{	if component[i] <> component[j] then
			 	{	# Case 4: i and j are in different connected components; merge the components into component[i].
					# Buggy: let {v in Nodes: component[v] = component[j]} component[v] := component[i];
					for {v in Nodes: component[v] = component[j]} let component[v] := component[i];
					let InTree := InTree union  {(i,j)};
				}
				# else (i,j) are in the same component, and this arc would make a subtour.
		}	}
		if card(InTree) = card(Nodes) - 1 then break;
}	}

for {(i,j) in InTree} let x[i,j] := 1; # This is needed only to produce the SVG graph, with the makesvg.run script.

let Tourlength := sum{(i,j) in InTree} length[i,j];
printf "The MST for this graph has cost %g.\n", sum{(i,j) in InTree} length[i,j];
display InTree;
commands ..\makesvg.run;