1 /*=========================================================================
2 
3   Program:   Visualization Toolkit
4   Module:    vtkPBGLRandomGraphSource.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 "vtkPBGLRandomGraphSource.h"
21 
22 #if !defined(VTK_LEGACY_REMOVE)
23 
24 #include "vtkBlockDistribution.h"
25 #include "vtkCellData.h"
26 #include "vtkExecutive.h"
27 #include "vtkFloatArray.h"
28 #include "vtkGraph.h"
29 #include "vtkIdTypeArray.h"
30 #include "vtkInformation.h"
31 #include "vtkMath.h"
32 #include "vtkMPI.h"
33 #include "vtkMutableDirectedGraph.h"
34 #include "vtkMutableUndirectedGraph.h"
35 #include "vtkObjectFactory.h"
36 #include "vtkPBGLDistributedGraphHelper.h"
37 #include "vtkPointData.h"
38 #include "vtkSmartPointer.h"
39 
40 #include <vtksys/stl/set>
41 #include <vtksys/stl/algorithm>
42 #include <vtksys/stl/functional>
43 
44 #include <boost/mpi/communicator.hpp>
45 #include <boost/mpi/collectives/scan.hpp>
46 
47 vtkStandardNewMacro(vtkPBGLRandomGraphSource);
48 
49 // ----------------------------------------------------------------------
vtkPBGLRandomGraphSource()50 vtkPBGLRandomGraphSource::vtkPBGLRandomGraphSource()
51 {
52   int rank;
53   MPI_Comm_rank(MPI_COMM_WORLD, &rank);
54 
55   this->NumberOfVertices = 10;
56   this->NumberOfEdges = 10;
57   this->EdgeProbability = 0.5;
58   this->IncludeEdgeWeights = false;
59   this->Directed = 0;
60   this->UseEdgeProbability = 0;
61   this->StartWithTree = 0;
62   this->AllowSelfLoops = false;
63   this->AllowBalancedEdgeDistribution = true;
64   this->GeneratePedigreeIds = true;
65   this->VertexPedigreeIdArrayName = 0;
66   this->SetVertexPedigreeIdArrayName("vertex id");
67   this->EdgePedigreeIdArrayName = 0;
68   this->SetEdgePedigreeIdArrayName("edge id");
69   this->EdgeWeightArrayName = 0;
70   this->SetEdgeWeightArrayName("edge weight");
71   this->Seed = 1177 + 17 * rank;
72   this->SetNumberOfInputPorts(0);
73   this->SetNumberOfOutputPorts(1);
74 
75   VTK_LEGACY_BODY(vtkPBGLRandomGraphSource::vtkPBGLRandomGraphSource, "VTK 6.2");
76 }
77 
78 // ----------------------------------------------------------------------
79 
~vtkPBGLRandomGraphSource()80 vtkPBGLRandomGraphSource::~vtkPBGLRandomGraphSource()
81 {
82   this->SetVertexPedigreeIdArrayName(0);
83   this->SetEdgePedigreeIdArrayName(0);
84   this->SetEdgeWeightArrayName(0);
85 }
86 
87 // ----------------------------------------------------------------------
88 
89 void
PrintSelf(ostream & os,vtkIndent indent)90 vtkPBGLRandomGraphSource::PrintSelf(ostream& os, vtkIndent indent)
91 {
92   this->Superclass::PrintSelf(os, indent);
93   os << indent << "NumberOfVertices: " << this->NumberOfVertices << endl;
94   os << indent << "NumberOfEdges: " << this->NumberOfEdges << endl;
95   os << indent << "EdgeProbability: " << this->EdgeProbability << endl;
96   os << indent << "IncludeEdgeWeights: " << this->IncludeEdgeWeights << endl;
97   os << indent << "Directed: " << this->Directed << endl;
98   os << indent << "UseEdgeProbability: " << this->UseEdgeProbability << endl;
99   os << indent << "StartWithTree: " << this->StartWithTree << endl;
100   os << indent << "AllowSelfLoops: " << this->AllowSelfLoops << endl;
101   os << indent << "AllowBalancedEdgeDistribution: " << this->AllowBalancedEdgeDistribution << endl;
102   os << indent << "GeneratePedigreeIds: " << this->GeneratePedigreeIds << endl;
103   os << indent << "VertexPedigreeIdArrayName: "
104     << (this->VertexPedigreeIdArrayName ? this->VertexPedigreeIdArrayName : "(null)") << endl;
105   os << indent << "EdgePedigreeIdArrayName: "
106     << (this->EdgePedigreeIdArrayName ? this->EdgePedigreeIdArrayName : "(null)") << endl;
107   os << indent << "EdgeWeightArrayName: "
108     << (this->EdgeWeightArrayName ? this->EdgeWeightArrayName : "(null)") << endl;
109   os << indent << "Seed: " << this->Seed << endl;
110 }
111 
112 // ----------------------------------------------------------------------
113 
114 int
RequestData(vtkInformation *,vtkInformationVector **,vtkInformationVector * outputVector)115 vtkPBGLRandomGraphSource::RequestData(
116   vtkInformation*,
117   vtkInformationVector**,
118   vtkInformationVector *outputVector)
119 {
120   int myRank;
121   int numProcs;
122   MPI_Comm_rank(MPI_COMM_WORLD, &myRank);
123   MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
124 
125   // Seed the random number generator so we can produce repeatable results
126   vtkMath::RandomSeed(this->Seed);
127 
128   // Create a mutable graph of the appropriate type.
129   vtkSmartPointer<vtkMutableDirectedGraph> dirBuilder =
130     vtkSmartPointer<vtkMutableDirectedGraph>::New();
131   vtkSmartPointer<vtkMutableUndirectedGraph> undirBuilder =
132     vtkSmartPointer<vtkMutableUndirectedGraph>::New();
133 
134   // Create a Parallel BGL distributed graph helper
135   vtkSmartPointer<vtkPBGLDistributedGraphHelper> helper
136     = vtkSmartPointer<vtkPBGLDistributedGraphHelper>::New();
137 
138   // Hook the distributed graph helper into the graph to make it a
139   // distributed graph.
140   if (this->Directed)
141     {
142     dirBuilder->SetDistributedGraphHelper(helper);
143     }
144   else
145     {
146     undirBuilder->SetDistributedGraphHelper(helper);
147     }
148 
149   // A simple block distribution of vertices.
150   vtkBlockDistribution distribution(this->NumberOfVertices, numProcs);
151 
152   // Add NumberOfVertices new vertices.
153   vtkIdType myNumberOfVertices = distribution.GetBlockSize(myRank);
154   vtkIdType myStartVertex = distribution.GetFirstGlobalIndexOnProcessor(myRank);
155   vtkIdType myEndVertex = myStartVertex + myNumberOfVertices;
156   for (vtkIdType i = 0; i < myNumberOfVertices; ++i)
157     {
158     if (this->Directed)
159       {
160       dirBuilder->AddVertex();
161       }
162     else
163       {
164       undirBuilder->AddVertex();
165       }
166     }
167 
168   // Make sure everyone has added their own local vertices.
169   helper->Synchronize();
170 
171   if (this->StartWithTree)
172     {
173     vtkIdType myStart = myStartVertex;
174     if (myStart == 0)
175       {
176       myStart = 1;
177       }
178 
179     for (vtkIdType i = myStart; i < myEndVertex; i++)
180       {
181       // Pick a random vertex in [0, i-1].
182       int j = static_cast<vtkIdType>(vtkMath::Random(0, i));
183 
184       vtkIdType iVertex
185         = helper->MakeDistributedId(distribution.GetProcessorOfElement(i),
186                                     distribution.GetLocalIndexOfElement(i));
187       vtkIdType jVertex
188         = helper->MakeDistributedId(distribution.GetProcessorOfElement(j),
189                                     distribution.GetLocalIndexOfElement(j));
190 
191       if (this->Directed)
192         {
193         dirBuilder->LazyAddEdge(jVertex, iVertex);
194         }
195       else
196         {
197         undirBuilder->LazyAddEdge(jVertex, iVertex);
198         }
199       }
200 
201     // Make sure everyone has added the edges in the random tree.
202     helper->Synchronize();
203     }
204 
205   if (this->UseEdgeProbability)
206     {
207     for (vtkIdType i = myStartVertex; i < myEndVertex; i++)
208       {
209       vtkIdType iVertex
210         = helper->MakeDistributedId(distribution.GetProcessorOfElement(i),
211                                     distribution.GetLocalIndexOfElement(i));
212       vtkIdType begin = this->Directed ? 0 : i + 1;
213       for (vtkIdType j = begin; j < this->NumberOfVertices; j++)
214         {
215         vtkIdType jVertex
216           = helper->MakeDistributedId(distribution.GetProcessorOfElement(j),
217                                       distribution.GetLocalIndexOfElement(j));
218         double r = vtkMath::Random();
219         if (r < this->EdgeProbability)
220           {
221           if (this->Directed)
222             {
223             dirBuilder->LazyAddEdge(iVertex, jVertex);
224             }
225           else
226             {
227             undirBuilder->LazyAddEdge(iVertex, jVertex);
228             }
229           }
230         }
231       }
232     }
233   else
234     {
235     vtkIdType MaxEdges;
236     if (this->AllowSelfLoops)
237       {
238       MaxEdges = this->NumberOfVertices * this->NumberOfVertices;
239       }
240     else
241       {
242       MaxEdges = (this->NumberOfVertices * (this->NumberOfVertices-1)) / 2;
243       }
244 
245     if (this->NumberOfEdges > MaxEdges)
246       {
247       this->NumberOfEdges = MaxEdges;
248       }
249 
250     vtkIdType avgNumberOfEdges = this->NumberOfEdges / numProcs;
251     vtkIdType myNumberOfEdges = avgNumberOfEdges;
252     if (myRank < this->NumberOfEdges % numProcs)
253       {
254       ++myNumberOfEdges;
255       }
256 
257     for (vtkIdType i = 0; i < myNumberOfEdges; i++)
258       {
259       bool newEdgeFound = false;
260       while (!newEdgeFound)
261         {
262         vtkIdType s;
263         vtkIdType t;
264 
265         if (this->AllowBalancedEdgeDistribution)
266           {
267           s = static_cast<vtkIdType>(vtkMath::Random(myStartVertex,
268                                                      myEndVertex));
269           }
270         else
271           {
272           s = static_cast<vtkIdType>(vtkMath::Random(0,
273                                                      this->NumberOfVertices));
274           }
275         t = static_cast<vtkIdType>(vtkMath::Random(0, this->NumberOfVertices));
276         if (s == t && (!this->AllowSelfLoops))
277           {
278           continue;
279           }
280 
281       vtkIdType sVertex
282         = helper->MakeDistributedId(distribution.GetProcessorOfElement(s),
283                                     distribution.GetLocalIndexOfElement(s));
284       vtkIdType tVertex
285         = helper->MakeDistributedId(distribution.GetProcessorOfElement(t),
286                                     distribution.GetLocalIndexOfElement(t));
287 
288         vtkDebugMacro(<<"Adding edge " << s << " to " << t);
289         if (this->Directed)
290           {
291           dirBuilder->LazyAddEdge(sVertex, tVertex);
292           }
293         else
294           {
295           undirBuilder->LazyAddEdge(sVertex, tVertex);
296           }
297         newEdgeFound = true;
298         }
299       }
300     }
301 
302   // Make sure everybody has added their edges and back-edges.
303   helper->Synchronize();
304 
305   // Copy the structure into the output.
306   vtkGraph *output = vtkGraph::GetData(outputVector);
307   if (this->Directed)
308     {
309     if (!output->CheckedShallowCopy(dirBuilder))
310       {
311       vtkErrorMacro(<<"Invalid structure.");
312       return 0;
313       }
314     }
315   else
316     {
317     if (!output->CheckedShallowCopy(undirBuilder))
318       {
319       vtkErrorMacro(<<"Invalid structure.");
320       return 0;
321       }
322     }
323 
324   if (this->IncludeEdgeWeights)
325     {
326     if (!this->EdgeWeightArrayName)
327       {
328       vtkErrorMacro("When generating edge weights, "
329         << "edge weights array name must be defined.");
330       return 0;
331       }
332     vtkFloatArray *weights = vtkFloatArray::New();
333     weights->SetName(this->EdgeWeightArrayName);
334     for (vtkIdType i = 0; i < output->GetNumberOfEdges(); ++i)
335       {
336       weights->InsertNextValue(vtkMath::Random());
337       }
338     output->GetEdgeData()->AddArray(weights);
339     weights->Delete();
340     }
341 
342   if (this->GeneratePedigreeIds)
343     {
344     if (!this->VertexPedigreeIdArrayName || !this->EdgePedigreeIdArrayName)
345       {
346       vtkErrorMacro("When generating pedigree ids, "
347         << "vertex and edge pedigree id array names must be defined.");
348       return 0;
349       }
350     vtkIdType numVert = output->GetNumberOfVertices();
351     vtkSmartPointer<vtkIdTypeArray> vertIds =
352       vtkSmartPointer<vtkIdTypeArray>::New();
353     vertIds->SetName(this->VertexPedigreeIdArrayName);
354     vertIds->SetNumberOfTuples(numVert);
355     for (vtkIdType i = 0; i < numVert; ++i)
356       {
357       vertIds->SetValue(i, myStartVertex + i);
358       }
359     output->GetVertexData()->SetPedigreeIds(vertIds);
360 
361     // Attach a distribution function to the helper that maps these
362     // global vertex numbers back to .  TODO: Actually do it :)
363 
364     // Figure out how many edges come before us in the graph.
365     boost::mpi::communicator world;
366     vtkIdType myStartEdge
367       = boost::mpi::scan(world, output->GetNumberOfEdges(),
368                          std::plus<vtkIdType>());
369 
370     vtkIdType numEdge = output->GetNumberOfEdges();
371     vtkSmartPointer<vtkIdTypeArray> edgeIds =
372       vtkSmartPointer<vtkIdTypeArray>::New();
373     edgeIds->SetName(this->EdgePedigreeIdArrayName);
374     edgeIds->SetNumberOfTuples(numEdge);
375     for (vtkIdType i = 0; i < numEdge; ++i)
376       {
377       edgeIds->SetValue(i, myStartEdge + i);
378       }
379     output->GetEdgeData()->SetPedigreeIds(edgeIds);
380     }
381 
382   return 1;
383 }
384 
385 //----------------------------------------------------------------------------
RequestDataObject(vtkInformation *,vtkInformationVector **,vtkInformationVector *)386 int vtkPBGLRandomGraphSource::RequestDataObject(
387   vtkInformation*,
388   vtkInformationVector**,
389   vtkInformationVector* )
390 {
391   vtkDataObject *current = this->GetExecutive()->GetOutputData(0);
392   if (!current
393     || (this->Directed && !vtkDirectedGraph::SafeDownCast(current))
394     || (!this->Directed && vtkDirectedGraph::SafeDownCast(current)))
395     {
396     vtkGraph *output = 0;
397     if (this->Directed)
398       {
399       output = vtkDirectedGraph::New();
400       }
401     else
402       {
403       output = vtkUndirectedGraph::New();
404       }
405 
406     this->GetExecutive()->SetOutputData(0, output);
407     output->Delete();
408     }
409 
410   return 1;
411 }
412 
413 #endif //VTK_LEGACY_REMOVE
414