Skip to content
  • Jason Shepherd's avatar
    ENH: Completing an implementation of the Boost Prim minimal spanning tree... · 9b2939ea
    Jason Shepherd authored
    ENH: Completing an implementation of the Boost Prim minimal spanning tree algorithm.  There are two caveats to be noted with this implementation versus the Kruskal MST implementation which was implemented earlier:
    1. Unlike the Kruskal implementation, the NegateEdgeWeights function cannot be utilized to obtain a 'maximal' spanning tree (an exception is thrown when negated edge weights exist), and
    2. the Boost implementation of the Prim algorithm returns a vertex predecessor map which results in some ambiguity about which edge from the original graph should be utilized if parallel edges between nodes exist; therefore, the current VTK implementation does not copy the edge data from the graph to the new tree.
    9b2939ea