CP-13675: Spanning tree algorithm produces wrong results when used on a simple delegate graph.

From unknown CodePlex user on Sunday, 19 July 2009 20:00:53

Hi Jonathan, I copy this from the discussions, together with a little cleaned up source, as it is more appropriate here.Can this be caused by some global state used by the algorithm (Dijkstra, BFS) that gets overwritten as multiple vertices are processed simultaneously (as there is no problem with the non-delegated version)? Thanks, Vlad

Something wrong goes on with the Delegate graphs. I attach an example of a very simple graph where I try to find a spanning tree. This is an F# code. I just build a delegate graph (which is a "trunk" chain of 99 edges with four additional "branches" of one edge) using a switch-case expression and there is just a single call to the spanning tree algorithm. getMEM_filter_simple uses chains_scores_1_read_simple to generate a graph of 99 nodes, with edge i<- >i+1 of weight 0 for all i in [0..97] and 4 edges of non-zero weight. This graph has a maximum spanning tree of weight 40. When I use Kruskal (the weights are set as "minus tag") I get the correct result of 40. If MinimumSpanningTreeKruskal is replaced with MinimumSpanningTreePrim I get a result of 32 with edge 68-93 missing from the optimal tree. I tried to replace FibonacciHeap with the BinaryQueue and got another result for MST: 24! (Side note, I head to modify in "class BinaryQueue<TVertex, TDistance> : IQueue" IQueue to IPriorityQueue. For some reason it was different than in FibonacciQueue).

I did not have such a discrepancy between Kruskal and Prim prior to switching to the Delegate graph. Notice that Kruskal has to precompute all the edges in advance so for Kruskal the Delegates does not matter.

#light
open System
open QuickGraph
open QuickGraph.Algorithms
open QuickGraph.Collections
open System.Collections.Generic
open System.IO

let chains_scores_1_read_simple input_read =     
    let edge =
        match input_read with
        |19 -> seq[new SUndirectedTaggedEdge<int, int> (19, 47, 11);new SUndirectedTaggedEdge<int, int> (input_read, input_read+1, 0)]
        |61 ->  seq[new SUndirectedTaggedEdge<int, int> (61, 87, 13);new SUndirectedTaggedEdge<int, int> (input_read, input_read+1, 0)]
        |39 -> seq[new SUndirectedTaggedEdge<int, int> (39, 96, 8);new SUndirectedTaggedEdge<int, int> (input_read, input_read+1, 0)]
        |68 -> seq[new SUndirectedTaggedEdge<int, int> (68, 93, 8);new SUndirectedTaggedEdge<int, int> (input_read, input_read+1, 0)]
        |98 -> Seq.empty
        |input_read -> seq[ new SUndirectedTaggedEdge<int, int> (input_read, input_read+1, 0)]
    edge    

let getMEM_filter_simple () =
    new TryFunc<int, IEnumerable<SUndirectedTaggedEdge<int, int>>  >
      (
      fun i ([<Out>] res: byref <IEnumerable<SUndirectedTaggedEdge<int, int>>>  ) ->

           res <-   (chains_scores_1_read_simple   i  )
           Printf.printf "edges=%A\n" (Seq.to_array res)
           not (Seq.isEmpty res))    

let build_graph ()= 
    let encoding=new System.Text.ASCIIEncoding()
    let num_reads = 99
    let edge_enum = getMEM_filter_simple ()
    let graph = new DelegateUndirectedGraph<int,SUndirectedTaggedEdge<int, int>>
                     ((seq[0..num_reads - 1]), edge_enum, false)
    let mst_edges = graph.MinimumSpanningTreeKruskal  (fun key -> -float (key.Tag))
    let mutable weight = 0
    for edge in mst_edges do
        weight <- weight + edge.Tag
        Printf.printf "Edge %A\n" edge

    Printf.printf "Total weight=%d\n" weight        

let _ = build_graph()

FubarDevelopment / QuickGraph

CP-13675: Spanning tree algorithm produces wrong results when used on a simple delegate graph. #85