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)
	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.
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

)

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