Satsuma.Kruskal< TCost > Class Template Reference

Finds a minimum cost spanning forest in a graph using Kruskal's algorithm. More...

Public Member Functions
bool	AddArc (Arc arc)
	Tries to add the specified arc to the current forest. More...
	Kruskal (IGraph graph, Func< Arc, TCost > cost, Func< Node, int > maxDegree=null)
	Kruskal (IGraph graph, Dictionary< Arc, TCost > cost)
void	Run ()
	Runs the algorithm and completes the current forest to a spanning forest. More...
bool	Step ()
	Performs a step in Kruskal's algorithm. More...

Properties
Func< Arc, TCost >	Cost [get, set]
	An arbitrary function assigning costs to the arcs. More...
Dictionary< Node, int >	Degree [get, set]
	Contains the degree of a node in the found spanning forest. More...
HashSet< Arc >	Forest [get, set]
	Contains the arcs of the current forest. More...
Subgraph	ForestGraph [get, set]
	The current forest as a subgraph of the original graph. More...
IGraph	Graph [get, set]
	The input graph. More...
Func< Node, int >	MaxDegree [get, set]
	An optional per-node maximum degree constraint on the resulting spanning forest. More...

Detailed Description

Finds a minimum cost spanning forest in a graph using Kruskal's algorithm.

Most suitable for sparse (i.e. everyday) graphs. For dense graphs, use Prim<TCost>.

The algorithm starts with an empty forest, and gradually expands it with one arc at a time, taking the cheapest possible arc in each step. At the end of the algorithm, this yields a cheapest spanning forest.

Running time: O(m log n), memory usage: O(m); where n is the number of nodes and m is the number of arcs.

Note

This class also allows finding a cheapest forest containing some fixed arc set. Call AddArc several times at the beginning to set an initial forest which needs to be contained, then call Run to complete the forest. It can be proven that the found spanning forest is optimal among those which contain the given arc set.

A maximum degree constraint can also be imposed on the spanning forest, and arbitrary arcs can be added to the forest at any time using AddArc. However, if using these features, the resulting forest may not be optimal.

See Prim<TCost> for a usage example.

Template Parameters

TCost

The arc cost type.

Type Constraints

TCost

:

IComparable<TCost>

Definition at line 152 of file SpanningForest.cs.

Constructor & Destructor Documentation

Satsuma.Kruskal< TCost >.Kruskal	(	IGraph	graph,
		Func< Arc, TCost >	cost,
		Func< Node, int >	maxDegree = null
	)

Definition at line 179 of file SpanningForest.cs.

Satsuma.Kruskal< TCost >.Kruskal	(	IGraph	graph,
		Dictionary< Arc, TCost >	cost
	)

Definition at line 198 of file SpanningForest.cs.

Member Function Documentation

bool Satsuma.Kruskal< TCost >.AddArc

(

Arc

arc

)

Tries to add the specified arc to the current forest.

An arc cannot be added if it would either create a cycle in the forest, or the maximum degree constraint would be violated with the addition.

Returns

true if the arc could be added.

Definition at line 228 of file SpanningForest.cs.

void Satsuma.Kruskal< TCost >.Run

(

)

Runs the algorithm and completes the current forest to a spanning forest.

Definition at line 219 of file SpanningForest.cs.

bool Satsuma.Kruskal< TCost >.Step

(

)

Performs a step in Kruskal's algorithm.

A step means trying to insert the next arc into the forest.

Returns

true if the forest has not been completed with this step.

Definition at line 206 of file SpanningForest.cs.

Property Documentation

Func<Arc, TCost> Satsuma.Kruskal< TCost >.Cost

getset

An arbitrary function assigning costs to the arcs.

Definition at line 158 of file SpanningForest.cs.

Dictionary<Node, int> Satsuma.Kruskal< TCost >.Degree

getset

Contains the degree of a node in the found spanning forest.

Definition at line 173 of file SpanningForest.cs.

HashSet<Arc> Satsuma.Kruskal< TCost >.Forest

getset

Contains the arcs of the current forest.

The forest is empty at the beginning. Run can be used to run the whole algorithm and make a cheapest spanning forest.

Definition at line 169 of file SpanningForest.cs.

Subgraph Satsuma.Kruskal< TCost >.ForestGraph

getset

The current forest as a subgraph of the original graph.

Definition at line 171 of file SpanningForest.cs.

IGraph Satsuma.Kruskal< TCost >.Graph

getset

The input graph.

Definition at line 156 of file SpanningForest.cs.

Func<Node, int> Satsuma.Kruskal< TCost >.MaxDegree

getset

An optional per-node maximum degree constraint on the resulting spanning forest.

Can be null.

Warning

The algorithm will most probably find a suboptimal solution if a maximum degree constraint is imposed, as the minimum cost Hamiltonian path problem can be formulated as a minimum cost spanning tree problem with maximum degree 2.

Definition at line 164 of file SpanningForest.cs.

---

The documentation for this class was generated from the following file:

• src/SpanningForest.cs