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

#include <sparse_graph.hh>

Inheritance diagram for SparseGraph:

Collaboration diagram for SparseGraph:

[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:

/home/runner/work/flow123d/flow123d/src/la/sparse_graph.hh
/home/runner/work/flow123d/flow123d/src/la/sparse_graph.cc

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SparseGraph() [1/2]

◆ SparseGraph() [2/2]

◆ ~SparseGraph()

Member Function Documentation

◆ allocate_sparse_graph()

◆ check_subgraph_connectivity()

◆ DFS()

◆ finalize()

◆ get_distr()

◆ is_symmetric()

◆ partition()

◆ set_edge()

◆ set_vtx_position()

◆ view()

Friends And Related Function Documentation

◆ operator<

Member Data Documentation

◆ adj

◆ adj_of_proc

◆ adj_weights

◆ checked_vtx

◆ part_to_check

◆ proc_to_check

◆ rows

◆ vtx_distr

◆ vtx_weights

◆ vtx_XYZ