1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: TestPRandomGraphSource.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 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 #include "vtkAdjacentVertexIterator.h"
21 #include "vtkBitArray.h"
22 #include "vtkDataSetAttributes.h"
23 #include "vtkDistributedGraphHelper.h"
24 #include "vtkGraph.h"
25 #include "vtkIdTypeArray.h"
26 #include "vtkMath.h"
27 #include "vtkOutEdgeIterator.h"
28 #include "vtkPBGLBreadthFirstSearch.h"
29 #include "vtkPBGLConnectedComponents.h"
30 #include "vtkPBGLGraphAdapter.h"
31 #include "vtkPBGLMinimumSpanningTree.h"
32 #include "vtkPBGLVertexColoring.h"
33 #include "vtkPBGLRandomGraphSource.h"
34 #include "vtkSmartPointer.h"
35 #include "vtkStreamingDemandDrivenPipeline.h"
36 #include "vtkVertexListIterator.h"
37
38 #include <vtksys/stl/functional>
39 #include <vtksys/stl/string>
40
41 #include <boost/mpi/collectives.hpp>
42 #include <boost/mpi/communicator.hpp>
43 #include <boost/mpi/timer.hpp>
44 #include <boost/lexical_cast.hpp>
45
46 #define VTK_CREATE(type, name) \
47 vtkSmartPointer<type> name = vtkSmartPointer<type>::New()
48
TestPRandomGraphSource(int argc,char * argv[])49 int TestPRandomGraphSource(int argc, char* argv[])
50 {
51 boost::mpi::environment env(argc, argv);
52 boost::mpi::communicator world;
53
54 vtkIdType wantVertices = 100;
55 vtkIdType wantEdges = 200;
56
57 bool doPrint = false;
58 bool onlyConnected = false;
59 bool doVerify = true;
60 bool doBFS = true;
61 bool doColoring = true;
62 bool doConnectedComponents = true;
63 bool doMST = true;
64
65 if (argc > 2)
66 {
67 wantVertices = boost::lexical_cast<vtkIdType>(argv[1]);
68 wantEdges = boost::lexical_cast<vtkIdType>(argv[2]);
69 }
70
71 // The Dehne-Gotz minimum spanning tree algorithm actually allocates
72 // O(|V|) memory, where |V| is the size of the full distributed
73 // graph. For this reason, we won't (by default) run the minimum
74 // spanning tree algorithm with > 1 million vertices.
75 if (wantVertices > 1000000)
76 {
77 doMST = false;
78 }
79
80 for (int argIdx = 3; argIdx < argc; ++argIdx)
81 {
82 std::string arg = argv[argIdx];
83 if (arg == "--print")
84 {
85 doPrint = true;
86 }
87 else if (arg == "--only-connected")
88 {
89 onlyConnected = true;
90 }
91 else if (arg == "--no-bfs")
92 {
93 doBFS = false;
94 }
95 else if (arg == "--no-coloring")
96 {
97 doColoring = false;
98 }
99 else if (arg == "--no-connected-components")
100 {
101 doConnectedComponents = false;
102 }
103 else if (arg == "--no-minumum-spanning-tree")
104 {
105 doMST = false;
106 }
107 else if (arg == "--minumum-spanning-tree")
108 {
109 doMST = true;
110 }
111 }
112
113 vtkIdType totalNumberOfVertices;
114 vtkIdType totalNumberOfEdges;
115 vtkGraph* g;
116
117 VTK_CREATE(vtkPBGLRandomGraphSource, source);
118
119 int errors = 0;
120
121 source->SetNumberOfVertices(wantVertices);
122 source->SetNumberOfEdges(wantEdges);
123
124 if (!onlyConnected)
125 {
126 if (world.rank() == 0)
127 {
128 cerr << "Testing simple random generator (" << wantVertices << ", "
129 << wantEdges << ")..." << endl;
130 }
131 source->Update();
132 g = source->GetOutput();
133
134 totalNumberOfVertices
135 = boost::mpi::all_reduce(world, g->GetNumberOfVertices(),
136 std::plus<vtkIdType>());
137 if (totalNumberOfVertices != wantVertices)
138 {
139 cerr << "ERROR: Wrong number of vertices ("
140 << totalNumberOfVertices << " != " << wantVertices << ")" << endl;
141 errors++;
142 }
143
144 totalNumberOfEdges
145 = boost::mpi::all_reduce(world, g->GetNumberOfEdges(),
146 std::plus<vtkIdType>());
147 if (totalNumberOfEdges != wantEdges)
148 {
149 cerr << "ERROR: Wrong number of edges ("
150 << totalNumberOfEdges << " != " << wantEdges << ")" << endl;
151 errors++;
152 }
153 if (world.rank() == 0)
154 {
155 cerr << "...done." << endl;
156 }
157 }
158
159 if (world.rank() == 0)
160 {
161 cerr << "Testing simple tree+random generator (" << wantVertices << ", "
162 << wantEdges << ")..." << endl;
163 }
164 source->SetStartWithTree(true);
165 source->Update();
166 g = source->GetOutput();
167
168 totalNumberOfVertices
169 = boost::mpi::all_reduce(world, g->GetNumberOfVertices(),
170 std::plus<vtkIdType>());
171 if (totalNumberOfVertices != wantVertices)
172 {
173 cerr << "ERROR: Wrong number of vertices ("
174 << totalNumberOfVertices << " != " << wantVertices << ")" << endl;
175 errors++;
176 }
177
178 totalNumberOfEdges
179 = boost::mpi::all_reduce(world, g->GetNumberOfEdges(),
180 std::plus<vtkIdType>());
181 if (totalNumberOfEdges != wantEdges + wantVertices - 1)
182 {
183 cerr << "ERROR: Wrong number of edges ("
184 << totalNumberOfEdges << " != " << (wantEdges + wantVertices - 1)
185 << ")" << endl;
186 errors++;
187 }
188
189 if (world.rank() == 0)
190 {
191 cerr << "...done." << endl;
192 }
193
194 if (doPrint)
195 {
196 vtkSmartPointer<vtkVertexListIterator> vertices
197 = vtkSmartPointer<vtkVertexListIterator>::New();
198 g->GetVertices(vertices);
199 while (vertices->HasNext())
200 {
201 vtkIdType u = vertices->Next();
202
203 vtkSmartPointer<vtkOutEdgeIterator> outEdges
204 = vtkSmartPointer<vtkOutEdgeIterator>::New();
205
206 g->GetOutEdges(u, outEdges);
207 while (outEdges->HasNext())
208 {
209 vtkOutEdgeType e = outEdges->Next();
210 cerr << " " << u << " -- " << e.Target << endl;
211 }
212 }
213 }
214
215 if (doBFS)
216 {
217 vtkSmartPointer<vtkPBGLBreadthFirstSearch> bfs
218 = vtkSmartPointer<vtkPBGLBreadthFirstSearch>::New();
219 bfs->SetInputData(g);
220 bfs->SetOriginVertex(g->GetDistributedGraphHelper()->MakeDistributedId(0, 0));
221
222 // Run the breadth-first search
223 if (world.rank() == 0)
224 {
225 cerr << "Breadth-first search...";
226 }
227 boost::mpi::timer timer;
228 bfs->UpdateInformation();
229 vtkStreamingDemandDrivenPipeline* exec =
230 vtkStreamingDemandDrivenPipeline::SafeDownCast(bfs->GetExecutive());
231 exec->SetUpdateNumberOfPieces(exec->GetOutputInformation(0), world.size());
232 exec->SetUpdatePiece(exec->GetOutputInformation(0), world.rank());
233 bfs->Update();
234
235 // Verify the results of the breadth-first search
236 if (world.rank() == 0)
237 {
238 cerr << " done in " << timer.elapsed() << " seconds" << endl;
239 }
240 }
241
242 if (doColoring)
243 {
244 vtkSmartPointer<vtkPBGLVertexColoring> coloring
245 = vtkSmartPointer<vtkPBGLVertexColoring>::New();
246 coloring->SetInputData(g);
247
248 // Run the vertex-coloring
249 if (world.rank() == 0)
250 {
251 cerr << "Vertex coloring...";
252 }
253 boost::mpi::timer timer;
254 coloring->UpdateInformation();
255 vtkStreamingDemandDrivenPipeline* exec =
256 vtkStreamingDemandDrivenPipeline::SafeDownCast(coloring->GetExecutive());
257 exec->SetUpdateNumberOfPieces(exec->GetOutputInformation(0), world.size());
258 exec->SetUpdatePiece(exec->GetOutputInformation(0), world.rank());
259 coloring->Update();
260
261 if (world.rank() == 0)
262 {
263 cerr << " done in " << timer.elapsed() << " seconds" << endl;
264 }
265
266 if (doVerify)
267 {
268 vtkGraph* output = vtkGraph::SafeDownCast(coloring->GetOutput());
269 if (world.rank() == 0)
270 {
271 cerr << " Verifying vertex coloring...";
272 }
273
274 // Turn the color array into a property map
275 vtkIdTypeArray* colorArray
276 = vtkIdTypeArray::SafeDownCast
277 (output->GetVertexData()->GetAbstractArray("Color"));
278 vtkDistributedVertexPropertyMapType<vtkIdTypeArray>::type colorMap
279 = MakeDistributedVertexPropertyMap(output, colorArray);
280
281 // Restart the timer
282 timer.restart();
283
284 vtkSmartPointer<vtkVertexListIterator> vertices
285 = vtkSmartPointer<vtkVertexListIterator>::New();
286 output->GetVertices(vertices);
287 while (vertices->HasNext())
288 {
289 vtkIdType u = vertices->Next();
290 vtkSmartPointer<vtkOutEdgeIterator> outEdges
291 = vtkSmartPointer<vtkOutEdgeIterator>::New();
292
293 output->GetOutEdges(u, outEdges);
294 while (outEdges->HasNext())
295 {
296 vtkOutEdgeType e = outEdges->Next();
297 if (get(colorMap, u) == get(colorMap, e.Target))
298 {
299 cerr << "ERROR: Found adjacent vertices " << u << " and "
300 << e.Target << " with the same color value ("
301 << get(colorMap, u) << ")" << endl;
302 ++errors;
303 }
304 }
305 }
306
307 output->GetDistributedGraphHelper()->Synchronize();
308
309 if (world.rank() == 0)
310 {
311 cerr << " done in " << timer.elapsed() << " seconds" << endl;
312 }
313 }
314 }
315
316 if (doConnectedComponents)
317 {
318 vtkSmartPointer<vtkPBGLConnectedComponents> cc
319 = vtkSmartPointer<vtkPBGLConnectedComponents>::New();
320 cc->SetInputData(g);
321
322 // Run the connected components algorithm
323 if (world.rank() == 0)
324 {
325 cerr << "Connected components...";
326 }
327 boost::mpi::timer timer;
328 cc->UpdateInformation();
329 vtkStreamingDemandDrivenPipeline* exec =
330 vtkStreamingDemandDrivenPipeline::SafeDownCast(cc->GetExecutive());
331 exec->SetUpdateNumberOfPieces(exec->GetOutputInformation(0), world.size());
332 exec->SetUpdatePiece(exec->GetOutputInformation(0), world.rank());
333 cc->Update();
334
335 if (world.rank() == 0)
336 {
337 cerr << " done in " << timer.elapsed() << " seconds" << endl;
338 }
339
340 if (doVerify)
341 {
342 vtkGraph* output = vtkGraph::SafeDownCast(cc->GetOutput());
343 if (world.rank() == 0)
344 {
345 cerr << " Verifying connected components...";
346 }
347
348 // Turn the component array into a property map
349 vtkIdTypeArray* componentArray
350 = vtkIdTypeArray::SafeDownCast
351 (output->GetVertexData()->GetAbstractArray("Component"));
352 vtkDistributedVertexPropertyMapType<vtkIdTypeArray>::type componentMap
353 = MakeDistributedVertexPropertyMap(output, componentArray);
354
355 // Restart the timer
356 timer.restart();
357
358 vtkSmartPointer<vtkVertexListIterator> vertices
359 = vtkSmartPointer<vtkVertexListIterator>::New();
360 output->GetVertices(vertices);
361 while (vertices->HasNext())
362 {
363 vtkIdType u = vertices->Next();
364 vtkSmartPointer<vtkOutEdgeIterator> outEdges
365 = vtkSmartPointer<vtkOutEdgeIterator>::New();
366
367 output->GetOutEdges(u, outEdges);
368 while (outEdges->HasNext())
369 {
370 vtkOutEdgeType e = outEdges->Next();
371 if (get(componentMap, u) != get(componentMap, e.Target))
372 {
373 cerr << "ERROR: Found adjacent vertices " << u << " and "
374 << e.Target << " with different component values ("
375 << get(componentMap, u) << " and "
376 << get(componentMap, e.Target) << ")" << endl;
377 ++errors;
378 }
379 }
380 }
381
382 output->GetDistributedGraphHelper()->Synchronize();
383
384 if (world.rank() == 0)
385 {
386 cerr << " done in " << timer.elapsed() << " seconds" << endl;
387 }
388 }
389 }
390
391 if (doMST)
392 {
393 vtkSmartPointer<vtkPBGLMinimumSpanningTree> mst
394 = vtkSmartPointer<vtkPBGLMinimumSpanningTree>::New();
395 mst->SetInputData(g);
396 mst->SetEdgeWeightArrayName("Weight");
397
398 // Create an edge-weight array with edge weights in [0, 1).
399 vtkDoubleArray *edgeWeightArray = vtkDoubleArray::New();
400 edgeWeightArray->SetName("Weight");
401 g->GetEdgeData()->AddArray(edgeWeightArray);
402 edgeWeightArray->SetNumberOfTuples(g->GetNumberOfEdges());
403 vtkMath::RandomSeed(1177 + 17 * world.rank());
404 for (vtkIdType i = 0; i < g->GetNumberOfEdges(); ++i)
405 {
406 edgeWeightArray->SetTuple1(i, vtkMath::Random());
407 }
408
409 // Run the shortest paths algorithm.
410 if (world.rank() == 0)
411 {
412 cerr << "Minimum spanning tree...";
413 }
414 boost::mpi::timer timer;
415 mst->UpdateInformation();
416 vtkStreamingDemandDrivenPipeline* exec =
417 vtkStreamingDemandDrivenPipeline::SafeDownCast(mst->GetExecutive());
418 exec->SetUpdateNumberOfPieces(exec->GetOutputInformation(0), world.size());
419 exec->SetUpdatePiece(exec->GetOutputInformation(0), world.rank());
420 mst->Update();
421
422 if (world.rank() == 0)
423 {
424 cerr << " done in " << timer.elapsed() << " seconds" << endl;
425 }
426 }
427
428 return errors;
429 }
430