Namespaces
namespace	spfa

Classes
class	Vertex
	Graph node with an adjacency list; the vertex type the graph algorithms operate on. More...

Functions
index_t	bfs (Graph &aGraph, Vertex *aStart=nullptr)
index_t	bfs (Graph &aGraph)
	Alternative implementation that also handles disconnected graphs by finding the maximum width across all connected components.
void	clear (Cell< Vertex * > &aGraph)
	tidy up a graph
proc_t	dfs (Graph &aGraph)
void	dfs_from_start (Graph &aGraph, Vertex *aStart)
index_t	find_connected_partitions (Graph &aGraph)
Vertex *	find_pseudo_peripheral_node (Graph &aGraph, Vertex *aStart)
Vertex *	find_pseudo_peripheral_vertex (Graph &aGraph, Vertex *aStart=nullptr)
	Finds a pseudo-peripheral vertex in the graph.
void	metis_nd (Graph &aGraph)
	Performs nested dissection ordering on the graph using METIS_NodeND.
void	metis_ndp (Graph &aGraph, const uint aNumPartitions)
	Performs nested dissection ordering with partitioning using METIS_NodeNDP.
void	metis_partition (Graph &aGraph, const uint aNumPartitions, const bool aForceContinuousPartitions, Vector< proc_t > *aPartitions)
string	metis_status (const int aStatus)
Vertex *	multibfs (Cell< Vertex * > &aGraph, const proc_t aOwnerSubset)
void	parmetis_nd (Graph &aGraph)
void	ptscotch_nd (Graph &aGraph)
void	scotch_nd (Graph &aGraph)
void	scotch_partition (Graph &aGraph, const uint aNumPartitions)
void	sort (Graph &aGraph)
bool	spfa_difference_constraints (const index_t aNumVertices, const Cell< index_t > &aArcTails, const Cell< index_t > &aArcHeads, const Cell< int64_t > &aArcWeights, Cell< int64_t > &aTheta, Cell< index_t > &aNegativeCycle)
	Feasibility solver for a system of difference constraints.
void	symrcm (Graph &aGraph, Vertex *aStart=nullptr)
	Performs Reverse Cuthill-McKee (RCM) ordering on the graph.
void	apply_rcm_permutation (Graph &aGraph, const Cell< index_t > &aPermutation)
	Applies the RCM permutation to reorder the graph vertices.
template<typename T>
void	apply_graph_permutation (Graph &aGraph, const Vector< T > &aPermutation)
template<typename T>
void	build_graph_adjacency (Graph &aGraph, Vector< T > &aVertices, Vector< T > &aEdges)
void	block_distribution (Graph &aGraph, const proc_t aCommSize)
	assign owners to an ownerless graph in contiguous blocks of graph order: the first aCommSize - ( N mod aCommSize ) ranks take N / aCommSize vertices, the remaining ranks one more ( the split DistMatrix uses for its rows ).
template<typename T>
void	build_pargraph_adjacency (Graph &aGraph, Vector< T > &aDistribution, Cell< Vector< T > > &aVertices, Cell< Vector< T > > &aEdges)

Function Documentation

◆ apply_graph_permutation()

template<typename T>

void belfem::graph::apply_graph_permutation	(	Graph &	aGraph,
		const Vector< T > &	aPermutation )

◆ apply_rcm_permutation()

void belfem::graph::apply_rcm_permutation	(	Graph &	aGraph,
		const Cell< index_t > &	aPermutation )

Applies the RCM permutation to reorder the graph vertices.

Updates the index of each vertex according to the new ordering.

Parameters

aGraph	Cell containing all vertices in the graph
aPermutation	The permutation vector from symrcm

◆ bfs() [1/2]

index_t belfem::graph::bfs ( Graph & aGraph )

Alternative implementation that also handles disconnected graphs by finding the maximum width across all connected components.

Parameters

aGraph Cell containing all vertices in the graph

Returns: The maximum width across all connected components

◆ bfs() [2/2]

index_t belfem::graph::bfs	(	Graph &	aGraph,
		Vertex *	aStart = nullptr )

◆ block_distribution()

void belfem::graph::block_distribution	(	Graph &	aGraph,
		const proc_t	aCommSize )

inline

assign owners to an ownerless graph in contiguous blocks of graph order: the first aCommSize - ( N mod aCommSize ) ranks take N / aCommSize vertices, the remaining ranks one more ( the split DistMatrix uses for its rows ).

A working distribution for the parallel nested-dissection wrappers, which need every vertex owned before build_pargraph_adjacency(); not a partition. Two loops, never k / ( N / P ): that quotient is zero when N < P.

◆ build_graph_adjacency()

template<typename T>

void belfem::graph::build_graph_adjacency	(	Graph &	aGraph,
		Vector< T > &	aVertices,
		Vector< T > &	aEdges )

◆ build_pargraph_adjacency()

template<typename T>

void belfem::graph::build_pargraph_adjacency	(	Graph &	aGraph,
		Vector< T > &	aDistribution,
		Cell< Vector< T > > &	aVertices,
		Cell< Vector< T > > &	aEdges )

◆ clear()

void belfem::graph::clear ( Cell< Vertex * > & aGraph )

tidy up a graph

◆ dfs()

proc_t belfem::graph::dfs ( Graph & aGraph )

◆ dfs_from_start()

void belfem::graph::dfs_from_start	(	Graph &	aGraph,
		Vertex *	aStart )

◆ find_connected_partitions()

index_t belfem::graph::find_connected_partitions ( Graph & aGraph )

◆ find_pseudo_peripheral_node()

Vertex * belfem::graph::find_pseudo_peripheral_node	(	Graph &	aGraph,
		Vertex *	aStart )

◆ find_pseudo_peripheral_vertex()

Vertex * belfem::graph::find_pseudo_peripheral_vertex	(	Graph &	aGraph,
		Vertex *	aStart = nullptr )

Finds a pseudo-peripheral vertex in the graph.

A pseudo-peripheral vertex is one that has a large eccentricity (distance to farthest vertex). This implementation uses the algorithm that repeatedly performs BFS to find vertices with increasing eccentricity until no further improvement is found.

Parameters

aGraph	Cell containing all vertices in the graph
aStart	Starting vertex for the search (if nullptr, uses first vertex in aGraph)

Returns: Pointer to a pseudo-peripheral vertex

◆ metis_nd()

void belfem::graph::metis_nd ( Graph & aGraph )

Performs nested dissection ordering on the graph using METIS_NodeND.

This algorithm reorders vertices to minimize fill-in during sparse matrix factorization, producing a shallow elimination tree that is optimal for direct solvers like STRUMPACK.

The graph is reordered in-place. After calling this function:

vertex->index() contains the new (permuted) index
The graph Cell is sorted by the new indices
vertex->id() is not touched; record the original index yourself before the call if you need the permutation

Parameters

aGraph Cell containing all vertices in the graph (will be reordered)

Note: Requires BELFEM_METIS to be defined ( set by USE_METIS ); Without METIS this raises BELFEM_ERROR. There is no symrcm fallback.

◆ metis_ndp()

void belfem::graph::metis_ndp	(	Graph &	aGraph,
		const uint	aNumPartitions )

Performs nested dissection ordering with partitioning using METIS_NodeNDP.

This variant creates a specified number of top-level partitions before applying nested dissection, which can produce better orderings for parallel factorization with many processors.

STRUMPACK documentation suggests this often works better than standard NodeND for certain problem types (use –sp_enable_METIS_NodeNDP).

The graph is reordered in-place. After calling this function:

vertex->index() contains the new (permuted) index
The graph Cell is sorted by the new indices
vertex->id() is not touched; record the original index yourself before the call if you need the permutation

Parameters

aGraph	Cell containing all vertices (will be reordered)
aNumPartitions	Number of top-level partitions

Note: Requires BELFEM_METIS to be defined ( set by USE_METIS ); without it, BELFEM_ERROR

◆ metis_partition()

void belfem::graph::metis_partition	(	Graph &	aGraph,
		const uint	aNumPartitions,
		const bool	aForceContinuousPartitions,
		Vector< proc_t > *	aPartitions )

◆ metis_status()

string belfem::graph::metis_status ( const int aStatus )

◆ multibfs()

Vertex * belfem::graph::multibfs	(	Cell< Vertex * > &	aGraph,
		const proc_t	aOwnerSubset )

◆ parmetis_nd()

void belfem::graph::parmetis_nd ( Graph & aGraph )

◆ ptscotch_nd()

void belfem::graph::ptscotch_nd ( Graph & aGraph )

◆ scotch_nd()

void belfem::graph::scotch_nd ( Graph & aGraph )

◆ scotch_partition()

void belfem::graph::scotch_partition	(	Graph &	aGraph,
		const uint	aNumPartitions )

◆ sort()

void belfem::graph::sort ( Graph & aGraph )

◆ spfa_difference_constraints()

bool belfem::graph::spfa_difference_constraints	(	const index_t	aNumVertices,
		const Cell< index_t > &	aArcTails,
		const Cell< index_t > &	aArcHeads,
		const Cell< int64_t > &	aArcWeights,
		Cell< int64_t > &	aTheta,
		Cell< index_t > &	aNegativeCycle )

Feasibility solver for a system of difference constraints.

theta( head( a ) ) - theta( tail( a ) ) <= weight( a )

for every arc a, using the queue-based Bellman-Ford-Moore algorithm (SPFA), warm-started from a BFS spanning forest ( theta( head ) = theta( tail ) + w along tree arcs ) so that only off-tree violations need relaxing. Infeasibility is detected by amortized periodic scans of the predecessor graph; only a strictly negative predecessor cycle is accepted as proof.

Vertices are addressed by index in [ 0, aNumVertices ); vertices that appear in no arc are left untouched at theta = 0. The returned theta is A feasible solution ( difference constraints are shift-invariant ), not distances from a source.

Parameters

aNumVertices	size of the vertex index space
aArcTails	tail vertex of each arc
aArcHeads	head vertex of each arc
aArcWeights	signed weight of each arc
aTheta	output: feasible potentials, sized to aNumVertices ( valid only if return is true )
aNegativeCycle	output: if infeasible, the arc indices of one negative cycle, in cycle order

Returns: true if the system is feasible, false if a negative cycle exists ( certificate in aNegativeCycle )

◆ symrcm()

void belfem::graph::symrcm	(	Graph &	aGraph,
		Vertex *	aStart = nullptr )

Performs Reverse Cuthill-McKee (RCM) ordering on the graph.

This algorithm reorders vertices to reduce the bandwidth of the adjacency matrix. The graph is reordered in-place.

Parameters

aGraph	Cell containing all vertices in the graph (will be reordered)
aStart	Starting vertex for the algorithm (if nullptr, uses pseudo-peripheral vertex)

Namespaces

Classes

Functions

Function Documentation

◆ apply_graph_permutation()

◆ apply_rcm_permutation()

◆ bfs() [1/2]

◆ bfs() [2/2]

◆ block_distribution()

◆ build_graph_adjacency()

◆ build_pargraph_adjacency()

◆ clear()

◆ dfs()

◆ dfs_from_start()

◆ find_connected_partitions()

◆ find_pseudo_peripheral_node()

◆ find_pseudo_peripheral_vertex()

◆ metis_nd()

◆ metis_ndp()

◆ metis_partition()

◆ metis_status()

◆ multibfs()

◆ parmetis_nd()

◆ ptscotch_nd()

◆ scotch_nd()

◆ scotch_partition()

◆ sort()

◆ spfa_difference_constraints()

◆ symrcm()