dolfinx::graph Namespace Reference

Graph data structures and algorithms. More...

Namespaces
namespace	build
namespace	kahip
	Interfaces to KaHIP parallel partitioner.

Classes
class	AdjacencyList

Typedefs
using	partition_fn
	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.

Typedef Documentation

partition_fn

using partition_fn

Initial value:

 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.

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

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