Satsuma.Prim< TCost > Class Template Reference

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

Public Member Functions
	Prim (IGraph graph, Func< Arc, TCost > cost)
	Prim (IGraph graph, Dictionary< Arc, TCost > cost)

Properties
Func< Arc, TCost >	Cost [get, set]
HashSet< Arc >	Forest [get, set]
	Contains the arcs of a cheapest spanning forest. More...
Subgraph	ForestGraph [get, set]
	The cheapest spanning forest as a subgraph of the original graph. More...
IGraph	Graph [get, set]

Detailed Description

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

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

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

Example:

CompleteGraph g = new CompleteGraph(10);
Node u = g.GetNode(0);
Node v = g.GetNode(1);
Node w = g.GetNode(2);
var expensiveArcs = new HashSet<Arc>() { g.GetArc(u, v), g.GetArc(v, w) };
Func<Arc, double> cost = (arc => expensiveArcs.Contains(arc) ? 1.5 : 1.0);
var p = new Prim<double>(g, cost);
// the graph is connected, so the spanning forest is a tree
Console.WriteLine("Total cost of a minimum cost spanning tree: "+p.Forest.Sum(cost));
Console.WriteLine("A minimum cost spanning tree:");
foreach (var arc in p.Forest) Console.WriteLine(g.ArcToString(arc));

Note

The graph in the example is a complete graph, which is dense. That's why we have used Prim<TCost> instead of Kruskal<TCost>.

Template Parameters

TCost

The arc cost type.

Type Constraints

TCost

:

IComparable<TCost>

Definition at line 55 of file SpanningForest.cs.

Constructor & Destructor Documentation

Satsuma.Prim< TCost >.Prim	(	IGraph	graph,
		Func< Arc, TCost >	cost
	)

Definition at line 66 of file SpanningForest.cs.

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

Definition at line 77 of file SpanningForest.cs.

Property Documentation

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

getset

Definition at line 59 of file SpanningForest.cs.

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

getset

Contains the arcs of a cheapest spanning forest.

Definition at line 62 of file SpanningForest.cs.

Subgraph Satsuma.Prim< TCost >.ForestGraph

getset

The cheapest spanning forest as a subgraph of the original graph.

Definition at line 64 of file SpanningForest.cs.

IGraph Satsuma.Prim< TCost >.Graph

getset

Definition at line 58 of file SpanningForest.cs.

---

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

• src/SpanningForest.cs