dolfinx::graph Namespace Reference

Graph data structures and algorithms. More...

Namespaces
namespace	build
	Tools for distributed graphs.
namespace	kahip
	Interfaces to KaHIP parallel partitioner.

Classes
class	AdjacencyList
	This class provides a static adjacency list data structure. It is commonly used to store directed graphs. For each node in the contiguous list of nodes [0, 1, 2, ..., n) it stores the connected nodes. The representation is strictly local, i.e. it is not parallel aware. More...

Typedefs
using	partition_fn = std::function< graph::AdjacencyList< std::int32_t >(MPI_Comm, int, const AdjacencyList< std::int64_t > &, bool)>
	Signature of functions for computing the parallel partitioning of a distributed graph.

Functions
template<typename U > requires requires { typename std::decay_t<U>::value_type; requires std::convertible_to< U, std::vector<typename std::decay_t<U>::value_type>>; }
AdjacencyList< typename std::decay_t< U >::value_type >	regular_adjacency_list (U &&data, int degree)
	Construct a constant degree (valency) adjacency list.
std::vector< std::int32_t >	reorder_gps (const graph::AdjacencyList< std::int32_t > &graph)
	Re-order a graph using the Gibbs-Poole-Stockmeyer algorithm.
AdjacencyList< std::int32_t >	partition_graph (MPI_Comm comm, int nparts, const AdjacencyList< std::int64_t > &local_graph, bool ghosting)
	Partition graph across processes using the default graph partitioner.

Detailed Description

Graph data structures and algorithms.

Data structures for building and representing graphs, and algorithms on graphs, e.g., re-ordering and partitioning.

Function Documentation

partition_graph()

graph::AdjacencyList< std::int32_t > partition_graph	(	MPI_Comm	comm,
		int	nparts,
		const AdjacencyList< std::int64_t > &	local_graph,
		bool	ghosting
	)

Partition graph across processes using the default graph partitioner.

Parameters

[in]	comm	MPI communicator that the graph is distributed across.
[in]	nparts	Number of partitions to divide graph nodes into.
[in]	local_graph	Node connectivity graph.
[in]	ghosting	Flag to enable ghosting of the output node distribution.

Returns

Destination rank for each input node.

regular_adjacency_list()

template<typename U >
requires requires { typename std::decay_t<U>::value_type; requires std::convertible_to< U, std::vector<typename std::decay_t<U>::value_type>>; }

AdjacencyList< typename std::decay_t< U >::value_type > regular_adjacency_list	(	U &&	data,
		int	degree
	)

Construct a constant degree (valency) adjacency list.

A constant degree graph has the same number of edges for every node.

Parameters

[in]	data	Adjacency array
[in]	degree	The number of (outgoing) edges for each node

Returns

An adjacency list

reorder_gps()

std::vector< std::int32_t > reorder_gps

(

const graph::AdjacencyList< std::int32_t > &

graph

)

Re-order a graph using the Gibbs-Poole-Stockmeyer algorithm.

The algorithm is described in An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix, SIAM Journal on Numerical Analysis, 13(2): 236-250, 1976, https://doi.org/10.1137/0713023.

Parameters

[in]

graph

The graph to compute a re-ordering for

Returns

Reordering array map, where map[i] is the new index of node i