Graph (dolfinx::graph)

Adjacency list

template<typename T>
class AdjacencyList

This class provides a static adjacency list data structure. It is commonly used to store directed graphs. For each node in the contiguous list of nodes [0, 1, 2, …, n) it stores the connected nodes. The representation is strictly local, i.e. it is not parallel aware.

Public Functions

inline explicit AdjacencyList(const std::int32_t n)

Construct trivial adjacency list where each of the n nodes is connected to itself

Parameters:

n – [in] Number of nodes

template<typename U, typename V>
inline AdjacencyList(U &&data, V &&offsets)

Construct adjacency list from arrays of data

Parameters:

  • data – [in] Adjacency array

  • offsets – [in] The index to the adjacency list in the data array for node i

template<typename X>
inline explicit AdjacencyList(const std::vector<X> &data)

Set all connections for all entities (T is a ‘2D’ container, e.g. a std::vector<<std::vector<std::size_t>>, std::vector<<std::set<std::size_t>>, etc).

Parameters:

data – [in] Adjacency list data, where std::next(data, i) points to the container of edges for node i.

AdjacencyList(const AdjacencyList &list) = default

Copy constructor.

AdjacencyList(AdjacencyList &&list) = default

Move constructor.

~AdjacencyList() = default

Destructor.

AdjacencyList &operator=(const AdjacencyList &list) = default

Assignment operator.

AdjacencyList &operator=(AdjacencyList &&list) = default

Move assignment operator.

inline bool operator==(const AdjacencyList &list) const

Equality operator

Returns:

True is the adjacency lists are equal

inline std::int32_t num_nodes() const

Get the number of nodes

Returns:

The number of nodes in the adjacency list

inline int num_links(std::size_t node) const

Number of connections for given node

Parameters:

node – [in] Node index

Returns:

The number of outgoing links (edges) from the node

inline std::span<T> links(std::size_t node)

Get the links (edges) for given node

Parameters:

node – [in] Node index

Returns:

Array of outgoing links for the node. The length will be AdjacencyList::num_links(node).

inline std::span<const T> links(std::size_t node) const

Get the links (edges) for given node (const version)

Parameters:

node – [in] Node index

Returns:

Array of outgoing links for the node. The length will be AdjacencyList:num_links(node).

inline const std::vector<T> &array() const

Return contiguous array of links for all nodes (const version)

inline std::vector<T> &array()

Return contiguous array of links for all nodes.

inline const std::vector<std::int32_t> &offsets() const

Offset for each node in array() (const version)

inline std::vector<std::int32_t> &offsets()

Offset for each node in array()

inline std::string str() const

Informal string representation (pretty-print)

Returns:

String representation of the adjacency list

Adjacency list builders

template<typename U>
AdjacencyList<typename std::decay_t<U>::value_type> dolfinx::graph::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:

  • data – [in] Adjacency array

  • degree – [in] The number of (outgoing) edges for each node

Returns:

An adjacency list

Re-ordering

std::vector<std::int32_t> dolfinx::graph::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:

graph – [in] The graph to compute a re-ordering for

Returns:

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

Partitioning

AdjacencyList<std::int32_t> dolfinx::graph::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:

  • comm – [in] MPI communicator that the graph is distributed across.

  • nparts – [in] Number of partitions to divide graph nodes into.

  • local_graph – [in] Node connectivity graph.

  • ghosting – [in] Flag to enable ghosting of the output node distribution.

Returns:

Destination rank for each input node.

graph::partition_fn dolfinx::graph::scotch::partitioner(scotch::strategy strategy = strategy::none, double imbalance = 0.025, int seed = 0)

Create a graph partitioning function that uses PT-SCOTCH.

Parameters:

  • strategy – [in] The SCOTCH strategy

  • imbalance – [in] The allowable imbalance (between 0 and 1). The smaller value the more balanced the partitioning must be.

  • seed – [in] Random number generator seed

Returns:

A graph partitioning function

graph::partition_fn dolfinx::graph::parmetis::partitioner(double imbalance = 1.02, std::array<int, 3> options = {1, 0, 5})

Create a graph partitioning function that uses ParMETIS.

Note

ParMETIS fails (crashes) if an MPI rank has no part of the graph. If necessary, the communicator should be split to avoid this situation.

Parameters:
graph::partition_fn dolfinx::graph::kahip::partitioner(int mode = 1, int seed = 1, double imbalance = 0.03, bool suppress_output = true)

Create a graph partitioning function that uses KaHIP.

Parameters:
Returns:

A KaHIP graph partitioning function with specified parameter options

Enumerations and typedefs

using dolfinx::graph::partition_fn = 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.

Param comm:

[in] MPI Communicator that the graph is distributed across

Param nparts:

[in] Number of partitions to divide graph nodes into

Param local_graph:

[in] Node connectivity graph

Param ghosting:

[in] Flag to enable ghosting of the output node distribution

Return:

Destination rank for each input node

enum class dolfinx::graph::scotch::strategy

PT-SCOTCH partitioning strategies.

See PT-SCOTCH documentation for details.

Values:

enumerator none

SCOTCH default strategy.

enumerator balance
enumerator quality
enumerator safety
enumerator speed
enumerator scalability

Functions for building distributed graphs

namespace build

Tools for distributed graphs

Todo:

Add a function that sends data to the ‘owner’

Functions

std::tuple<graph::AdjacencyList<std::int64_t>, std::vector<int>, std::vector<std::int64_t>, std::vector<int>> distribute(MPI_Comm comm, const graph::AdjacencyList<std::int64_t> &list, const graph::AdjacencyList<std::int32_t> &destinations)

Distribute adjacency list nodes to destination ranks.

The global index of each node is assumed to be the local index plus the offset for this rank.

Parameters:

  • comm – [in] MPI Communicator

  • list – [in] The adjacency list to distribute

  • destinations – [in] Destination ranks for the ith node in the adjacency list. The first rank is the ‘owner’ of the node.

Returns:

  1. Received adjacency list for this process

  2. Source ranks for each node in the adjacency list

  3. Original global index for each node in the adjacency list

  4. Owning rank of ghost nodes.

std::tuple<std::vector<std::int64_t>, std::vector<int>, std::vector<std::int64_t>, std::vector<int>> distribute(MPI_Comm comm, std::span<const std::int64_t> list, std::array<std::size_t, 2> shape, const graph::AdjacencyList<std::int32_t> &destinations)

Distribute fixed size nodes to destination ranks.

The global index of each node is assumed to be the local index plus the offset for this rank.

Parameters:

  • comm – [in] MPI Communicator

  • list – [in] Constant degree (valency) adjacency list. The array shape is (num_nodes, degree). Storage is row-major.

  • shape – [in] Shape (num_nodes, degree) of list.

  • destinations – [in] Destination ranks for the ith node (row) of list. The first rank is the ‘owner’ of the node.

Returns:

  1. Received adjacency list on this process. The array shape is (num_nodes, degree). Storage is row-major.

  2. Source rank for each received node.

  3. Original global index for each received node.

  4. Owning rank of ghost nodes.

std::vector<std::int64_t> compute_ghost_indices(MPI_Comm comm, std::span<const std::int64_t> owned_indices, std::span<const std::int64_t> ghost_indices, std::span<const int> ghost_owners)

Take a set of distributed input global indices, including ghosts, and determine the new global indices after remapping.

Each rank receive ‘input’ global indices [i0, i1, ..., i(m-1), im, / ..., i(n-1)], where the first m indices are owned by the caller and the remainder are ‘ghosts’ indices that are owned by other ranks.

Each rank assigns new global indices to its owned indices. The new index is the rank offset (scan of the number of indices owned by the lower rank processes, typically computed using MPI_Exscan with MPI_SUM), i.e. i1 -> offset + 1, i2 -> offset + 2, etc. Ghost indices are number by the remote owning processes. The function returns the new ghost global indices by retrieving the new indices from the owning ranks.

Parameters:

  • comm – [in] MPI communicator

  • owned_indices – [in] List of owned global indices. It should not contain duplicates, and these indices must not appear in owned_indices on other ranks.

  • ghost_indices – [in] List of ghost global indices.

  • ghost_owners – [in] The owning rank for each entry in ghost_indices.

Returns:

New global indices for the ghost indices.

std::vector<std::int64_t> compute_local_to_global(std::span<const std::int64_t> global, std::span<const std::int32_t> local)

Given an adjacency list with global, possibly non-contiguous, link indices and a local adjacency list with contiguous link indices starting from zero, compute a local-to-global map for the links. Both adjacency lists must have the same shape.

Parameters:

  • global – [in] Adjacency list with global link indices.

  • local – [in] Adjacency list with local, contiguous link indices.

Returns:

Map from local index to global index, which if applied to the local adjacency list indices would yield the global adjacency list.

std::vector<std::int32_t> compute_local_to_local(std::span<const std::int64_t> local0_to_global, std::span<const std::int64_t> local1_to_global)

Compute a local0-to-local1 map from two local-to-global maps with common global indices.

Parameters:

  • local0_to_global – [in] Map from local0 indices to global indices

  • local1_to_global – [in] Map from local1 indices to global indices

Returns:

Map from local0 indices to local1 indices