dolfinx::graph Namespace Reference

Graph data structures and algorithms. More...

Namespaces
namespace	build
namespace	kahip
	Interfaces to KaHIP parallel partitioner.

Classes
class	AdjacencyList
	This class provides a static adjacency list data structure. More...

Typedefs
using	partition_fn
	Signature of functions for computing the parallel partitioning of a distributed graph.

Functions
template<typename V = std::nullptr_t, 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, V >	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, std::size_t max_candidates, std::size_t num_threads)
	Re-order a graph using the Gibbs-Poole-Stockmeyer algorithm.
std::vector< std::int32_t >	reorder_rcm (const graph::AdjacencyList< std::int32_t > &graph)
	Re-order a graph using the Reverse Cuthill-McKee 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.
template<typename T>
graph::AdjacencyList< int >	compute_destination_ranks (MPI_Comm comm, const graph::AdjacencyList< std::int64_t > &graph, const std::vector< T > &node_disp, const std::vector< T > &part)
AdjacencyList< std::tuple< int, std::size_t, std::int8_t >, std::pair< std::int32_t, std::int32_t > >	comm_graph (const common::IndexMap &map, int root=0)
	Compute an directed graph that describes the parallel communication patterns.
std::string	comm_to_json (const AdjacencyList< std::tuple< int, std::size_t, std::int8_t >, std::pair< std::int32_t, std::int32_t > > &g)
	Build communication graph data as a JSON string.

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

comm_graph()

graph::AdjacencyList< std::tuple< int, std::size_t, std::int8_t >, std::pair< std::int32_t, std::int32_t > > comm_graph	(	const common::IndexMap &	map,
		int	root = 0 )

Compute an directed graph that describes the parallel communication patterns.

The graph describes the communication pattern for a 'forward scatter', i.e. sending owned data to ranks that ghost the data (owner->ghost operation).

Each node in the graph corresponds to an MPI rank. A graph edge is a forward (owner->ghost) communication path. The edge weight is the number 'values' communicated along the edge. Each edge also has a marker that indicates if the edge is sending data to:

1. A node (rank) that shares memory with the sender (true), or
2. A remote node that does not share memory with the sender (false).

The graph data can be visualised using a tool like NetworkX,

Note

Collective.

Parameters

[in]	map	Index map to build the graph for.
[in]	root	MPI rank on which to build the communication graph data.

Returns

Adjacency list representing the communication pattern. Edges data is (0) the edge, (1) edge weight (weight) and (2) local/remote is memory indicator (local==1 is an edge to a shared memory node). Node data is (number of owned indices, number of ghost indices).

comm_to_json()

std::string comm_to_json

(

const AdjacencyList< std::tuple< int, std::size_t, std::int8_t >, std::pair< std::int32_t, std::int32_t > > &

g

)

Build communication graph data as a JSON string.

The data string can be decoded (loaded) to create a Python object from which a NetworkX graph can be constructed.

See ::comm_graph for a description of the data.

Parameters

[in]

g

Communication graph.

Returns

JSON string representing the communication graph. Edge data is data volume (weight) and local/remote memory indicator (local==1 is an edge to an shared memory process/rank, other wise the target node is a remote memory rank).

compute_destination_ranks()

template<typename T>

graph::AdjacencyList< int > compute_destination_ranks	(	MPI_Comm	comm,
		const graph::AdjacencyList< std::int64_t > &	graph,
		const std::vector< T > &	node_disp,
		const std::vector< T > &	part )

Todo

Is it un-documented that the owning rank must come first in reach list of edges?

Parameters

[in]	comm	The communicator
[in]	graph	Graph, using global indices for graph edges
[in]	node_disp	The distribution of graph nodes across MPI ranks. The global index gidx of local index lidx is lidx + node_disp[my_rank].
[in]	part	The destination rank for owned nodes, i.e. dest[i] is the destination of the node with local index i.

Returns

Destination ranks for each local node.

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 V = std::nullptr_t, 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, V > regular_adjacency_list	(	U &&	data,
		int	degree )

Construct a constant degree (valency) adjacency list.

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

Parameters

[in]	data	Adjacency array.
[in]	degree	Number of (outgoing) links for each node.

Returns

An adjacency list.

reorder_gps()

std::vector< std::int32_t > reorder_gps	(	const graph::AdjacencyList< std::int32_t > &	graph,
		std::size_t	max_candidates,
		std::size_t	num_threads )

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.

At each step the pseudo-diameter search (the dominant cost for dense graphs, e.g. dof-adjacency graphs from higher-order elements) tests candidate root vertices from the final level of a level structure, in increasing degree order, to find the pair of vertices that minimises level width. Testing every candidate costs O(|S| * (V+E)) per step, where |S| is the size of the final level, which can dominate run time for large graphs. max_candidates bounds how many of the lowest-degree candidates are tried at each step; the (up to max_candidates) candidates that are tried are evaluated concurrently across num_threads threads. The result is identical for any num_threads, since candidates are only evaluated concurrently, not selected concurrently: the choice of which candidate to use is still made sequentially afterwards, in the original order.

A small max_candidates (e.g. 5) is a good trade-off for simple, convex, roughly uniform-density meshes, where it matches an exhaustive search at a fraction of the cost. For non-convex domains or strongly graded meshes (e.g. boundary-layer meshes) a small cap can measurably worsen the resulting bandwidth and profile; pass a larger value if ordering quality matters more than reordering time for such meshes.

To recover the original (uncapped) Gibbs-Poole-Stockmeyer algorithm as published – testing every candidate in the final level, with no truncation – pass max_candidates = std::numeric_limits<std::size_t>::max() (or any value at least as large as the largest final level S encountered; the actual number of candidates tested is std::min(max_candidates, S.size()), so an oversized value is never invalid, just unnecessary).

Parameters

[in]	graph	The graph to compute a re-ordering for
[in]	max_candidates	Maximum number of final-level candidates to test at each step of the pseudo-diameter search. Pass std::numeric_limits<std::size_t>::max() for the original, exhaustive algorithm (see above).
[in]	num_threads	Number of threads to use for the pseudo-diameter candidate search.

Returns

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

reorder_rcm()

std::vector< std::int32_t > reorder_rcm

(

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

graph

)

Re-order a graph using the Reverse Cuthill-McKee algorithm.

The algorithm is described in Reducing the Bandwidth of Sparse Symmetric Matrices, Proceedings of the 1969 24th National Conference, ACM, 1969, pp. 157-172, https://doi.org/10.1145/800195.805928. The pseudo-peripheral root used to start the ordering is found using the George-Liu "double sweep" heuristic (as in reorder_gps's Algorithm I, but trying only the single lowest-degree candidate at each step).

Unlike reorder_gps, there is no width-minimising second phase: a single level structure is built from the pseudo-peripheral root, each level is numbered in increasing degree order, and the whole numbering is reversed (the "reverse" in Reverse Cuthill-McKee, which tends to reduce profile relative to the plain, non-reversed numbering). This makes reorder_rcm an O(V+E) algorithm with a much smaller constant than reorder_gps, at the cost of the bandwidth and profile quality that reorder_gps's extra phase can provide on non-convex or strongly graded meshes – for simple, convex, roughly uniform-density meshes the two typically produce comparable bandwidth.

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.