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