DOLFINx 0.9.0
DOLFINx C++ interface
Loading...
Searching...
No Matches
dolfinx::graph Namespace Reference

Graph data structures and algorithms. More...

Namespaces

namespace  build
 
namespace  kahip
 Interfaces to KaHIP parallel partitioner.
 

Classes

class  AdjacencyList
 

Typedefs

using partition_fn
 Signature of functions for computing the parallel partitioning of a distributed graph.
 

Functions

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

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]commMPI Communicator that the graph is distributed across
[in]npartsNumber of partitions to divide graph nodes into
[in]local_graphNode connectivity graph
[in]ghostingFlag to enable ghosting of the output node distribution
Returns
Destination rank for each input node

Function Documentation

◆ 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]commMPI communicator that the graph is distributed across.
[in]npartsNumber of partitions to divide graph nodes into.
[in]local_graphNode connectivity graph.
[in]ghostingFlag to enable ghosting of the output node distribution.
Returns
Destination rank for each input node.

◆ regular_adjacency_list()

template<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 > 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
[in]dataAdjacency array
[in]degreeThe number of (outgoing) edges 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]graphThe graph to compute a re-ordering for
Returns
Reordering array map, where map[i] is the new index of node i