Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
259 lines (219 sloc) 10.8 KB
/*=========================================================================
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)
*/
// .NAME vtkDistributedGraphHelper - helper for the vtkGraph class
// that allows the graph to be distributed across multiple memory spaces.
//
// .SECTION Description
// 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.
//
// .SECTION See Also
// vtkGraph
#ifndef __vtkDistributedGraphHelper_h
#define __vtkDistributedGraphHelper_h
#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 VTK_FILTERING_EXPORT vtkDistributedGraphHelper : public vtkObject
{
public:
vtkTypeMacro(vtkDistributedGraphHelper,vtkObject);
void PrintSelf(ostream& os, vtkIndent indent);
// Description:
// Returns owner of vertex v, by extracting top ceil(log2 P) bits of v.
vtkIdType GetVertexOwner(vtkIdType v) const;
// Description:
// Returns local index of vertex v, by masking off top ceil(log2 P) bits of v.
vtkIdType GetVertexIndex(vtkIdType v) const;
// Description:
// Returns owner of edge with ID e_id, by extracting top ceil(log2 P) bits of e_id.
vtkIdType GetEdgeOwner(vtkIdType e_id) const;
// Description:
// 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;
// Description:
// Builds a distributed ID consisting of the given owner and the local ID.
vtkIdType MakeDistributedId(int owner, vtkIdType local);
//BTX
// Description:
// 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 NULL function pointer is provided, the default
// hashed distribution will be used.
void SetVertexPedigreeIdDistribution(vtkVertexPedigreeIdDistribution Func,
void *userData);
//ETX
// Description:
// Determine which processor owns the vertex with the given pedigree ID.
vtkIdType GetVertexOwnerByPedigreeId(const vtkVariant& pedigreeId);
// Description:
// 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;
// Description:
// 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;
// Description:
// 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();
virtual ~vtkDistributedGraphHelper();
// Description:
// Add a vertex, optionally with properties, to the distributed graph.
// If vertex is non-NULL, it will be set
// to the newly-added (or found) vertex. Note that if propertyArr is
// non-NULL 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;
// Description:
// Add a vertex with the given pedigreeId to the distributed graph. If
// vertex is non-NULL, it will receive the newly-created vertex.
virtual void AddVertexInternal(const vtkVariant& pedigreeId, vtkIdType *vertex) = 0;
// Description:
// 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;
// Description:
// 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;
// Description:
// 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;
// Description:
// 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;
// Description:
// 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;
// Description:
// 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;
// Description:
// Attach this distributed graph helper to the given graph. This will
// be called as part of vtkGraph::SetDistributedGraphHelper.
virtual void AttachToGraph(vtkGraph *graph);
// Description:
// The graph to which this distributed graph helper is already attached.
vtkGraph *Graph;
//BTX
// Description:
// The distribution function used to map a pedigree ID to a processor.
vtkVertexPedigreeIdDistribution VertexDistribution;
// Description:
// Extra, user-specified data to be passed into the distribution function.
void *VertexDistributionUserData;
// Description:
// Bit mask to speed up decoding graph info {owner,index}
vtkIdType signBitMask;
// Description:
// Bit mask to speed up decoding graph info {owner,index}
vtkIdType highBitShiftMask;
// Description:
// Number of bits required to represent # of processors (owner)
int procBits;
// Description:
// Number of bits required to represent {vertex,edge} index
int indexBits;
//ETX
private:
vtkDistributedGraphHelper(const vtkDistributedGraphHelper&); // Not implemented
void operator=(const vtkDistributedGraphHelper&); // Not implemented
//BTX
friend class vtkGraph;
//ETX
};
#endif // __vtkDistributedGraphHelper_h