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 – Graph link (edge) type.

  • NodeData – 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_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:

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, 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:

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

  • node_weights – [in] Node weights. Each partition aims to have the same sum of node weights. If std::nullopt, nodes are treated as having equal weight.

  • edge_weights – [in] 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.

  • 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::speed, double imbalance = 0.025, int seed = 0)#

Create a graph partitioning function that uses PT-SCOTCH.

Note

The default strategy is strategy::speed rather than strategy::none (SCOTCH’s own default). For a mesh dual graph, strategy::speed has been measured to be around 20% faster with no measurable change in the number of cut edges. Note also that strategy::quality is slower and cuts more edges than strategy::none for such graphs.

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. Note that this does not affect the run time appreciably.

  • 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:

  • imbalance – [in] Imbalance tolerance. See ParMETIS manual for details (KarypisLab/ParMETIS).

  • options – [in] The ParMETIS option. See ParMETIS manual for details.

Returns:

A graph partitioning function.

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:

  • mode – [in] The KaHiP partitioning mode (see KaHIP/KaHIP)

  • seed – [in] The KaHiP random number generator seed

  • imbalance – [in] The allowable imbalance

  • suppress_output – [in] Suppresses KaHIP output if true

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>&, 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.

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 node_weights:

[in] Node weights, one entry per node in local_graph. If std::nullopt, nodes are treated as having equal weight.

Param edge_weights:

[in] Edge weights, one entry per edge in local_graph. If std::nullopt, edges are treated as having equal weight.

Param ghosting:

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

Return:

Destination rank(s) for each input node.

enum class dolfinx::graph::scotch::strategy : std::uint8_t#

PT-SCOTCH partitioning strategies.

See PT-SCOTCH documentation for details.

Values:

enumerator none#

SCOTCH’s own default strategy, which is not the DOLFINx default (see ::partitioner)

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 the ith node (row) in list is assumed to be i plus the offset for this rank, i.e. the number of nodes owned by lower-ranked processes.

Note

Collective.

Note

The neighbourhood communicator is built with MPI::compute_graph_edges_nbx, which discovers incoming edges from the outgoing edges alone via the scalable NBX consensus algorithm, keeping the communication pattern sparse. This is not free: it costs one or more non-blocking consensus rounds, so calling this function repeatedly (e.g. once per cell type) has a real cost.

Parameters:

  • comm – [in] MPI Communicator that list/destinations are distributed across.

  • list – [in] The adjacency list to distribute.

  • destinations – [in] Destination rank(s) for the ith node in list. The first rank is the ‘owner’ of the node; any further ranks receive it as a ghost.

Returns:

  1. Received adjacency list for this process. Nodes owned by this process come first, followed by any ghost nodes.

  2. Source rank of each node in (1), i.e. the rank it was sent from.

  3. Original global index of each node in (1).

  4. Owning rank of the ghost nodes among (1). This has one entry per ghost node &#8212; the trailing entries of (1) &#8212; not one entry per node of (1).

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 rows of a fixed-degree array to destination ranks.

The global index of the ith row of list is assumed to be i plus the offset for this rank, i.e. the number of rows owned by lower-ranked processes.

Note

Collective.

Note

The neighbourhood communicator is built with MPI::compute_graph_edges_nbx, which discovers incoming edges from the outgoing edges alone via the scalable NBX consensus algorithm, keeping the communication pattern sparse. This is not free: it costs one or more non-blocking consensus rounds, so calling this function repeatedly (e.g. once per cell type) has a real cost.

Parameters:

  • comm – [in] MPI Communicator that list/destinations are distributed across.

  • list – [in] Constant degree (valency) data, flattened row-major with shape shape.

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

  • destinations – [in] Destination rank(s) for the ith row of list. The first rank is the ‘owner’ of the row; any further ranks receive it as a ghost.

Returns:

  1. Received rows for this process, flattened row-major with shape (num_nodes, degree). Rows owned by this process come first, followed by any ghost rows.

  2. Source rank of each row in (1), i.e. the rank it was sent from.

  3. Original global index of each row in (1).

  4. Owning rank of the ghost rows among (1). This has one entry per ghost row &#8212; the trailing rows of (1) &#8212; not one entry per row of (1).

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, int num_threads)#

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.

  • num_threads – [in] Number of threads to use.

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