1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkPBGLCollapseParallelEdges.cxx
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 (c) Sandia Corporation
17 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
18 ----------------------------------------------------------------------------*/
19
20 #include "vtkPBGLCollapseParallelEdges.h"
21
22 #if !defined(VTK_LEGACY_REMOVE)
23
24 #include "vtkDataSetAttributes.h"
25 #include "vtkEdgeListIterator.h"
26 #include "vtkInformation.h"
27 #include "vtkInformationVector.h"
28 #include "vtkMutableDirectedGraph.h"
29 #include "vtkMutableUndirectedGraph.h"
30 #include "vtkObjectFactory.h"
31 #include "vtkOutEdgeIterator.h"
32 #include "vtkPBGLDistributedGraphHelper.h"
33 #include "vtkPBGLGraphAdapter.h"
34 #include "vtkSmartPointer.h"
35 #include "vtkStreamingDemandDrivenPipeline.h"
36 #include "vtkTable.h"
37 #include "vtkTimerLog.h"
38 #include "vtkVariantArray.h"
39 #include "vtkVertexListIterator.h"
40
41 #include <vtksys/stl/map>
42 #include <vtksys/stl/utility> // for pair
43
44 vtkStandardNewMacro(vtkPBGLCollapseParallelEdges);
45
vtkPBGLCollapseParallelEdges()46 vtkPBGLCollapseParallelEdges::vtkPBGLCollapseParallelEdges()
47 {
48 VTK_LEGACY_BODY(vtkPBGLCollapseParallelEdges::vtkPBGLCollapseParallelEdges, "VTK 6.2");
49 }
50
~vtkPBGLCollapseParallelEdges()51 vtkPBGLCollapseParallelEdges::~vtkPBGLCollapseParallelEdges()
52 {
53 }
54
PrintSelf(ostream & os,vtkIndent indent)55 void vtkPBGLCollapseParallelEdges::PrintSelf(ostream& os, vtkIndent indent)
56 {
57 this->Superclass::PrintSelf(os, indent);
58 }
59
60 template<class MutableGraph>
vtkPBGLCollapseParallelEdgesRequestData(vtkPBGLCollapseParallelEdges * self,vtkInformation *,vtkInformationVector ** input_vec,vtkInformationVector * output_vec)61 int vtkPBGLCollapseParallelEdgesRequestData(
62 vtkPBGLCollapseParallelEdges* self,
63 vtkInformation*,
64 vtkInformationVector** input_vec,
65 vtkInformationVector* output_vec)
66 {
67 vtkSmartPointer<vtkTimerLog> timer = vtkSmartPointer<vtkTimerLog>::New();
68 timer->StartTimer();
69
70 vtkGraph* input = vtkGraph::GetData(input_vec[0]);
71 vtkGraph* output = vtkGraph::GetData(output_vec);
72
73 vtkPBGLDistributedGraphHelper* input_helper =
74 vtkPBGLDistributedGraphHelper::SafeDownCast(input->GetDistributedGraphHelper());
75
76 // Create directed or undirected graph
77 MutableGraph* builder = MutableGraph::New();
78
79 // Setup the graph as a distributed graph
80 vtkSmartPointer<vtkPBGLDistributedGraphHelper> output_helper =
81 vtkSmartPointer<vtkPBGLDistributedGraphHelper>::New();
82 builder->SetDistributedGraphHelper(output_helper);
83
84 // Distributed weight map
85 vtkSmartPointer<vtkIntArray> weight_arr = vtkSmartPointer<vtkIntArray>::New();
86 weight_arr->SetName("weight");
87 typedef vtkDistributedEdgePropertyMapType<vtkIntArray>::type
88 DistributedWeightMap;
89 DistributedWeightMap distrib_weight_arr
90 = MakeDistributedEdgePropertyMap(builder, weight_arr.GetPointer());
91
92 // Prepare vertex data.
93 vtkAbstractArray *input_pedigrees = input->GetVertexData()->GetPedigreeIds();
94 vtkAbstractArray *pedigrees
95 = vtkAbstractArray::CreateArray(input_pedigrees->GetDataType());
96 pedigrees->SetName(input_pedigrees->GetName());
97 builder->GetVertexData()->AddArray(pedigrees);
98 builder->GetVertexData()->SetPedigreeIds(pedigrees);
99
100 // Prepare edge data.
101 builder->GetEdgeData()->AddArray(weight_arr);
102
103 // Iterate through input graph, adding vertices.
104 // This assumes the vertices will be distributed in the same way
105 // as the input graph.
106 vtkSmartPointer<vtkVertexListIterator> vertices
107 = vtkSmartPointer<vtkVertexListIterator>::New();
108 input->GetVertices(vertices);
109 while (vertices->HasNext())
110 {
111 vtkIdType v = vertices->Next();
112 vtkIdType ind = input->GetDistributedGraphHelper()->GetVertexIndex(v);
113 builder->LazyAddVertex(input_pedigrees->GetVariantValue(ind));
114 }
115 output_helper->Synchronize();
116
117 // Iterate through input edges, adding a new edge for every new (source,target) pair.
118 vtksys_stl::map<vtksys_stl::pair<vtkIdType, vtkIdType>, int> edge_weights;
119 vtkSmartPointer<vtkOutEdgeIterator> out_edges
120 = vtkSmartPointer<vtkOutEdgeIterator>::New();
121 input->GetVertices(vertices);
122 while (vertices->HasNext())
123 {
124 vtkIdType u = vertices->Next();
125 input->GetOutEdges(u, out_edges);
126 while (out_edges->HasNext())
127 {
128 vtkOutEdgeType e = out_edges->Next();
129 //cerr << "processing edge " << u << " to " << e.Target << endl;
130 vtkIdType a = u;
131 vtkIdType b = e.Target;
132 if (u > e.Target)
133 {
134 a = e.Target;
135 b = u;
136 }
137 vtksys_stl::pair<vtkIdType,vtkIdType> p(a, b);
138 if (edge_weights.count(p) > 0)
139 {
140 edge_weights[p]++;
141 }
142 else
143 {
144 edge_weights[p] = 1;
145 }
146 }
147 }
148
149 vtksys_stl::map<vtksys_stl::pair<vtkIdType, vtkIdType>, int>::iterator wi;
150 for (wi = edge_weights.begin(); wi != edge_weights.end(); ++wi)
151 {
152 builder->LazyAddEdge(wi->first.first, wi->first.second);
153 }
154 output_helper->Synchronize();
155
156 vtkSmartPointer<vtkEdgeListIterator> edges
157 = vtkSmartPointer<vtkEdgeListIterator>::New();
158 builder->GetEdges(edges);
159 while (edges->HasNext())
160 {
161 vtkEdgeType e = edges->Next();
162 vtksys_stl::pair<vtkIdType,vtkIdType> p(e.Source, e.Target);
163 weight_arr->InsertNextValue(edge_weights[p]);
164 //put(distrib_weight_arr, e, edge_weights[p]);
165 }
166 output_helper->Synchronize();
167
168 int rank = process_id(output_helper->GetProcessGroup());
169
170 // Copy into output graph
171 if (!output->CheckedShallowCopy(builder))
172 {
173 vtkErrorWithObjectMacro(self, "Could not copy to output.");
174 return 0;
175 }
176
177 timer->StopTimer();
178 cerr << "vtkPBGLCollapseParallelEdges: " << timer->GetElapsedTime() << endl;
179
180 return 1;
181 }
182
RequestData(vtkInformation * info,vtkInformationVector ** input_vec,vtkInformationVector * output_vec)183 int vtkPBGLCollapseParallelEdges::RequestData(
184 vtkInformation* info,
185 vtkInformationVector** input_vec,
186 vtkInformationVector* output_vec)
187 {
188 vtkGraph* input = vtkGraph::GetData(input_vec[0]);
189 if (vtkDirectedGraph::SafeDownCast(input))
190 {
191 return vtkPBGLCollapseParallelEdgesRequestData<vtkMutableDirectedGraph>(
192 this, info, input_vec, output_vec);
193 }
194 return vtkPBGLCollapseParallelEdgesRequestData<vtkMutableUndirectedGraph>(
195 this, info, input_vec, output_vec);
196 }
197
198 #endif //VTK_LEGACY_REMOVE
199