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