dolfinx::graph Namespace Reference

Graph data structures and algorithms. More...

Namespaces
	build
	Tools for distributed graphs.
	kahip
	Interfaces to KaHIP parallel partitioner.
	scotch
	Interface to SCOTCH-PT.

Classes
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. More...

Typedefs
using	partition_fn = std::function< graph::AdjacencyList< std::int32_t >(MPI_Comm comm, int nparts, const AdjacencyList< std::int64_t > &local_graph, std::int32_t num_ghost_nodes, bool ghosting)>
	Signature of functions for computing the parallel partitioning of a distributed graph. More...

Functions
template<typename T >
auto	create_adjacency_data (const xt::xtensor< T, 2 > &array)
	Construct adjacency list data for a problem with a fixed number of links (edges) for each node. More...
template<typename T , typename U >
AdjacencyList< T >	build_adjacency_list (U &&data, int degree)
	Construct an adjacency list from array of data for a graph with constant degree (valency). A constant degree graph has the same number of edges for every node. More...
std::vector< int >	compute_cuthill_mckee (const AdjacencyList< std::int32_t > &graph, bool reverse=false)
	This class computes graph re-orderings. It uses Boost Graph. More...
std::vector< int >	compute_cuthill_mckee (const std::set< std::pair< std::size_t, std::size_t >> &edges, std::size_t size, bool reverse=false)
	Compute re-ordering (map[old] -> new) using Cuthill-McKee algorithm.
AdjacencyList< std::int32_t >	partition_graph (const MPI_Comm comm, int nparts, const AdjacencyList< std::int64_t > &local_graph, std::int32_t num_ghost_nodes, bool ghosting)
	Partition graph across processes using the default graph partitioner. More...

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 dolfinx::graph::partition_fn = typedef std::function<graph::AdjacencyList<std::int32_t>( MPI_Comm comm, int nparts, const AdjacencyList<std::int64_t>& local_graph, std::int32_t num_ghost_nodes, bool ghosting)>

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

Parameters

comm	MPI Communicator that the graph is distributed across
nparts	Number of partitions to divide graph nodes into
local_graph	Node connectivity graph
num_ghost_nodes	Number of graph nodes appearing in local_graph that are owned on other processes
ghosting	Flag to enable ghosting of the output node distribution

Returns

Destination rank for each input node

Function Documentation

build_adjacency_list()

template<typename T , typename U >

AdjacencyList<T> dolfinx::graph::build_adjacency_list	(	U &&	data,
		int	degree
	)

Construct an adjacency list from array of data for a graph with constant degree (valency). A constant degree graph has the same number of edges for every node.

Parameters

[in]	data	Adjacency array
[in]	degree	The number of (outgoing) edges for each node

Returns

An adjacency list

compute_cuthill_mckee()

std::vector< int > dolfinx::graph::compute_cuthill_mckee	(	const AdjacencyList< std::int32_t > &	graph,
		bool	reverse = false
	)

This class computes graph re-orderings. It uses Boost Graph.

Compute re-ordering (map[old] -> new) using Cuthill-McKee algorithm

create_adjacency_data()

template<typename T >

auto dolfinx::graph::create_adjacency_data

(

const xt::xtensor< T, 2 > &

array

)

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

Parameters

[in]

array

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

partition_graph()

graph::AdjacencyList< std::int32_t > dolfinx::graph::partition_graph	(	const MPI_Comm	comm,
		int	nparts,
		const AdjacencyList< std::int64_t > &	local_graph,
		std::int32_t	num_ghost_nodes,
		bool	ghosting
	)

Partition graph across processes using the default graph partitioner.

Parameters

comm	MPI Communicator that the graph is distributed across
nparts	Number of partitions to divide graph nodes into
local_graph	Node connectivity graph
num_ghost_nodes	Number of graph nodes appearing in local_graph that are owned on other processes
ghosting	Flag to enable ghosting of the output node distribution

Returns

Destination rank for each input node