Flow123d
release_2.2.0-914-gf1a3a4f
|
Virtual class for construction and partitioning of a distributed sparse graph. More...
#include <sparse_graph.hh>
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) |
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.
SparseGraph::SparseGraph | ( | const Distribution & | distr | ) |
Construct an empty graph form given Distribution of vertices.
Definition at line 37 of file sparse_graph.cc.
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.
|
virtual |
Free all non-null pointers.
Definition at line 303 of file sparse_graph.cc.
|
protectedpure virtual |
Use virtual method for allocation since for PETSC interface we have to use PetscMalloc.
Implemented in SparseGraphMETIS, and SparseGraphPETSC.
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.
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.
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.
|
inline |
Returns reference to the distribution of the graph.
Definition at line 120 of file sparse_graph.hh.
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.
|
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.
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
[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.
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.
[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.
void SparseGraph::view | ( | ) |
Simple graph output. Has to be already finalized.
Definition at line 261 of file sparse_graph.cc.
Edge comparison. For lexical sorting of local edges.
Definition at line 89 of file sparse_graph.cc.
|
protected |
sparse adjency
Definition at line 146 of file sparse_graph.hh.
storage for graph edges for individual processors
Definition at line 154 of file sparse_graph.hh.
|
protected |
Definition at line 147 of file sparse_graph.hh.
|
protected |
coloring of DFS algorithm
Definition at line 151 of file sparse_graph.hh.
|
protected |
created partitioning used through check of connectivity
Definition at line 149 of file sparse_graph.hh.
|
protected |
subgraph to check
Definition at line 150 of file sparse_graph.hh.
|
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.
|
protected |
distribution of vertexes
Definition at line 141 of file sparse_graph.hh.
|
protected |
Vertex weights for computations (optional).
Definition at line 145 of file sparse_graph.hh.
|
protected |
optional vertex coordinates (global array)
Definition at line 144 of file sparse_graph.hh.