Flow123d  master-f44eb46
Classes | Public Member Functions | Protected Member Functions | Protected Attributes | Friends | List of all members
SparseGraph Class Referenceabstract

Virtual class for construction and partitioning of a distributed sparse graph. More...

#include <sparse_graph.hh>

Inheritance diagram for SparseGraph:
Inheritance graph
[legend]
Collaboration diagram for SparseGraph:
Collaboration graph
[legend]

Classes

struct  Edge
 

Public Member Functions

 SparseGraph (const Distribution &distr)
 
 SparseGraph (int loc_size, MPI_Comm comm)
 
void set_edge (const int a, const int b, int weight=1)
 
void set_vtx_position (const int vtx, const float xyz[3], int weight=1)
 
void finalize ()
 Make sparse graph structures: rows, adj. More...
 
virtual void partition (int *loc_part)=0
 
bool check_subgraph_connectivity (int *part)
 
void DFS (int vtx)
 
Distribution get_distr ()
 
void view ()
 
bool is_symmetric ()
 
virtual ~SparseGraph ()
 

Protected Member Functions

virtual void allocate_sparse_graph (int lsize_vtxs, int lsize_adj)=0
 

Protected Attributes

Distribution vtx_distr
 distribution of vertexes More...
 
int * rows
 
float * vtx_XYZ
 optional vertex coordinates (global array) More...
 
int * vtx_weights
 Vertex weights for computations (optional). More...
 
int * adj
 sparse adjency More...
 
int * adj_weights
 
int * part_to_check
 created partitioning used through check of connectivity More...
 
int proc_to_check
 subgraph to check More...
 
std::vector< int > checked_vtx
 coloring of DFS algorithm More...
 
vector< stack< Edge > > adj_of_proc
 storage for graph edges for individual processors More...
 

Friends

bool operator< (const Edge &a, const Edge &b)
 

Detailed Description

Virtual class for construction and partitioning of a distributed sparse graph.

An empty graph is created in constructor (collective). You has to provide either Distribution of the vertices or local number of vertices and communicator. Than you can add edges with set_edge method. Added edges are stored in the buffer on calling processor. Than you have to call finalize method (collective) to make sparse graph. Graph partitioning is either directly through METIS or through PETSC (ParMETIS, and others). There is derived class for particular partitioning method.

Actual implementation is not fully scalable. row sizes (vtx degree) are accumulated in global arrays, then communicated to all processors and finally only local part is used. There should be only local part of the final array with aditional buffer for ex-processor values.

Other issue is that we hav eproblem using Parmetis so acctualy only METIS can be used on a parallel graph located on the first processor.

TODO: use Boost parallel graphs and write interface form them to METIS, Parmetis or PETSC

Definition at line 56 of file sparse_graph.hh.

Constructor & Destructor Documentation

◆ SparseGraph() [1/2]

SparseGraph::SparseGraph ( const Distribution distr)

Construct an empty graph form given Distribution of vertices.

Definition at line 37 of file sparse_graph.cc.

◆ SparseGraph() [2/2]

SparseGraph::SparseGraph ( int  loc_size,
MPI_Comm  comm 
)

Construct an empty graph for given number of local vertices of the graph. Make its own distribution object.

Definition at line 53 of file sparse_graph.cc.

◆ ~SparseGraph()

SparseGraph::~SparseGraph ( )
virtual

Free all non-null pointers.

Definition at line 303 of file sparse_graph.cc.

Member Function Documentation

◆ allocate_sparse_graph()

virtual void SparseGraph::allocate_sparse_graph ( int  lsize_vtxs,
int  lsize_adj 
)
protectedpure virtual

Use virtual method for allocation since for PETSC interface we have to use PetscMalloc.

Implemented in SparseGraphMETIS, and SparseGraphPETSC.

Here is the caller graph for this function:

◆ check_subgraph_connectivity()

bool SparseGraph::check_subgraph_connectivity ( int *  part)

Check if the subgraphs of the given partitioning are connected. Works only for fully localized graph (on one processor).

Check if the subgraphs of the partitions are connected.

Definition at line 213 of file sparse_graph.cc.

◆ DFS()

void SparseGraph::DFS ( int  vtx)

Recursive part of Deep First Search algorithm of the connectivity check.

Definition at line 245 of file sparse_graph.cc.

Here is the caller graph for this function:

◆ finalize()

void SparseGraph::finalize ( )

Make sparse graph structures: rows, adj.

1) send edges to the owner of .from vertex 2) sort local edges 3) fill rows, adj; remove duplicities

Using MPICH valgrind reports condition on uninitialized value here. Nevertheless we cna not get rid of it even after explicitly set all allocated space to zero.

Definition at line 98 of file sparse_graph.cc.

Here is the caller graph for this function:

◆ get_distr()

Distribution SparseGraph::get_distr ( )
inline

Returns reference to the distribution of the graph.

Definition at line 120 of file sparse_graph.hh.

Here is the caller graph for this function:

◆ is_symmetric()

bool SparseGraph::is_symmetric ( )

Check symmetry of the local part of the graph. Has to be already finalized.

Definition at line 275 of file sparse_graph.cc.

◆ partition()

virtual void SparseGraph::partition ( int *  loc_part)
pure virtual

Fills an array of integers by the partitioning of the vertices. The array size is number of local verices according to the distribution of the graph. see get_distr() method. The array has to be PREALLOCATED by user to the correct size.

Implemented in SparseGraphMETIS, and SparseGraphPETSC.

Here is the caller graph for this function:

◆ set_edge()

void SparseGraph::set_edge ( const int  a,
const int  b,
int  weight = 1 
)

Store an edge. We just store all inserted edges and count support arrays to communicate edges to the right processors

Parameters
[in]a- starting vertex of the edge
[in]b- terminal vertex of the edge
[in]weight- optional weight of the edge (integer)

Definition at line 66 of file sparse_graph.cc.

Here is the caller graph for this function:

◆ set_vtx_position()

void SparseGraph::set_vtx_position ( const int  vtx,
const float  xyz[3],
int  weight = 1 
)

Set position and possibly weight of a local vertex. Assume that vtx is an index of local vertex. Positions are used for initial distribution when using ParMETIS.

Parameters
[in]vtx- global vertex index (from zero)
[in]xyz- coordinates of vetrex position
[in]weight- optional weight of the vertex

Definition at line 76 of file sparse_graph.cc.

◆ view()

void SparseGraph::view ( )

Simple graph output. Has to be already finalized.

Definition at line 261 of file sparse_graph.cc.

Friends And Related Function Documentation

◆ operator<

bool operator< ( const Edge a,
const Edge b 
)
friend

Edge comparison. For lexical sorting of local edges.

Definition at line 89 of file sparse_graph.cc.

Member Data Documentation

◆ adj

int* SparseGraph::adj
protected

sparse adjency

Definition at line 146 of file sparse_graph.hh.

◆ adj_of_proc

vector< stack<Edge> > SparseGraph::adj_of_proc
protected

storage for graph edges for individual processors

Definition at line 154 of file sparse_graph.hh.

◆ adj_weights

int* SparseGraph::adj_weights
protected

Definition at line 147 of file sparse_graph.hh.

◆ checked_vtx

std::vector<int> SparseGraph::checked_vtx
protected

coloring of DFS algorithm

Definition at line 151 of file sparse_graph.hh.

◆ part_to_check

int* SparseGraph::part_to_check
protected

created partitioning used through check of connectivity

Definition at line 149 of file sparse_graph.hh.

◆ proc_to_check

int SparseGraph::proc_to_check
protected

subgraph to check

Definition at line 150 of file sparse_graph.hh.

◆ rows

int* SparseGraph::rows
protected

starts of vtx rows in adj array, vtx i have edge to vertexes adj[rows[i]] .. adj[rows[i+1]-1]

Definition at line 142 of file sparse_graph.hh.

◆ vtx_distr

Distribution SparseGraph::vtx_distr
protected

distribution of vertexes

Definition at line 141 of file sparse_graph.hh.

◆ vtx_weights

int* SparseGraph::vtx_weights
protected

Vertex weights for computations (optional).

Definition at line 145 of file sparse_graph.hh.

◆ vtx_XYZ

float* SparseGraph::vtx_XYZ
protected

optional vertex coordinates (global array)

Definition at line 144 of file sparse_graph.hh.


The documentation for this class was generated from the following files: