1 /*========================================================================= 2 3 Program: Visualization Toolkit 4 Module: vtkGraph.h 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 /** 21 * @class vtkGraph 22 * @brief Base class for graph data types. 23 * 24 * 25 * vtkGraph is the abstract base class that provides all read-only API for graph 26 * data types. A graph consists of a collection of vertices and a 27 * collection of edges connecting pairs of vertices. The vtkDirectedGraph 28 * subclass represents a graph whose edges have inherent order from source 29 * vertex to target vertex, while vtkUndirectedGraph is a graph whose edges 30 * have no inherent ordering. 31 * 32 * Graph vertices may be traversed in two ways. In the current implementation, 33 * all vertices are assigned consecutive ids starting at zero, so they may 34 * be traversed in a simple for loop from 0 to graph->GetNumberOfVertices() - 1. 35 * You may alternately create a vtkVertexListIterator and call graph->GetVertices(it). 36 * it->Next() will return the id of the next vertex, while it->HasNext() indicates 37 * whether there are more vertices in the graph. 38 * This is the preferred method, since in the future graphs may support filtering 39 * or subsetting where the vertex ids may not be contiguous. 40 * 41 * Graph edges must be traversed through iterators. To traverse all edges 42 * in a graph, create an instance of vtkEdgeListIterator and call graph->GetEdges(it). 43 * it->Next() returns lightweight vtkEdgeType structures, which contain the public 44 * fields Id, Source and Target. Id is the identifier for the edge, which may 45 * be used to look up values in assiciated edge data arrays. Source and Target 46 * store the ids of the source and target vertices of the edge. Note that the 47 * edge list iterator DOES NOT necessarily iterate over edges in order of ascending 48 * id. To traverse edges from wrapper code (Python, Java), use 49 * it->NextGraphEdge() instead of it->Next(). This will return a heavyweight, 50 * wrappable vtkGraphEdge object, which has the same fields as vtkEdgeType 51 * accessible through getter methods. 52 * 53 * To traverse all edges outgoing from a vertex, create a vtkOutEdgeIterator and 54 * call graph->GetOutEdges(v, it). it->Next() returns a lightweight vtkOutEdgeType 55 * containing the fields Id and Target. The source of the edge is always the 56 * vertex that was passed as an argument to GetOutEdges(). 57 * Incoming edges may be similarly traversed with vtkInEdgeIterator, which returns 58 * vtkInEdgeType structures with Id and Source fields. 59 * Both vtkOutEdgeIterator and vtkInEdgeIterator also provide the wrapper functions 60 * NextGraphEdge() which return vtkGraphEdge objects. 61 * 62 * An additional iterator, vtkAdjacentVertexIterator can traverse outgoing vertices 63 * directly, instead needing to parse through edges. Initialize the iterator by 64 * calling graph->GetAdjacentVertices(v, it). 65 * 66 * vtkGraph has two instances of vtkDataSetAttributes for associated 67 * vertex and edge data. It also has a vtkPoints instance which may store 68 * x,y,z locations for each vertex. This is populated by filters such as 69 * vtkGraphLayout and vtkAssignCoordinates. 70 * 71 * All graph types share the same implementation, so the structure of one 72 * may be shared among multiple graphs, even graphs of different types. 73 * Structures from vtkUndirectedGraph and vtkMutableUndirectedGraph may be 74 * shared directly. Structures from vtkDirectedGraph, vtkMutableDirectedGraph, 75 * and vtkTree may be shared directly with the exception that setting a 76 * structure to a tree requires that a "is a tree" test passes. 77 * 78 * For graph types that are known to be compatible, calling ShallowCopy() 79 * or DeepCopy() will work as expected. When the outcome of a conversion 80 * is unknown (i.e. setting a graph to a tree), CheckedShallowCopy() and 81 * CheckedDeepCopy() exist which are identical to ShallowCopy() and DeepCopy(), 82 * except that instead of emitting an error for an incompatible structure, 83 * the function returns false. This allows you to programmatically check 84 * structure compatibility without causing error messages. 85 * 86 * To construct a graph, use vtkMutableDirectedGraph or 87 * vtkMutableUndirectedGraph. You may then use CheckedShallowCopy 88 * to set the contents of a mutable graph type into one of the non-mutable 89 * types vtkDirectedGraph, vtkUndirectedGraph. 90 * To construct a tree, use vtkMutableDirectedGraph, with directed edges 91 * which point from the parent to the child, then use CheckedShallowCopy 92 * to set the structure to a vtkTree. 93 * 94 * @warning 95 * All copy operations implement copy-on-write. The structures are initially 96 * shared, but if one of the graphs is modified, the structure is copied 97 * so that to the user they function as if they were deep copied. This means 98 * that care must be taken if different threads are accessing different graph 99 * instances that share the same structure. Race conditions may develop if 100 * one thread is modifying the graph at the same time that another graph is 101 * copying the structure. 102 * 103 * @par Vertex pedigree IDs: 104 * The vertices in a vtkGraph can be associated with pedigree IDs 105 * through GetVertexData()->SetPedigreeIds. In this case, there is a 106 * 1-1 mapping between pedigree Ids and vertices. One can query the 107 * vertex ID based on the pedigree ID using FindVertex, add new 108 * vertices by pedigree ID with AddVertex, and add edges based on the 109 * pedigree IDs of the source and target vertices. For example, 110 * AddEdge("Here", "There") will find (or add) vertices with pedigree 111 * ID "Here" and "There" and then introduce an edge from "Here" to 112 * "There". 113 * 114 * @par Vertex pedigree IDs: 115 * To configure the vtkGraph with a pedigree ID mapping, create a 116 * vtkDataArray that will store the pedigree IDs and set that array as 117 * the pedigree ID array for the vertices via 118 * GetVertexData()->SetPedigreeIds(). 119 * 120 * 121 * @par Distributed graphs: 122 * vtkGraph instances can be distributed across multiple machines, to 123 * allow the construction and manipulation of graphs larger than a 124 * single machine could handle. A distributed graph will typically be 125 * distributed across many different nodes within a cluster, using the 126 * Message Passing Interface (MPI) to allow those cluster nodes to 127 * communicate. 128 * 129 * @par Distributed graphs: 130 * An empty vtkGraph can be made into a distributed graph by attaching 131 * an instance of a vtkDistributedGraphHelper via the 132 * SetDistributedGraphHelper() method. To determine whether a graph is 133 * distributed or not, call GetDistributedGraphHelper() and check 134 * whether the result is non-nullptr. For a distributed graph, the number 135 * of processors across which the graph is distributed can be 136 * retrieved by extracting the value for the DATA_NUMBER_OF_PIECES key 137 * in the vtkInformation object (retrieved by GetInformation()) 138 * associated with the graph. Similarly, the value corresponding to 139 * the DATA_PIECE_NUMBER key of the vtkInformation object describes 140 * which piece of the data this graph instance provides. 141 * 142 * @par Distributed graphs: 143 * Distributed graphs behave somewhat differently from non-distributed 144 * graphs, and will require special care. In a distributed graph, each 145 * of the processors will contain a subset of the vertices in the 146 * graph. That subset of vertices can be accessed via the 147 * vtkVertexListIterator produced by GetVertices(). 148 * GetNumberOfVertices(), therefore, returns the number of vertices 149 * stored locally: it does not account for vertices stored on other 150 * processors. A vertex (or edge) is identified by both the rank of 151 * its owning processor and by its index within that processor, both 152 * of which are encoded within the vtkIdType value that describes that 153 * vertex (or edge). The owning processor is a value between 0 and 154 * P-1, where P is the number of processors across which the vtkGraph 155 * has been distributed. The local index will be a value between 0 and 156 * GetNumberOfVertices(), for vertices, or GetNumberOfEdges(), for 157 * edges, and can be used to access the local parts of distributed 158 * data arrays. When given a vtkIdType identifying a vertex, one can 159 * determine the owner of the vertex with 160 * vtkDistributedGraphHelper::GetVertexOwner() and the local index 161 * with vtkDistributedGraphHelper::GetVertexIndex(). With edges, the 162 * appropriate methods are vtkDistributedGraphHelper::GetEdgeOwner() 163 * and vtkDistributedGraphHelper::GetEdgeIndex(), respectively. To 164 * construct a vtkIdType representing either a vertex or edge given 165 * only its owner and local index, use 166 * vtkDistributedGraphHelper::MakeDistributedId(). 167 * 168 * @par Distributed graphs: 169 * The edges in a distributed graph are always stored on the 170 * processors that own the vertices named by the edge. For example, 171 * given a directed edge (u, v), the edge will be stored in the 172 * out-edges list for vertex u on the processor that owns u, and in 173 * the in-edges list for vertex v on the processor that owns v. This 174 * "row-wise" decomposition of the graph means that, for any vertex 175 * that is local to a processor, that processor can look at all of the 176 * incoming and outgoing edges of the graph. Processors cannot, 177 * however, access the incoming or outgoing edge lists of vertex owned 178 * by other processors. Vertices owned by other processors will not be 179 * encountered when traversing the vertex list via GetVertices(), but 180 * may be encountered by traversing the in- and out-edge lists of 181 * local vertices or the edge list. 182 * 183 * @par Distributed graphs: 184 * Distributed graphs can have pedigree IDs for the vertices in the 185 * same way that non-distributed graphs can. In this case, the 186 * distribution of the vertices in the graph is based on pedigree 187 * ID. For example, a vertex with the pedigree ID "Here" might land on 188 * processor 0 while a vertex pedigree ID "There" would end up on 189 * processor 3. By default, the pedigree IDs themselves are hashed to 190 * give a random (and, hopefully, even) distribution of the 191 * vertices. However, one can provide a different vertex distribution 192 * function by calling 193 * vtkDistributedGraphHelper::SetVertexPedigreeIdDistribution. Once a 194 * distributed graph has pedigree IDs, the no-argument AddVertex() 195 * method can no longer be used. Additionally, once a vertex has a 196 * pedigree ID, that pedigree ID should not be changed unless the user 197 * can guarantee that the vertex distribution will still map that 198 * vertex to the same processor where it already resides. 199 * 200 * @sa 201 * vtkDirectedGraph vtkUndirectedGraph vtkMutableDirectedGraph 202 * vtkMutableUndirectedGraph vtkTree vtkDistributedGraphHelper 203 * 204 * @par Thanks: 205 * Thanks to Brian Wylie, Timothy Shead, Ken Moreland of Sandia National 206 * Laboratories and Douglas Gregor of Indiana University for designing these 207 * classes. 208 */ 209 210 #ifndef vtkGraph_h 211 #define vtkGraph_h 212 213 #include "vtkCommonDataModelModule.h" // For export macro 214 #include "vtkDataObject.h" 215 216 class vtkAdjacentVertexIterator; 217 class vtkCellArray; 218 class vtkEdgeListIterator; 219 class vtkDataSetAttributes; 220 class vtkDirectedGraph; 221 class vtkGraphEdge; 222 class vtkGraphEdgePoints; 223 class vtkDistributedGraphHelper; 224 class vtkGraphInternals; 225 class vtkIdTypeArray; 226 class vtkInEdgeIterator; 227 class vtkOutEdgeIterator; 228 class vtkPoints; 229 class vtkUndirectedGraph; 230 class vtkVertexListIterator; 231 class vtkVariant; 232 class vtkVariantArray; 233 234 // Forward declare some boost stuff even if boost wrappers 235 // are turned off. 236 namespace boost 237 { 238 class vtk_edge_iterator; 239 class vtk_out_edge_pointer_iterator; 240 class vtk_in_edge_pointer_iterator; 241 } 242 243 // Edge structures. 244 struct vtkEdgeBase 245 { 246 vtkEdgeBase() = default; vtkEdgeBasevtkEdgeBase247 vtkEdgeBase(vtkIdType id) 248 : Id(id) 249 { 250 } 251 vtkIdType Id; 252 }; 253 254 struct vtkOutEdgeType : vtkEdgeBase 255 { 256 vtkOutEdgeType() = default; vtkOutEdgeTypevtkOutEdgeType257 vtkOutEdgeType(vtkIdType t, vtkIdType id) 258 : vtkEdgeBase(id) 259 , Target(t) 260 { 261 } 262 vtkIdType Target; 263 }; 264 265 struct vtkInEdgeType : vtkEdgeBase 266 { 267 vtkInEdgeType() = default; vtkInEdgeTypevtkInEdgeType268 vtkInEdgeType(vtkIdType s, vtkIdType id) 269 : vtkEdgeBase(id) 270 , Source(s) 271 { 272 } 273 vtkIdType Source; 274 }; 275 276 struct vtkEdgeType : vtkEdgeBase 277 { 278 vtkEdgeType() = default; vtkEdgeTypevtkEdgeType279 vtkEdgeType(vtkIdType s, vtkIdType t, vtkIdType id) 280 : vtkEdgeBase(id) 281 , Source(s) 282 , Target(t) 283 { 284 } 285 vtkIdType Source; 286 vtkIdType Target; 287 }; 288 289 class VTKCOMMONDATAMODEL_EXPORT vtkGraph : public vtkDataObject 290 { 291 public: 292 vtkTypeMacro(vtkGraph, vtkDataObject); 293 void PrintSelf(ostream& os, vtkIndent indent) override; 294 295 ///@{ 296 /** 297 * Get the vertex or edge data. 298 */ 299 vtkGetObjectMacro(VertexData, vtkDataSetAttributes); 300 vtkGetObjectMacro(EdgeData, vtkDataSetAttributes); 301 ///@} 302 303 /** 304 * Return what type of dataset this is. 305 */ GetDataObjectType()306 int GetDataObjectType() override { return VTK_GRAPH; } 307 308 /** 309 * Initialize to an empty graph. 310 */ 311 void Initialize() override; 312 313 ///@{ 314 /** 315 * These methods return the point (0,0,0) until the points structure 316 * is created, when it returns the actual point position. In a 317 * distributed graph, only the points for local vertices can be 318 * retrieved. 319 */ 320 double* GetPoint(vtkIdType ptId); 321 void GetPoint(vtkIdType ptId, double x[3]); 322 ///@} 323 324 ///@{ 325 /** 326 * Returns the points array for this graph. 327 * If points is not yet constructed, generates and returns 328 * a new points array filled with (0,0,0) coordinates. In a 329 * distributed graph, only the points for local vertices can be 330 * retrieved or modified. 331 */ 332 vtkPoints* GetPoints(); 333 virtual void SetPoints(vtkPoints* points); 334 ///@} 335 336 /** 337 * Compute the bounds of the graph. In a distributed graph, this 338 * computes the bounds around the local part of the graph. 339 */ 340 void ComputeBounds(); 341 342 ///@{ 343 /** 344 * Return a pointer to the geometry bounding box in the form 345 * (xmin,xmax, ymin,ymax, zmin,zmax). In a distributed graph, this 346 * computes the bounds around the local part of the graph. 347 */ 348 double* GetBounds(); 349 void GetBounds(double bounds[6]); 350 ///@} 351 352 /** 353 * The modified time of the graph. 354 */ 355 vtkMTimeType GetMTime() override; 356 357 /** 358 * Initializes the out edge iterator to iterate over 359 * all outgoing edges of vertex v. For an undirected graph, 360 * returns all incident edges. In a distributed graph, the vertex 361 * v must be local to this processor. 362 */ 363 virtual void GetOutEdges(vtkIdType v, vtkOutEdgeIterator* it); 364 365 /** 366 * The total of all incoming and outgoing vertices for vertex v. 367 * For undirected graphs, this is simply the number of edges incident 368 * to v. In a distributed graph, the vertex v must be local to this 369 * processor. 370 */ 371 virtual vtkIdType GetDegree(vtkIdType v); 372 373 /** 374 * The number of outgoing edges from vertex v. 375 * For undirected graphs, returns the same as GetDegree(). In a 376 * distributed graph, the vertex v must be local to this processor. 377 */ 378 virtual vtkIdType GetOutDegree(vtkIdType v); 379 380 /** 381 * Random-access method for retrieving outgoing edges from vertex v. 382 */ 383 virtual vtkOutEdgeType GetOutEdge(vtkIdType v, vtkIdType index); 384 385 /** 386 * Random-access method for retrieving outgoing edges from vertex v. 387 * The method fills the vtkGraphEdge instance with the id, source, and 388 * target of the edge. This method is provided for wrappers, 389 * GetOutEdge(vtkIdType, vtkIdType) is preferred. 390 */ 391 virtual void GetOutEdge(vtkIdType v, vtkIdType index, vtkGraphEdge* e); 392 393 /** 394 * Initializes the in edge iterator to iterate over 395 * all incoming edges to vertex v. For an undirected graph, 396 * returns all incident edges. In a distributed graph, the vertex 397 * v must be local to this processor. 398 */ 399 virtual void GetInEdges(vtkIdType v, vtkInEdgeIterator* it); 400 401 /** 402 * The number of incoming edges to vertex v. 403 * For undirected graphs, returns the same as GetDegree(). In a 404 * distributed graph, the vertex v must be local to this processor. 405 */ 406 virtual vtkIdType GetInDegree(vtkIdType v); 407 408 /** 409 * Random-access method for retrieving incoming edges to vertex v. 410 */ 411 virtual vtkInEdgeType GetInEdge(vtkIdType v, vtkIdType index); 412 413 /** 414 * Random-access method for retrieving incoming edges to vertex v. 415 * The method fills the vtkGraphEdge instance with the id, source, and 416 * target of the edge. This method is provided for wrappers, 417 * GetInEdge(vtkIdType, vtkIdType) is preferred. 418 */ 419 virtual void GetInEdge(vtkIdType v, vtkIdType index, vtkGraphEdge* e); 420 421 /** 422 * Initializes the adjacent vertex iterator to iterate over 423 * all outgoing vertices from vertex v. For an undirected graph, 424 * returns all adjacent vertices. In a distributed graph, the vertex 425 * v must be local to this processor. 426 */ 427 virtual void GetAdjacentVertices(vtkIdType v, vtkAdjacentVertexIterator* it); 428 429 /** 430 * Initializes the edge list iterator to iterate over all 431 * edges in the graph. Edges may not be traversed in order of 432 * increasing edge id. In a distributed graph, this returns edges 433 * that are stored locally. 434 */ 435 virtual void GetEdges(vtkEdgeListIterator* it); 436 437 /** 438 * The number of edges in the graph. In a distributed graph, 439 * this returns the number of edges stored locally. 440 */ 441 virtual vtkIdType GetNumberOfEdges(); 442 443 /** 444 * Initializes the vertex list iterator to iterate over all 445 * vertices in the graph. In a distributed graph, the iterator 446 * traverses all local vertices. 447 */ 448 virtual void GetVertices(vtkVertexListIterator* it); 449 450 /** 451 * The number of vertices in the graph. In a distributed graph, 452 * returns the number of local vertices in the graph. 453 */ 454 virtual vtkIdType GetNumberOfVertices(); 455 456 /** 457 * Sets the distributed graph helper of this graph, turning it into a 458 * distributed graph. This operation can only be executed on an empty 459 * graph. 460 */ 461 void SetDistributedGraphHelper(vtkDistributedGraphHelper* helper); 462 463 /** 464 * Retrieves the distributed graph helper for this graph 465 */ 466 vtkDistributedGraphHelper* GetDistributedGraphHelper(); 467 468 /** 469 * Retrieve the vertex with the given pedigree ID. If successful, 470 * returns the ID of the vertex. Otherwise, either the vertex data 471 * does not have a pedigree ID array or there is no vertex with the 472 * given pedigree ID, so this function returns -1. 473 * If the graph is a distributed graph, this method will return the 474 * Distributed-ID of the vertex. 475 */ 476 vtkIdType FindVertex(const vtkVariant& pedigreeID); 477 478 /** 479 * Shallow copies the data object into this graph. 480 * If it is an incompatible graph, reports an error. 481 */ 482 void ShallowCopy(vtkDataObject* obj) override; 483 484 /** 485 * Deep copies the data object into this graph. 486 * If it is an incompatible graph, reports an error. 487 */ 488 void DeepCopy(vtkDataObject* obj) override; 489 490 /** 491 * Does a shallow copy of the topological information, 492 * but not the associated attributes. 493 */ 494 virtual void CopyStructure(vtkGraph* g); 495 496 /** 497 * Performs the same operation as ShallowCopy(), 498 * but instead of reporting an error for an incompatible graph, 499 * returns false. 500 */ 501 virtual bool CheckedShallowCopy(vtkGraph* g); 502 503 /** 504 * Performs the same operation as DeepCopy(), 505 * but instead of reporting an error for an incompatible graph, 506 * returns false. 507 */ 508 virtual bool CheckedDeepCopy(vtkGraph* g); 509 510 /** 511 * Reclaim unused memory. 512 */ 513 virtual void Squeeze(); 514 515 /** 516 * Return the actual size of the data in kibibytes (1024 bytes). This number 517 * is valid only after the pipeline has updated. The memory size 518 * returned is guaranteed to be greater than or equal to the 519 * memory required to represent the data (e.g., extra space in 520 * arrays, etc. are not included in the return value). 521 */ 522 unsigned long GetActualMemorySize() override; 523 524 ///@{ 525 /** 526 * Retrieve a graph from an information vector. 527 */ 528 static vtkGraph* GetData(vtkInformation* info); 529 static vtkGraph* GetData(vtkInformationVector* v, int i = 0); 530 ///@} 531 532 /** 533 * Reorder the outgoing vertices of a vertex. 534 * The vertex list must have the same elements as the current out edge 535 * list, just in a different order. 536 * This method does not change the topology of the graph. 537 * In a distributed graph, the vertex v must be local. 538 */ 539 void ReorderOutVertices(vtkIdType v, vtkIdTypeArray* vertices); 540 541 /** 542 * Returns true if both graphs point to the same adjacency structure. 543 * Can be used to test the copy-on-write feature of the graph. 544 */ 545 bool IsSameStructure(vtkGraph* other); 546 547 ///@{ 548 /** 549 * Retrieve the source and target vertices for an edge id. 550 * NOTE: The first time this is called, the graph will build 551 * a mapping array from edge id to source/target that is the 552 * same size as the number of edges in the graph. If you have 553 * access to a vtkOutEdgeType, vtkInEdgeType, vtkEdgeType, or 554 * vtkGraphEdge, you should directly use these structures 555 * to look up the source or target instead of this method. 556 */ 557 vtkIdType GetSourceVertex(vtkIdType e); 558 vtkIdType GetTargetVertex(vtkIdType e); 559 ///@} 560 561 ///@{ 562 /** 563 * Get/Set the internal edge control points associated with each edge. 564 * The size of the pts array is 3*npts, and holds the x,y,z 565 * location of each edge control point. 566 */ 567 void SetEdgePoints(vtkIdType e, vtkIdType npts, const double pts[]) VTK_SIZEHINT(pts, 3 * npts); 568 void GetEdgePoints(vtkIdType e, vtkIdType& npts, double*& pts) VTK_SIZEHINT(pts, 3 * npts); 569 ///@} 570 571 /** 572 * Get the number of edge points associated with an edge. 573 */ 574 vtkIdType GetNumberOfEdgePoints(vtkIdType e); 575 576 /** 577 * Get the x,y,z location of a point along edge e. 578 */ 579 double* GetEdgePoint(vtkIdType e, vtkIdType i) VTK_SIZEHINT(3); 580 581 /** 582 * Clear all points associated with an edge. 583 */ 584 void ClearEdgePoints(vtkIdType e); 585 586 /** 587 * Set an x,y,z location of a point along an edge. 588 * This assumes there is already a point at location i, and simply 589 * overwrites it. 590 */ 591 void SetEdgePoint(vtkIdType e, vtkIdType i, const double x[3]); SetEdgePoint(vtkIdType e,vtkIdType i,double x,double y,double z)592 void SetEdgePoint(vtkIdType e, vtkIdType i, double x, double y, double z) 593 { 594 double p[3] = { x, y, z }; 595 this->SetEdgePoint(e, i, p); 596 } 597 598 /** 599 * Adds a point to the end of the list of edge points for a certain edge. 600 */ 601 void AddEdgePoint(vtkIdType e, const double x[3]); AddEdgePoint(vtkIdType e,double x,double y,double z)602 void AddEdgePoint(vtkIdType e, double x, double y, double z) 603 { 604 double p[3] = { x, y, z }; 605 this->AddEdgePoint(e, p); 606 } 607 608 ///@{ 609 /** 610 * Copy the internal edge point data from another graph into this graph. 611 * Both graphs must have the same number of edges. 612 */ 613 void ShallowCopyEdgePoints(vtkGraph* g); 614 void DeepCopyEdgePoints(vtkGraph* g); 615 ///@} 616 617 /** 618 * Returns the internal representation of the graph. If modifying is 619 * true, then the returned vtkGraphInternals object will be unique to 620 * this vtkGraph object. 621 */ 622 vtkGraphInternals* GetGraphInternals(bool modifying); 623 624 /** 625 * Fills a list of edge indices with the edges contained in the induced 626 * subgraph formed by the vertices in the vertex list. 627 */ 628 void GetInducedEdges(vtkIdTypeArray* verts, vtkIdTypeArray* edges); 629 630 /** 631 * Returns the attributes of the data object as a vtkFieldData. 632 * This returns non-null values in all the same cases as GetAttributes, 633 * in addition to the case of FIELD, which will return the field data 634 * for any vtkDataObject subclass. 635 */ 636 vtkFieldData* GetAttributesAsFieldData(int type) override; 637 638 /** 639 * Get the number of elements for a specific attribute type (VERTEX, EDGE, etc.). 640 */ 641 vtkIdType GetNumberOfElements(int type) override; 642 643 /** 644 * Dump the contents of the graph to standard output. 645 */ 646 void Dump(); 647 648 /** 649 * Returns the Id of the edge between vertex a and vertex b. 650 * This is independent of directionality of the edge, that is, 651 * if edge A->B exists or if edge B->A exists, this function will 652 * return its Id. If multiple edges exist between a and b, here is no guarantee 653 * about which one will be returned. 654 * Returns -1 if no edge exists between a and b. 655 */ 656 vtkIdType GetEdgeId(vtkIdType a, vtkIdType b); 657 658 /** 659 * Convert the graph to a directed graph. 660 */ 661 bool ToDirectedGraph(vtkDirectedGraph* g); 662 663 /** 664 * Convert the graph to an undirected graph. 665 */ 666 bool ToUndirectedGraph(vtkUndirectedGraph* g); 667 668 protected: 669 vtkGraph(); 670 ~vtkGraph() override; 671 672 /** 673 * Protected method for adding vertices, optionally with properties, 674 * used by mutable subclasses. If vertex is non-null, it will be set 675 * to the newly-added (or found) vertex. Note that if propertyArr is 676 * non-null and the vertex data contains pedigree IDs, a vertex will 677 * only be added if there is no vertex with that pedigree ID. 678 */ 679 void AddVertexInternal(vtkVariantArray* propertyArr = nullptr, vtkIdType* vertex = nullptr); 680 681 /** 682 * Adds a vertex with the given pedigree ID to the graph. If a vertex with 683 * this pedigree ID already exists, no new vertex is added, but the vertex 684 * argument is set to the ID of the existing vertex. Otherwise, a 685 * new vertex is added and its ID is provided. 686 */ 687 void AddVertexInternal(const vtkVariant& pedigree, vtkIdType* vertex); 688 689 ///@{ 690 /** 691 * Protected method for adding edges of a certain directedness used 692 * by mutable subclasses. If propertyArr is non-null, it specifies 693 * the properties to be attached to the newly-created edge. If 694 * non-null, edge will receive the newly-added edge. 695 */ 696 void AddEdgeInternal( 697 vtkIdType u, vtkIdType v, bool directed, vtkVariantArray* propertyArr, vtkEdgeType* edge); 698 void AddEdgeInternal(const vtkVariant& uPedigree, vtkIdType v, bool directed, 699 vtkVariantArray* propertyArr, vtkEdgeType* edge); 700 void AddEdgeInternal(vtkIdType u, const vtkVariant& vPedigree, bool directed, 701 vtkVariantArray* propertyArr, vtkEdgeType* edge); 702 void AddEdgeInternal(const vtkVariant& uPedigree, const vtkVariant& vPedigree, bool directed, 703 vtkVariantArray* propertyArr, vtkEdgeType* edge); 704 ///@} 705 706 /** 707 * Removes a vertex from the graph, along with any adjacent edges. 708 * This invalidates the id of the last vertex, since it is reassigned to v. 709 */ 710 void RemoveVertexInternal(vtkIdType v, bool directed); 711 712 /** 713 * Removes an edge from the graph. 714 * This invalidates the id of the last edge, since it is reassigned to e. 715 */ 716 void RemoveEdgeInternal(vtkIdType e, bool directed); 717 718 /** 719 * Removes a collection of vertices from the graph, along with any adjacent edges. 720 */ 721 void RemoveVerticesInternal(vtkIdTypeArray* arr, bool directed); 722 723 /** 724 * Removes a collection of edges from the graph. 725 */ 726 void RemoveEdgesInternal(vtkIdTypeArray* arr, bool directed); 727 728 /** 729 * Subclasses override this method to accept the structure 730 * based on their requirements. 731 */ 732 virtual bool IsStructureValid(vtkGraph* g) = 0; 733 734 /** 735 * Copy internal data structure. 736 */ 737 virtual void CopyInternal(vtkGraph* g, bool deep); 738 739 /** 740 * The adjacency list internals of this graph. 741 */ 742 vtkGraphInternals* Internals; 743 744 /** 745 * The distributed graph helper. Only non-nullptr for distributed graphs. 746 */ 747 vtkDistributedGraphHelper* DistributedHelper; 748 749 /** 750 * Private method for setting internals. 751 */ 752 void SetInternals(vtkGraphInternals* internals); 753 754 /** 755 * The structure for holding the edge points. 756 */ 757 vtkGraphEdgePoints* EdgePoints; 758 759 /** 760 * Private method for setting edge points. 761 */ 762 void SetEdgePoints(vtkGraphEdgePoints* edgePoints); 763 764 /** 765 * If this instance does not own its internals, it makes a copy of the 766 * internals. This is called before any write operation. 767 */ 768 void ForceOwnership(); 769 770 ///@{ 771 /** 772 * Fast access functions for iterators. 773 */ 774 virtual void GetOutEdges(vtkIdType v, const vtkOutEdgeType*& edges, vtkIdType& nedges); 775 virtual void GetInEdges(vtkIdType v, const vtkInEdgeType*& edges, vtkIdType& nedges); 776 ///@} 777 778 /** 779 * Builds a mapping from edge id to source/target vertex id. 780 */ 781 void BuildEdgeList(); 782 783 ///@{ 784 /** 785 * Friend iterator classes. 786 */ 787 friend class vtkAdjacentVertexIterator; 788 friend class vtkEdgeListIterator; 789 friend class vtkInEdgeIterator; 790 friend class vtkOutEdgeIterator; 791 friend class boost::vtk_edge_iterator; 792 friend class boost::vtk_in_edge_pointer_iterator; 793 friend class boost::vtk_out_edge_pointer_iterator; 794 ///@} 795 796 ///@{ 797 /** 798 * The vertex and edge data. 799 */ 800 vtkDataSetAttributes* VertexData; 801 vtkDataSetAttributes* EdgeData; 802 ///@} 803 804 /** 805 * (xmin,xmax, ymin,ymax, zmin,zmax) geometric bounds. 806 */ 807 double Bounds[6]; 808 809 /** 810 * Time at which bounds were computed. 811 */ 812 vtkTimeStamp ComputeTime; 813 814 ///@{ 815 /** 816 * The vertex locations. 817 */ 818 vtkPoints* Points; 819 static double DefaultPoint[3]; 820 ///@} 821 822 ///@{ 823 /** 824 * The optional mapping from edge id to source/target ids. 825 */ 826 vtkGetObjectMacro(EdgeList, vtkIdTypeArray); 827 virtual void SetEdgeList(vtkIdTypeArray* list); 828 vtkIdTypeArray* EdgeList; 829 ///@} 830 831 private: 832 vtkGraph(const vtkGraph&) = delete; 833 void operator=(const vtkGraph&) = delete; 834 }; 835 836 bool VTKCOMMONDATAMODEL_EXPORT operator==(vtkEdgeBase e1, vtkEdgeBase e2); 837 bool VTKCOMMONDATAMODEL_EXPORT operator!=(vtkEdgeBase e1, vtkEdgeBase e2); 838 VTKCOMMONDATAMODEL_EXPORT ostream& operator<<(ostream& out, vtkEdgeBase e); 839 840 #endif 841