# Graph (`dolfinx::graph`)

template<typename T>

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

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, typename = std::enable_if_t<std::is_same<std::vector<T>, std::decay_t<U>>::value && std::is_same<std::vector<std::int32_t>, std::decay_t<V>>::value>>

Construct adjacency list from arrays of data.

Parameters

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

template<typename X>

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

Copy constructor.

Move constructor.

Destructor.

Assignment operator.

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

Number of connections for given node.

Parameters

node[in] Node index

Returns

The number of outgoing links (edges) from the node

Get the links (edges) for given node.

Parameters

node[in] Node index

Returns

inline xtl::span<const T> links(int node) const

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

Parameters

node[in] Node index

Returns

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

template<typename U>

Construct a constant degree (valency) adjacency list.

A constant degree graph has the same number of edges for every node.

Parameters

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

Returns

template<typename T>

Construct adjacency list data for a problem with a fixed number of links (edges) for each node.

Parameters

array[in] Two-dimensional array of adjacency data where matrix(i, j) is the jth neighbor of the ith node

Returns

Adjacency list data and offset array

## Re-ordering

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://www.jstor.org/stable/2156090.

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

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.

Parameters
• imbalance[in] Imbalance tolerance. See ParMETIS manual for details.

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

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

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 dolfinx::graph::build

Tools for distributed graphs.

Todo:

Add a function that sends data to the ‘owner’

Functions

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

2. Source ranks for each node in the adjacency list

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

4. Owner rank of ghost nodes

std::vector<std::int64_t> compute_ghost_indices(MPI_Comm comm, const xtl::span<const std::int64_t> &owned_indices, const xtl::span<const std::int64_t> &ghost_indices, const xtl::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 remained 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 but 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 now 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.

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

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(const xtl::span<const std::int64_t> &local0_to_global, const xtl::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