dolfinx.graph#

Graph representations and operations on graphs.

Functions

`adjacencylist`(data[, offsets])	Create an `AdjacencyList` for int32 or int64 datasets.
`comm_graph`(map[, root])	Build a parallel communication graph from an index map.
`comm_graph_data`(graph)	Build communication graph data for use with NetworkX.
`comm_to_json`(graph)	Build and JSON string from a communication graph.
`distribute`(comm, list, destinations)	Distribute rows of a fixed-degree array to destination ranks.
`partition`(comm, nparts, local_graph, *[, ...])	Partition the nodes of a graph into parts.
`partitioner`()	Create the default graph partitioner, also used by mesh creation.
`reorder_rcm`(graph)	Re-order a graph using the reverse Cuthill-McKee algorithm.

Classes

`AdjacencyList`(g)	Adjacency list representation of a graph.
`GeometricPartitioner`(partitioner)	A partitioner using positions, without graph edges or ghosting.
`GraphPartitioner`(partitioner)	A graph partitioner for direct calls and mesh creation.
`HybridPartitioner`(partitioner)	A partitioner using both graph edges and node positions.

class dolfinx.graph.AdjacencyList(g: AdjacencyList_int32 | AdjacencyList_int64 | AdjacencyList_int_sizet_int8__int32_int32)[source]#

Bases: Generic[Index]

Adjacency list representation of a graph.

Creates a Python wrapper for the exported adjacency list class.

Note

Do not use this constructor directly. Instead use adjacencylist().

Parameters:: g – The underlying cpp instance that this object will wrap.

property array: ndarray[tuple[Any, ...], dtype[Index]]#

Array representation of the adjacency list.

Note

This is available only for adjacency lists with no additional link (edge) data.

Returns:: Flattened array representation of the adjacency list.

links(node: int) → ndarray[tuple[Any, ...], dtype[Index]][source]#

Retrieve the links of a node.

Note

This is available only for adjacency lists with no additional link (edge) data.

Parameters:: node – Node to retrieve the connectivity of.
Returns:: Neighbors of the node.

property num_nodes: int32#

Number of nodes in the adjacency list.

Returns:: Number of nodes.

property offsets: ndarray[tuple[Any, ...], dtype[int32]]#

Offsets for each node in the array().

Returns:: Array of indices with shape (num_nodes+1).

class dolfinx.graph.GeometricPartitioner(partitioner: GeometricPartitioner)[source]#

Bases: object

A partitioner using positions, without graph edges or ghosting.

Wrap a native handle. Use the partitioner factories instead.

class dolfinx.graph.GraphPartitioner(partitioner: GraphPartitioner)[source]#

Bases: object

A graph partitioner for direct calls and mesh creation.

Wrap a native handle. Use the partitioner factories instead.

class dolfinx.graph.HybridPartitioner(partitioner: HybridPartitioner)[source]#

Bases: object

A partitioner using both graph edges and node positions.

Wrap a native handle. Use the partitioner factories instead.

dolfinx.graph.adjacencylist(data: ndarray[tuple[Any, ...], dtype[Index]], offsets: ndarray[tuple[Any, ...], dtype[int32]] | None = None) → AdjacencyList[Index][source]#

Create an AdjacencyList for int32 or int64 datasets.

Parameters:

data – The adjacency array. If the array is one-dimensional, offsets should be supplied. If the array is two-dimensional the number of edges per node is the second dimension.
offsets – The offsets array with the number of edges per node.

Returns:

An adjacency list.

dolfinx.graph.comm_graph(map: IndexMap, root: int = 0) → AdjacencyList[source]#

Build a parallel communication graph from an index map.

The communication graph is a directed graph that represents the communication pattern for a distributed array, and specifically the forward scatter operation where the values for owned indices are sent to ghosting ranks. The graph is built from an index map, which describes the local and ghosted indices of the array.

Edges in the graph represent communication from the owning rank to ranks that ghost the data. The edge data holds the (0) target node, (1) edge weight, and (2) an indicator for whether the sending and receiving ranks share memory (local==1) or if the ranks do not share memory (local==0). The node data holds the local size (number of owned indices) and the number of ghost indices.

The graph can be processed using comm_graph() to build data structures that can be used to build a NetworkX directed graph.

Note

This function is collective across all MPI ranks. The communication graph is returned on the root rank. All other ranks return an empty graph

Parameters:

map – Index map to build the communication graph from.
root – Rank that will return the communication graph. Other ranks return an empty graph.

Returns:

An adjacency list representing the communication graph.

dolfinx.graph.comm_graph_data(graph: AdjacencyList) → tuple[list[tuple[int, int, dict[str, int]]], list[tuple[int, dict[str, int]]]][source]#

Build communication graph data for use with NetworkX.

Parameters:: graph – Communication graph to build data from. Normally created by comm_graph().
Returns:: A tuple of two lists. The first list contains the edge data, where an edge is a (nodeID_0, nodeID_1, dict) tuple, where dict holds edge data. The second list hold node data, where a node is a (nodeID, dict) tuple, where dict holds node data.

dolfinx.graph.comm_to_json(graph: AdjacencyList) → str[source]#

Build and JSON string from a communication graph.

The JSON string can be used to construct a NetworkX graph. This is helpful for cases where a simulation is executed and the graph data is written to file as a JSON string for later analysis.

Parameters:: graph – The communication graph to convert. Normally created by calling comm_graph().
Returns:: A JSON string representing the communication graph.

dolfinx.graph.distribute(comm: Comm, list: ndarray[tuple[Any, ...], dtype[int64]], destinations: AdjacencyList[int32]) → tuple[ndarray[tuple[Any, ...], dtype[int64]], ndarray[tuple[Any, ...], dtype[int32]], ndarray[tuple[Any, ...], dtype[int64]], ndarray[tuple[Any, ...], dtype[int32]]][source]#

Distribute rows of a fixed-degree array to destination ranks.

Uses a scalable neighbourhood exchange: send/receive ranks are discovered via NBX consensus rather than an all-to-all, keeping communication sparse as the communicator grows, at the cost of at least one non-blocking consensus round.

Parameters:

comm – MPI communicator that list/destinations are distributed across.
list – Rows to distribute, with shape (num_nodes, degree). The global index of row i is assumed to be i plus the number of rows owned by lower-ranked processes.
destinations – 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:

Tuple of (received rows, source rank of each received row, original global index of each received row, owning rank of the ghost rows). The last entry has one entry per ghost row – the trailing rows of the first entry – not one entry per received row.

dolfinx.graph.partition(comm: Comm, nparts: int, local_graph: AdjacencyList[int64], *, partitioner: GraphPartitioner | None = None, node_weights: ndarray[tuple[Any, ...], dtype[int32]] | None = None, edge_weights: ndarray[tuple[Any, ...], dtype[int32]] | None = None, ghosting: bool = False) → AdjacencyList[int32][source]#

Partition the nodes of a graph into parts.

Applies a partitioner to a graph, e.g. the dual graph of a mesh from build_dual_graph. create_mesh partitions a mesh itself; this is for partitioning a graph directly, for instance to build the subdomains of a domain decomposition method. Passing MPI.COMM_SELF partitions a graph held on one process into nparts parts without communication.

Note

Collective across comm, and requires DOLFINx to be built with a graph partitioner (ParMETIS, SCOTCH or KaHIP).

Parameters:

comm – MPI communicator that local_graph is distributed across.
nparts – Number of parts to partition the graph into.
local_graph – Graph to partition, with the nodes owned by this process as its nodes and global node indices as its links.
partitioner – Partitioner to apply. The default partitioner, which is the one create_mesh uses, is applied if None.
node_weights – Weight of each node, which a partitioner may use to balance the parts.
edge_weights – Weight of each edge, which a partitioner may use to weigh the cost of cutting it.
ghosting – Return, for each node, the parts that share a node with it in addition to the part that owns it.

Returns:

Part(s) of each node of local_graph. The first entry for a node is the part that owns it; any further entries are parts that ghost it, and appear only if ghosting is True.

dolfinx.graph.partitioner() → GraphPartitioner[source]#: Create the default graph partitioner, also used by mesh creation.

dolfinx.graph.reorder_rcm(graph: AdjacencyList[int32]) → ndarray[tuple[Any, ...], dtype[int32]][source]#

Re-order a graph using the reverse Cuthill-McKee algorithm.

Pass it as create_mesh’s reorder_fn argument; it is also the default cell reordering.

Parameters:: graph – Graph to re-order.
Returns:: New index of each node, i.e. entry i is the new index of node i.