![]() |
Satsuma
a delicious .NET graph library
|
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) | |
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... | |
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... | |
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.
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.
TCost | The arc cost type. |
TCost | : | IComparable<TCost> |
Definition at line 139 of file SpanningForest.cs.
Satsuma.Kruskal< TCost >.Kruskal | ( | IGraph | graph, |
Func< Arc, TCost > | cost, | ||
Func< Node, int > | maxDegree = null |
||
) |
Definition at line 164 of file SpanningForest.cs.
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.
true
if the arc could be added. Definition at line 206 of file SpanningForest.cs.
void Satsuma.Kruskal< TCost >.Run | ( | ) |
Runs the algorithm and completes the current forest to a spanning forest.
Definition at line 197 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.
true
if the forest has not been completed with this step. Definition at line 184 of file SpanningForest.cs.
|
getset |
An arbitrary function assigning costs to the arcs.
Definition at line 145 of file SpanningForest.cs.
|
getset |
Contains the degree of a node in the found spanning forest.
Definition at line 158 of file SpanningForest.cs.
|
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 156 of file SpanningForest.cs.
|
getset |
The input graph.
Definition at line 143 of file SpanningForest.cs.
|
getset |
An optional per-node maximum degree constraint on the resulting spanning forest.
Can be null.
Definition at line 151 of file SpanningForest.cs.