Graph (dolfinx::graph)

Adjacency list

template<typename LinkData, typename NodeData = std::nullptr_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.

The link (edge) type is template parameter, which allows link data to be stored, e.g. a pair with the target node index and the link weight.

Node data can also be stored.

Template Parameters:

  • LinkData_t – Graph link (edge) type.

  • NodeData_t – Data type for graph node data.

Public Types

using link_type = LinkData

Adjacency list link (edge) type.

using node_data_type = NodeData

Adjacency list node data type.

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 link (edge) data and offsets.

Parameters:

  • data – [in] Adjacency lost data array.

  • offsets – [in] Offsets into data for each node, where offsets[i] is the first index in data for node i. The last index in offsets is the equal to the length of data. array for node i.

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

Construct adjacency list from arrays of link (edge) data, offsets, and node data.

Parameters:

  • data – [in] Adjacency lost data array.

  • offsets – [in] Offsets into data for each node, where offsets[i] is the first index in data for node i. The last index in offsets is the equal to the length of data.

  • node_data – [in] Node data array where node_data[i] is the data attached to 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 links (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<LinkData> 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 LinkData> 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<LinkData> &array() const

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

inline std::vector<LinkData> &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 const std::optional<std::vector<NodeData>> &node_data() const

Return node data (if present), where node_data()[i] is the data for node i (const version).

inline std::optional<std::vector<NodeData>> &node_data()

Return node data (if present), where node_data()[i] is the data for node i.

inline std::string str() const

Informal string representation (pretty-print).

Returns:

String representation of the adjacency list.

Adjacency list builders

template<typename V = std::nullptr_t, typename U>
AdjacencyList<typename std::decay_t<U>::value_type, V> 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 links (edges) for every node.

Parameters:

  • data – [in] Adjacency array.

  • degree – [in] Number of (outgoing) links 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.

Warning

doxygenfunction: Cannot find function “dolfinx::graph::scotch::partitioner” in doxygen xml output for project “DOLFINx” from directory: ../xml/

Warning

doxygenfunction: Cannot find function “dolfinx::graph::parmetis::partitioner” in doxygen xml output for project “DOLFINx” from directory: ../xml/

Warning

doxygenfunction: Cannot find function “dolfinx::graph::kahip::partitioner” in doxygen xml output for project “DOLFINx” from directory: ../xml/

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

Warning

doxygenenum: Cannot find enum “dolfinx::graph::scotch::strategy” in doxygen xml output for project “DOLFINx” from directory: ../xml/

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