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