1 /*========================================================================= 2 3 Program: Visualization Toolkit 4 Module: vtkBoostPrimMinimumSpanningTree.h 5 6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 7 All rights reserved. 8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 9 10 This software is distributed WITHOUT ANY WARRANTY; without even 11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 12 PURPOSE. See the above copyright notice for more information. 13 14 =========================================================================*/ 15 /*------------------------------------------------------------------------- 16 Copyright 2008 Sandia Corporation. 17 Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation, 18 the U.S. Government retains certain rights in this software. 19 -------------------------------------------------------------------------*/ 20 /** 21 * @class vtkBoostPrimMinimumSpanningTree 22 * @brief Constructs a minimum spanning 23 * tree from a graph, start node, and the weighting array 24 * 25 * 26 * 27 * This vtk class uses the Boost Prim Minimum Spanning Tree 28 * generic algorithm to perform a minimum spanning tree creation given 29 * a weighting value for each of the edges in the input graph and a 30 * a starting node for the tree. 31 * A couple of caveats to be noted with the Prim implementation versus the 32 * Kruskal implementation: 33 * 1. The negate edge weights function cannot be utilized to obtain a 34 * 'maximal' spanning tree (an exception is thrown when negated edge weights 35 * exist), and 36 * 2. the Boost implementation of the Prim algorithm returns a vertex 37 * predecessor map which results in some ambiguity about which edge from 38 * the original graph should be utilized if parallel edges between nodes 39 * exist; therefore, the current VTK implementation does not copy the edge 40 * data from the graph to the new tree. 41 * 42 * @sa 43 * vtkGraph vtkBoostGraphAdapter 44 */ 45 46 #ifndef vtkBoostPrimMinimumSpanningTree_h 47 #define vtkBoostPrimMinimumSpanningTree_h 48 49 #include "vtkInfovisBoostGraphAlgorithmsModule.h" // For export macro 50 #include "vtkStdString.h" // For string type 51 #include "vtkVariant.h" // For variant type 52 53 #include "vtkTreeAlgorithm.h" 54 55 class VTKINFOVISBOOSTGRAPHALGORITHMS_EXPORT vtkBoostPrimMinimumSpanningTree 56 : public vtkTreeAlgorithm 57 { 58 public: 59 static vtkBoostPrimMinimumSpanningTree* New(); 60 vtkTypeMacro(vtkBoostPrimMinimumSpanningTree, vtkTreeAlgorithm); 61 void PrintSelf(ostream& os, vtkIndent indent) override; 62 63 ///@{ 64 /** 65 * Set the name of the edge-weight input array, which must name an 66 * array that is part of the edge data of the input graph and 67 * contains numeric data. If the edge-weight array is not of type 68 * vtkDoubleArray, the array will be copied into a temporary 69 * vtkDoubleArray. 70 */ 71 vtkSetStringMacro(EdgeWeightArrayName); 72 ///@} 73 74 /** 75 * Set the index (into the vertex array) of the 76 * minimum spanning tree 'origin' vertex. 77 */ 78 void SetOriginVertex(vtkIdType index); 79 80 /** 81 * Set the minimum spanning tree 'origin' vertex. 82 * This method is basically the same as above 83 * but allows the application to simply specify 84 * an array name and value, instead of having to 85 * know the specific index of the vertex. 86 */ 87 void SetOriginVertex(vtkStdString arrayName, vtkVariant value); 88 89 ///@{ 90 /** 91 * Stores the graph vertex ids for the tree vertices in an array 92 * named "GraphVertexId". Default is off. 93 */ 94 vtkSetMacro(CreateGraphVertexIdArray, bool); 95 vtkGetMacro(CreateGraphVertexIdArray, bool); 96 vtkBooleanMacro(CreateGraphVertexIdArray, bool); 97 ///@} 98 99 ///@{ 100 /** 101 * Whether to negate the edge weights. By negating the edge 102 * weights this algorithm will give you the 'maximal' spanning 103 * tree (i.e. the algorithm will try to create a spanning tree 104 * with the highest weighted edges). Defaulted to Off. 105 * FIXME: put a real definition in... 106 */ 107 void SetNegateEdgeWeights(bool value); 108 vtkGetMacro(NegateEdgeWeights, bool); 109 vtkBooleanMacro(NegateEdgeWeights, bool); 110 ///@} 111 112 protected: 113 vtkBoostPrimMinimumSpanningTree(); 114 ~vtkBoostPrimMinimumSpanningTree() override; 115 116 int RequestData(vtkInformation*, vtkInformationVector**, vtkInformationVector*) override; 117 118 int FillInputPortInformation(int port, vtkInformation* info) override; 119 120 private: 121 char* EdgeWeightArrayName; 122 vtkIdType OriginVertexIndex; 123 vtkVariant OriginValue; 124 bool CreateGraphVertexIdArray; 125 bool ArrayNameSet; 126 char* ArrayName; 127 bool NegateEdgeWeights; 128 float EdgeWeightMultiplier; 129 130 ///@{ 131 /** 132 * Using the convenience function internally 133 */ 134 vtkSetStringMacro(ArrayName); 135 ///@} 136 137 /** 138 * This method is basically a helper function to find 139 * the index of a specific value within a specific array 140 */ 141 vtkIdType GetVertexIndex(vtkAbstractArray* abstract, vtkVariant value); 142 143 vtkBoostPrimMinimumSpanningTree(const vtkBoostPrimMinimumSpanningTree&) = delete; 144 void operator=(const vtkBoostPrimMinimumSpanningTree&) = delete; 145 }; 146 147 #endif 148