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	reorder_graph_fn
	Signature of functions that reorder the nodes of a graph.
using	reorder_geom_fn
	Signature of functions that reorder points from their positions.
using	Reorder = std::variant<reorder_graph_fn, reorder_geom_fn>
	A graph or geometric reordering function for mesh cells.
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 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 using a Hilbert space-filling curve.
std::vector< std::int32_t >	reorder_sfc_morton (std::span< const double > x, int gdim)
	Reorder locally supplied points using a Morton ('Z-order') space-filling curve.
std::vector< std::int32_t >	reorder_sfc_hilbert (std::span< const double > x, int gdim)
	Reorder locally supplied points 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.

◆ Reorder

using Reorder = std::variant<reorder_graph_fn, reorder_geom_fn>

A graph or geometric reordering function for mesh cells.

An empty ::reorder_graph_fn selects ::reorder_rcm for mesh construction. A ::reorder_geom_fn is called with locally owned cell centroids.

◆ reorder_geom_fn

using reorder_geom_fn

Initial value:

std::function<std::vector<std::int32_t>(

std::span<const double> x, int gdim)>

Signature of functions that reorder points from their positions.

Parameters

[in]	x	Point coordinates, row-major with gdim columns.
[in]	gdim	Number of coordinate components per point.

Returns: Reordering array map, where map[i] is the new index of point i.

◆ reorder_graph_fn

using reorder_graph_fn

Initial value:

std::function<std::vector<std::int32_t>(

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

Signature of functions that reorder the nodes of a graph.

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 using a Hilbert space-filling curve.

As ::partition_sfc_morton, but uses Hilbert keys, which generally preserve spatial locality better than Morton keys.

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. Each weight must be positive. 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 using a Morton ('Z-order') space-filling curve.

Points are ordered by their Morton keys in the global bounding box and divided into groups with approximately equal numbers of points or total weight. For improved spatial locality, see ::partition_sfc_hilbert.

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. Each weight must be positive. 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.

◆ reorder_sfc_hilbert()

std::vector< std::int32_t > reorder_sfc_hilbert	(	std::span< const double >	x,
		int	gdim )

Reorder locally supplied points using a Hilbert space-filling curve.

As ::reorder_sfc_morton, but uses Hilbert keys.

Parameters

[in]	x	Point coordinates, row-major with gdim columns.
[in]	gdim	Number of coordinate components per point. Must be 1, 2 or 3.

Returns: Reordering array map, where map[i] is the new index of point i.

◆ reorder_sfc_morton()

std::vector< std::int32_t > reorder_sfc_morton	(	std::span< const double >	x,
		int	gdim )

Reorder locally supplied points using a Morton ('Z-order') space-filling curve.

The bounding box is computed from x. The returned ordering is local and does not provide a distributed ordering.

Parameters

[in]	x	Point coordinates, row-major with gdim columns.
[in]	gdim	Number of coordinate components per point. Must be 1, 2 or 3.

Returns: Reordering array map, where map[i] is the new index of point i.

Namespaces

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ AnyPartitionFunction

◆ geom_partition_fn

◆ hybrid_partition_fn

◆ partition_fn

◆ Reorder

◆ reorder_geom_fn

◆ reorder_graph_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()

◆ reorder_sfc_hilbert()

◆ reorder_sfc_morton()