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...
struct	Partitioner
	An ::AnyPartitionFunction together with the node weights it should be called with, if any. More...

Typedefs
using	partition_fn
	Signature of functions for computing the parallel partitioning of a distributed graph, using the graph edges alone.
using	geom_partition_fn
	Signature of functions for computing the parallel partitioning of a distributed graph from the positions of its nodes in space alone, with no access to the graph edges.
using	hybrid_partition_fn
	Signature of functions for computing the parallel partitioning of a distributed graph using both its edges and the positions of its nodes in space.
using	AnyPartitionFunction = std::variant<partition_fn, geom_partition_fn, hybrid_partition_fn>
	Any of the three partitioning function shapes that mesh::create_mesh accepts: ::partition_fn, ::geom_partition_fn, or ::hybrid_partition_fn.

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_rcm (const graph::AdjacencyList< std::int32_t > &graph)
	Re-order a graph using the Reverse Cuthill-McKee algorithm.
bool	has_partitioner (const AnyPartitionFunction &partitioner)
	Whether an ::AnyPartitionFunction holds a callable partitioner.
AdjacencyList< std::int32_t >	partition_graph (MPI_Comm comm, int nparts, const AdjacencyList< std::int64_t > &local_graph, std::optional< std::span< const std::int32_t > > node_weights, std::optional< std::span< const std::int32_t > > edge_weights, 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)
std::vector< int >	partition_sfc_morton (MPI_Comm comm, int nparts, std::span< const double > x, int gdim, std::optional< std::span< const std::int32_t > > weights=std::nullopt)
	Partition points into nparts groups of (approximately) equal size using a Morton ('Z-order') space-filling curve.
std::vector< int >	partition_sfc_hilbert (MPI_Comm comm, int nparts, std::span< const double > x, int gdim, std::optional< std::span< const std::int32_t > > weights=std::nullopt)
	Partition points into nparts groups of (approximately) equal size using a Hilbert space-filling curve.
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

◆ AnyPartitionFunction

using AnyPartitionFunction = std::variant<partition_fn, geom_partition_fn, hybrid_partition_fn>

Any of the three partitioning function shapes that mesh::create_mesh accepts: ::partition_fn, ::geom_partition_fn, or ::hybrid_partition_fn.

mesh::create_mesh always has the cell topology available, so it builds the dual graph itself and passes it to a ::partition_fn or ::hybrid_partition_fn, neither of which has any other way to obtain it. For a ::geom_partition_fn or ::hybrid_partition_fn it also computes cell centroids from the vertex coordinates – using the same (commg, x, xshape) data it uses to build the mesh – since neither has any other way to obtain them.

◆ geom_partition_fn

using geom_partition_fn

Initial value:

 std::function<std::vector<int>(
    MPI_Comm, int, std::span<const double>, int,
    std::optional<std::span<const std::int32_t>>)>

Signature of functions for computing the parallel partitioning of a distributed graph from the positions of its nodes in space alone, with no access to the graph edges.

With no graph, ghost destinations cannot be computed, so this signature has no ghosting parameter – a partitioner of this type is never asked to ghost. See ::hybrid_partition_fn for a partitioning function that has access to both node positions and graph edges, and so can ghost.

Note: Coordinates are always double, regardless of the mesh's scalar type: partition quality is insensitive to position precision, and double avoids precision loss when positions are quantised into keys.

Parameters

[in]	comm	MPI Communicator that the graph is distributed across.
[in]	nparts	Number of partitions to divide graph nodes into.
[in]	x	Node coordinates, row-major with gdim columns and one row per node.
[in]	gdim	Number of coordinate components per node.
[in]	node_weights	Node weights, one entry per row of x. If std::nullopt, nodes are treated as having equal weight. Not every ::geom_partition_fn can honour node weights; one that cannot throws if given anything other than std::nullopt.

Returns: Destination rank(s) for each input node.

◆ hybrid_partition_fn

using hybrid_partition_fn

Initial value:

 std::function<graph::AdjacencyList<std::int32_t>(
    MPI_Comm, int, const AdjacencyList<std::int64_t>&, std::span<const double>,
    std::optional<std::span<const std::int32_t>>,
    std::optional<std::span<const std::int32_t>>, bool)>

Signature of functions for computing the parallel partitioning of a distributed graph using both its edges and the positions of its nodes in space.

Unlike ::geom_partition_fn, a hybrid partitioner uses the graph edges in the partitioning decision itself, not just for ghosting, so it always needs both inputs. ParMETIS GeomKway, for example, redistributes nodes along a space-filling curve and then applies graph partitioning to the result.

Note: The coordinates are always double, for the same reason as ::geom_partition_fn.

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]	x	Node coordinates, row-major with one row per node. x.size() / local_graph.num_nodes() gives the number of coordinate components per node.
[in]	node_weights	Node weights, one entry per node in local_graph. If std::nullopt, nodes are treated as having equal weight.
[in]	edge_weights	Edge weights, one entry per edge in local_graph. If std::nullopt, edges are treated as having equal weight.
[in]	ghosting	Flag to enable ghosting of the output node distribution.

Returns: Destination rank(s) for each input node.

◆ partition_fn

using partition_fn

Initial value:

 std::function<graph::AdjacencyList<std::int32_t>(
    MPI_Comm, int, const AdjacencyList<std::int64_t>&,
    std::optional<std::span<const std::int32_t>>,
    std::optional<std::span<const std::int32_t>>, bool)>

Signature of functions for computing the parallel partitioning of a distributed graph, using the graph edges alone.

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]	node_weights	Node weights, one entry per node in local_graph. If std::nullopt, nodes are treated as having equal weight.
[in]	edge_weights	Edge weights, one entry per edge in local_graph. If std::nullopt, edges are treated as having equal weight.
[in]	ghosting	Flag to enable ghosting of the output node distribution.

Returns: Destination rank(s) 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:

A node (rank) that shares memory with the sender (true), or
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.

◆ has_partitioner()

bool has_partitioner ( const AnyPartitionFunction & partitioner )

Whether an ::AnyPartitionFunction holds a callable partitioner.

Parameters

[in] partitioner Partitioner to check.

Returns: true if partitioner holds a callable function, false if it is default-constructed (not callable).

◆ partition_graph()

graph::AdjacencyList< std::int32_t > partition_graph	(	MPI_Comm	comm,
		int	nparts,
		const AdjacencyList< std::int64_t > &	local_graph,
		std::optional< std::span< const std::int32_t > >	node_weights,
		std::optional< std::span< const std::int32_t > >	edge_weights,
		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]	node_weights	Node weights. Each partition aims to have the same sum of node weights. If std::nullopt, nodes are treated as having equal weight.
[in]	edge_weights	Edge weights. Higher values increase the likelihood that adjacent cells will be on the same partition. If std::nullopt, edges are treated as having equal weight.
[in]	ghosting	Flag to enable ghosting of the output node distribution.

Returns: Destination rank for each input node.

◆ partition_sfc_hilbert()

std::vector< int > partition_sfc_hilbert	(	MPI_Comm	comm,
		int	nparts,
		std::span< const double >	x,
		int	gdim,
		std::optional< std::span< const std::int32_t > >	weights = std::nullopt )

Partition points into nparts groups of (approximately) equal size using a Hilbert space-filling curve.

As ::partition_sfc_morton, but points are ordered along a Hilbert curve. Successive points on a Hilbert curve are always neighbours in space, which a Morton curve does not guarantee, so the resulting partitions are more compact and cut fewer edges. Computing the curve index is more expensive than a Morton key, but in both cases the cost is dominated by the sampling and the search for each point's part.

Note: Collective.; There is no graph, so this cannot ghost: it always assigns exactly one destination per point.

Parameters

[in]	comm	MPI communicator that the points are distributed across.
[in]	nparts	Number of partitions to divide the points into.
[in]	x	Point coordinates, row-major with gdim columns.
[in]	gdim	Number of coordinate components per point. Must be 1, 2 or 3.
[in]	weights	Point weights, one entry per row of x. Partitions aim for equal sums of weight along the curve rather than equal counts. If std::nullopt, points are treated as having equal weight.

Returns: Destination rank for each point, one entry per row of x.

◆ partition_sfc_morton()

std::vector< int > partition_sfc_morton	(	MPI_Comm	comm,
		int	nparts,
		std::span< const double >	x,
		int	gdim,
		std::optional< std::span< const std::int32_t > >	weights = std::nullopt )

Partition points into nparts groups of (approximately) equal size using a Morton ('Z-order') space-filling curve.

Points are ordered by the Morton key of their position in the global bounding box, and the resulting order is cut into nparts equal pieces. Splitters are found from a distributed sample of the keys, routed to the rank owning its key range rather than gathered to every rank, so per-rank cost and memory scale with the sample size divided across ranks, not multiplied by them.

Compared to a graph partitioner, this is much cheaper because no graph is required and gives a near-perfect load balance, at the cost of a larger number of cut edges (typically tens of percent for a mesh dual graph). The distributed sample uses a global budget proportional to nparts, but every rank stores the nparts - 1 splitter keys.

A Morton curve jumps a long way in space each time a high bit of the key changes, so consecutive points on the curve are not always close together. ::partition_sfc_hilbert avoids this.

Note: Collective.; There is no graph, so this cannot ghost: it always assigns exactly one destination per point.

Parameters

[in]	comm	MPI communicator that the points are distributed across.
[in]	nparts	Number of partitions to divide the points into.
[in]	x	Point coordinates, row-major with gdim columns.
[in]	gdim	Number of coordinate components per point. Must be 1, 2 or 3.
[in]	weights	Point weights, one entry per row of x. Partitions aim for equal sums of weight along the curve rather than equal counts. If std::nullopt, points are treated as having equal weight.

Returns: Destination rank for each point, one entry per row of x.

◆ 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_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, trying only the single lowest-degree candidate at each step.

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 small constant.

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.

Namespaces

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ AnyPartitionFunction

◆ geom_partition_fn

◆ hybrid_partition_fn

◆ partition_fn

Function Documentation

◆ comm_graph()

◆ comm_to_json()

◆ compute_destination_ranks()

◆ has_partitioner()

◆ partition_graph()

◆ partition_sfc_hilbert()

◆ partition_sfc_morton()

◆ regular_adjacency_list()

◆ reorder_rcm()