Question about Prim spanning tree algorithm

Topics: algorithm, bug, graph
Dec 27, 2008 at 7:06 PM
Hello,
I tried to call PrimMinimumSpanningTreeAlgorithm for simple input and I got wrong results. So this is my input:
 AdjacencyGraph<TVertex,TEdge> adjency_graph with edges (1,2), (3,2),(3,4),(1,4) and all weights are equal to 1.
I use the following code to call PrimMinimumSpanningTreeAlgorithm:

     IDictionary<TEdge, double> weights = new Dictionary<TEdge, double>();
     IEnumerable<TEdge> edges = adjency_graph.Edges;
            foreach (TEdge edge in edges)
            {
                weights.Add(edge, 1);
            }
       UndirectedGraph<TVertex, TEdge> undirectedgraph =
               new UndirectedGraph<TVertex, TEdge>();
            foreach (TVertex v in adjency_graph.Vertices)
                undirectedgraph.AddVertex(v);
            foreach (TEdge e1 in adjency_graph.Edges)
                if (!undirectedgraph.ContainsEdge(e1.Source, e1.Target))
                    undirectedgraph.AddEdge(e1);

   Then I call PrimMinimumSpanningTreeAlgorithm in debugging mode

  Prim_alg =
             new PrimMinimumSpanningTreeAlgorithm<TVertex, TEdge>(undirectedgraph, weights);

          
            Prim_alg.Compute(root);  //root is 1


   I see in InternalCompute method that only (1,2) and (1,4) edges give TreeEdge event and it is not sufficient because vertex 3 does   not belong such tree.
   I suppose that problem is because you process only edge.Target but not process edge.Source. I tried to improve
  code of InternalCompute as the following (in the cycle):
  TVertex second_end;
 foreach (var edge in this.VisitedGraph.AdjacentEdges(u))
                    {
                        if (cancelManager.IsCancelling)
                            return;
                        double edgeWeight = this.EdgeWeights[edge];
                        //My
                        if(edge.Target.Equals(u))
                        {
                            second_end = edge.Source;
                        }
                        else
                            second_end=edge.Target;

                        if (
                            queue.Contains(second_end) &&
                            edgeWeight < this.minimumWeights[second_end]
                            )
                        {
                            this.minimumWeights[second_end] = edgeWeight;
                            this.queue.Update(second_end);
                            this.OnTreeEdge(edge);
                        }
                    }

 Am I right or I have missed something?
 Thank you
Evgeny
 


Coordinator
Dec 29, 2008 at 1:39 PM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
Coordinator
Dec 31, 2008 at 2:32 PM
There was a general issue with undirected graph algorithms. Things have been fixed and tested now.
Jan 2, 2009 at 6:27 PM
Edited Jan 2, 2009 at 6:29 PM
Hello,

I tried your implementation of Prim spanning tree algorithm after your changes: I downloaded release 29565 and changed my program
according to MinimumSpanningTreePrim method from AlgorithmExtensions class. You just use here your UndirectedDijkstraShortestPathAlgorithm and then return tree that consists from edges that are included in shortest paths from some (default) vertex to all other vertices. IMHO that did not guarantee that the result is minimum spanning tree. I tested this algorithm with a graph from book "Graph theory" by N.Christofides, chapter 7 “Trees, paragraph 3.4 (I have Russian translation of 1975 year). The weight of minimal spanning tree is equal to 63. But your algorithm gives 88. I modified slightly  MinimumSpanningTreePrim and tried it for all vertices being the root. The minimal weight is when the root is vertex 10 and it is equal to 72.  But it is greater than 63. So the minimal tree could not be founded by this way. I add an XML representation of this graph so you could check it:

<?xml version="1.0" encoding="utf-8"?>

  <graph>

    <node id="1" />

    <node id="2" />

    <node id="3" />

    <node id="4" />

    <node id="5"  />

    <node id="6" />

    <node id="7" />

    <node id="8" />

    <node id="9" />

    <node id="10" />

    <node id="11" />

    <node id="12" />

    <edge id="1_2" source="1" target="2" weight="6" />

    <edge id="1_4" source="1" target="4" weight="11" />

    <edge id="1_5" source="1" target="5" weight="5" />

    <edge id="2_5" source="2" target="5" weight="8" />

    <edge id="2_3" source="2" target="3" weight="15" />

    <edge id="2_4" source="2" target="4" weight="18" />

    <edge id="2_7" source="2" target="7" weight="11" />

    <edge id="3_4" source="3" target="4" weight="8" />

    <edge id="3_8" source="3" target="8" weight="18" />

    <edge id="3_9" source="3" target="9" weight="6" />

    <edge id="4_6" source="4" target="6" weight="10" />

    <edge id="4_7" source="4" target="7" weight="7" />

    <edge id="4_11" source="4" target="11" weight="17" />

    <edge id="5_6" source="5" target="6" weight="15" />

    <edge id="5_7" source="5" target="7" weight="9" />

    <edge id="6_11" source="6" target="11" weight="3" />

    <edge id="7_8" source="7" target="8" weight="9" />

    <edge id="7_9" source="7" target="9" weight="4" />

    <edge id="7_11" source="7" target="11" weight="12" />

    <edge id="7_10" source="7" target="10" weight="13" />

    <edge id="8_9" source="8" target="9" weight="14" />

    <edge id="8_12" source="8" target="12" weight="5" />

    <edge id="9_10" source="9" target="10" weight="19" />

    <edge id="10_12" source="10" target="12" weight="2" />

    <edge id="11_12" source="11" target="12" weight="7" />

  </graph>

Coordinator
Jan 2, 2009 at 8:55 PM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
Coordinator
Jan 2, 2009 at 10:23 PM
Good catch. I was not asserting correctly the result of Kruskal and Prim. As for prim, I was not using the correct combine method for the relaxation (should be weight instead of distance + weight).