You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
276 lines
10 KiB
C++
276 lines
10 KiB
C++
/*=========================================================================
|
|
|
|
Program: Visualization Toolkit
|
|
Module: vtkDistributedGraphHelper.h
|
|
|
|
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
|
|
All rights reserved.
|
|
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
|
|
|
|
This software is distributed WITHOUT ANY WARRANTY; without even
|
|
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
|
|
PURPOSE. See the above copyright notice for more information.
|
|
|
|
=========================================================================*/
|
|
/*
|
|
* Copyright (C) 2008 The Trustees of Indiana University.
|
|
* Use, modification and distribution is subject to the Boost Software
|
|
* License, Version 1.0. (See http://www.boost.org/LICENSE_1_0.txt)
|
|
*/
|
|
|
|
/**
|
|
* @class vtkDistributedGraphHelper
|
|
* @brief helper for the vtkGraph class
|
|
* that allows the graph to be distributed across multiple memory spaces.
|
|
*
|
|
*
|
|
* A distributed graph helper can be attached to an empty vtkGraph
|
|
* object to turn the vtkGraph into a distributed graph, whose
|
|
* vertices and edges are distributed across several different
|
|
* processors. vtkDistributedGraphHelper is an abstract class. Use a
|
|
* subclass of vtkDistributedGraphHelper, such as
|
|
* vtkPBGLDistributedGraphHelper, to build distributed graphs.
|
|
*
|
|
* The distributed graph helper provides facilities used by vtkGraph
|
|
* to communicate with other processors that store other parts of the
|
|
* same distributed graph. The only user-level functionality provided
|
|
* by vtkDistributedGraphHelper involves this communication among
|
|
* processors and the ability to map between "distributed" vertex and
|
|
* edge IDs and their component parts (processor and local index). For
|
|
* example, the Synchronize() method provides a barrier that allows
|
|
* all processors to catch up to the same point in the code before any
|
|
* processor can leave that Synchronize() call. For example, one would
|
|
* call Synchronize() after adding many edges to a distributed graph,
|
|
* so that all processors can handle the addition of inter-processor
|
|
* edges and continue, after the Synchronize() call, with a consistent
|
|
* view of the distributed graph. For more information about
|
|
* manipulating (distributed) graphs, see the vtkGraph documentation.
|
|
*
|
|
* @sa
|
|
* vtkGraph
|
|
*/
|
|
|
|
#ifndef vtkDistributedGraphHelper_h
|
|
#define vtkDistributedGraphHelper_h
|
|
|
|
#include "vtkCommonDataModelModule.h" // For export macro
|
|
#include "vtkObject.h"
|
|
|
|
class vtkDistributedGraphHelperInternals;
|
|
struct vtkEdgeType;
|
|
class vtkGraph;
|
|
class vtkVariant;
|
|
class vtkVariantArray;
|
|
class vtkInformationIntegerKey;
|
|
|
|
// .NAME vtkVertexPedigreeIdDistributionFunction - The type of a
|
|
// function used to determine how to distribute vertex pedigree IDs
|
|
// across processors in a vtkGraph. The pedigree ID distribution
|
|
// function takes the pedigree ID of the vertex and a user-supplied
|
|
// void pointer and returns a hash value V. A vertex with that
|
|
// pedigree ID will reside on processor V % P, where P is the number
|
|
// of processors. This type is used in conjunction with the
|
|
// vtkDistributedGraphHelper class.
|
|
typedef vtkIdType (*vtkVertexPedigreeIdDistribution)(const vtkVariant& pedigreeId, void* userData);
|
|
|
|
class VTKCOMMONDATAMODEL_EXPORT vtkDistributedGraphHelper : public vtkObject
|
|
{
|
|
public:
|
|
vtkTypeMacro(vtkDistributedGraphHelper, vtkObject);
|
|
void PrintSelf(ostream& os, vtkIndent indent) override;
|
|
|
|
/**
|
|
* Returns owner of vertex v, by extracting top ceil(log2 P) bits of v.
|
|
*/
|
|
vtkIdType GetVertexOwner(vtkIdType v) const;
|
|
|
|
/**
|
|
* Returns local index of vertex v, by masking off top ceil(log2 P) bits of v.
|
|
*/
|
|
vtkIdType GetVertexIndex(vtkIdType v) const;
|
|
|
|
/**
|
|
* Returns owner of edge with ID e_id, by extracting top ceil(log2 P) bits of e_id.
|
|
*/
|
|
vtkIdType GetEdgeOwner(vtkIdType e_id) const;
|
|
|
|
/**
|
|
* Returns local index of edge with ID e_id, by masking off top ceil(log2 P)
|
|
* bits of e_id.
|
|
*/
|
|
vtkIdType GetEdgeIndex(vtkIdType e_id) const;
|
|
|
|
/**
|
|
* Builds a distributed ID consisting of the given owner and the local ID.
|
|
*/
|
|
vtkIdType MakeDistributedId(int owner, vtkIdType local);
|
|
|
|
/**
|
|
* Set the pedigreeId -> processor distribution function that determines
|
|
* how vertices are distributed when they are associated with
|
|
* pedigree ID, which must be a unique label such as a URL or IP
|
|
* address. If a nullptr function pointer is provided, the default
|
|
* hashed distribution will be used.
|
|
*/
|
|
void SetVertexPedigreeIdDistribution(vtkVertexPedigreeIdDistribution Func, void* userData);
|
|
|
|
/**
|
|
* Determine which processor owns the vertex with the given pedigree ID.
|
|
*/
|
|
vtkIdType GetVertexOwnerByPedigreeId(const vtkVariant& pedigreeId);
|
|
|
|
/**
|
|
* Synchronizes all of the processors involved in this distributed
|
|
* graph, so that all processors have a consistent view of the
|
|
* distributed graph for the computation that follows. This routine
|
|
* should be invoked after adding new edges into the distributed
|
|
* graph, so that other processors will see those edges (or their
|
|
* corresponding back-edges).
|
|
*/
|
|
virtual void Synchronize() = 0;
|
|
|
|
/**
|
|
* Clones the distributed graph helper, returning another
|
|
* distributed graph helper of the same kind that can be used in
|
|
* another vtkGraph.
|
|
*/
|
|
virtual vtkDistributedGraphHelper* Clone() = 0;
|
|
|
|
//@{
|
|
/**
|
|
* Information Keys that distributed graphs can append to attribute arrays
|
|
* to flag them as containing distributed IDs. These can be used to let
|
|
* routines that migrate vertices (either repartitioning or collecting graphs
|
|
* to single nodes) to also modify the ids contained in the attribute arrays
|
|
* to maintain consistency.
|
|
*/
|
|
static vtkInformationIntegerKey* DISTRIBUTEDVERTEXIDS();
|
|
static vtkInformationIntegerKey* DISTRIBUTEDEDGEIDS();
|
|
//@}
|
|
|
|
protected:
|
|
vtkDistributedGraphHelper();
|
|
~vtkDistributedGraphHelper() override;
|
|
|
|
/**
|
|
* Add a vertex, optionally with properties, to the distributed graph.
|
|
* If vertex is non-nullptr, it will be set
|
|
* to the newly-added (or found) vertex. Note that if propertyArr is
|
|
* non-nullptr and the vertex data contains pedigree IDs, a vertex will
|
|
* only be added if there is no vertex with that pedigree ID.
|
|
*/
|
|
virtual void AddVertexInternal(vtkVariantArray* propertyArr, vtkIdType* vertex) = 0;
|
|
|
|
/**
|
|
* Add a vertex with the given pedigreeId to the distributed graph. If
|
|
* vertex is non-nullptr, it will receive the newly-created vertex.
|
|
*/
|
|
virtual void AddVertexInternal(const vtkVariant& pedigreeId, vtkIdType* vertex) = 0;
|
|
|
|
/**
|
|
* Add an edge (u, v) to the distributed graph. The edge may be directed
|
|
* undirected. If edge is non-null, it will receive the newly-created edge.
|
|
* If propertyArr is non-null, it specifies the properties that will be
|
|
* attached to the newly-created edge.
|
|
*/
|
|
virtual void AddEdgeInternal(
|
|
vtkIdType u, vtkIdType v, bool directed, vtkVariantArray* propertyArr, vtkEdgeType* edge) = 0;
|
|
|
|
/**
|
|
* Adds an edge (u, v) and returns the new edge. The graph edge may
|
|
* or may not be directed, depending on the given flag. If edge is
|
|
* non-null, it will receive the newly-created edge. uPedigreeId is
|
|
* the pedigree ID of vertex u, which will be added if no vertex by
|
|
* that pedigree ID exists. If propertyArr is non-null, it specifies
|
|
* the properties that will be attached to the newly-created edge.
|
|
*/
|
|
virtual void AddEdgeInternal(const vtkVariant& uPedigreeId, vtkIdType v, bool directed,
|
|
vtkVariantArray* propertyArr, vtkEdgeType* edge) = 0;
|
|
|
|
/**
|
|
* Adds an edge (u, v) and returns the new edge. The graph edge may
|
|
* or may not be directed, depending on the given flag. If edge is
|
|
* non-null, it will receive the newly-created edge. vPedigreeId is
|
|
* the pedigree ID of vertex u, which will be added if no vertex
|
|
* with that pedigree ID exists. If propertyArr is non-null, it specifies
|
|
* the properties that will be attached to the newly-created edge.
|
|
*/
|
|
virtual void AddEdgeInternal(vtkIdType u, const vtkVariant& vPedigreeId, bool directed,
|
|
vtkVariantArray* propertyArr, vtkEdgeType* edge) = 0;
|
|
|
|
/**
|
|
* Adds an edge (u, v) and returns the new edge. The graph edge may
|
|
* or may not be directed, depending on the given flag. If edge is
|
|
* non-null, it will receive the newly-created edge. uPedigreeId is
|
|
* the pedigree ID of vertex u and vPedigreeId is the pedigree ID of
|
|
* vertex u, each of which will be added if no vertex by that
|
|
* pedigree ID exists. If propertyArr is non-null, it specifies
|
|
* the properties that will be attached to the newly-created edge.
|
|
*/
|
|
virtual void AddEdgeInternal(const vtkVariant& uPedigreeId, const vtkVariant& vPedigreeId,
|
|
bool directed, vtkVariantArray* propertyArr, vtkEdgeType* edge) = 0;
|
|
|
|
/**
|
|
* Try to find the vertex with the given pedigree ID. Returns the
|
|
* vertex ID if the vertex is found, or -1 if there is no vertex
|
|
* with that pedigree ID.
|
|
*/
|
|
virtual vtkIdType FindVertex(const vtkVariant& pedigreeId) = 0;
|
|
|
|
/**
|
|
* Determine the source and target of the edge with the given
|
|
* ID. Used internally by vtkGraph::GetSourceVertex and
|
|
* vtkGraph::GetTargetVertex.
|
|
*/
|
|
virtual void FindEdgeSourceAndTarget(vtkIdType id, vtkIdType* source, vtkIdType* target) = 0;
|
|
|
|
/**
|
|
* Attach this distributed graph helper to the given graph. This will
|
|
* be called as part of vtkGraph::SetDistributedGraphHelper.
|
|
*/
|
|
virtual void AttachToGraph(vtkGraph* graph);
|
|
|
|
/**
|
|
* The graph to which this distributed graph helper is already attached.
|
|
*/
|
|
vtkGraph* Graph;
|
|
|
|
/**
|
|
* The distribution function used to map a pedigree ID to a processor.
|
|
*/
|
|
vtkVertexPedigreeIdDistribution VertexDistribution;
|
|
|
|
/**
|
|
* Extra, user-specified data to be passed into the distribution function.
|
|
*/
|
|
void* VertexDistributionUserData;
|
|
|
|
/**
|
|
* Bit mask to speed up decoding graph info {owner,index}
|
|
*/
|
|
vtkIdType signBitMask;
|
|
|
|
/**
|
|
* Bit mask to speed up decoding graph info {owner,index}
|
|
*/
|
|
vtkIdType highBitShiftMask;
|
|
|
|
/**
|
|
* Number of bits required to represent # of processors (owner)
|
|
*/
|
|
int procBits;
|
|
|
|
/**
|
|
* Number of bits required to represent {vertex,edge} index
|
|
*/
|
|
int indexBits;
|
|
|
|
private:
|
|
vtkDistributedGraphHelper(const vtkDistributedGraphHelper&) = delete;
|
|
void operator=(const vtkDistributedGraphHelper&) = delete;
|
|
|
|
friend class vtkGraph;
|
|
};
|
|
|
|
#endif // vtkDistributedGraphHelper_h
|