Minimum Spanning Tree quick graph

Question

I want to find the minimum spanning tree of the following graph using quick graph. I Went through the manual provided but I don't really understand how to do it. Here is my code:

 static void Main(string[] args)
        {

        var g = new UndirectedGraph<int, TaggedUndirectedEdge<int,int>>();

        var e1 = new TaggedUndirectedEdge<int, int>(1, 2, 57);
        var e2 = new TaggedUndirectedEdge<int, int>(1, 4, 65);
        var e3 = new TaggedUndirectedEdge<int, int>(2, 3, 500);
        var e4 = new TaggedUndirectedEdge<int, int>(2, 4, 1);
        var e5 = new TaggedUndirectedEdge<int, int>(3, 4, 78);
        var e6 = new TaggedUndirectedEdge<int, int>(3, 5, 200);

        g.AddVerticesAndEdge(e1);
        g.AddVerticesAndEdge(e2);
        g.AddVerticesAndEdge(e3);
        g.AddVerticesAndEdge(e4);
        g.AddVerticesAndEdge(e5);
        g.AddVerticesAndEdge(e6);

        foreach (var v in g.Edges)
            Console.WriteLine(v);
}

Thank you for your help.

have you read http://quickgraph.codeplex.com/wikipage?title=Minimum%20Spanning%20Tree — daryal, Jan 28 '13 at 08:12
Yes I did but i was kind of lost when i read this line:"Func edgeWeights = ...;" — cgadjoro, Jan 28 '13 at 08:15

score 3 · Accepted Answer · edited May 23 '17 at 12:34

3

@daryal beat me to it - my version is:

var mst = g.MinimumSpanningTreePrim(e => e.Tag).ToList();

enter image description here

"Use the source Luke" - I looked at MinimumSpanningTreeTest.cs, test Prim12273

(Also you could look at this question on Lambda's / Delegates for a better understanding of basic function pointers)

edited May 23 '17 at 12:34

Community

1
1

answered Jan 28 '13 at 09:48

mhoff

403
4
11

score 1 · Answer 2 · answered Jan 28 '13 at 08:24

Assuming that the Tag (last) parameter of TaggedUndirectedEdge implies the edgeWeight of the edge, the following may work.

Func<TEdge, double> edgeWeights = (q) => {
g.Edges.SingleOrDefault(m => q == m).Tag;
}

IEnumerable<TEdge> mst = g.MinimumSpanningTreePrim(g, edgeWeights);

Minimum Spanning Tree quick graph

2 Answers2