graph_toolbox.hpp File Reference

Functions and classes to build/represent sparse graphs or sparse patterns. More...

#include "../code_config.hpp"
#include "../containers/C2DContainer.hpp"
#include "../parallelization/omp_structure.hpp"
#include <set>
#include <vector>
#include <limits>
#include <cassert>
#include <algorithm>
#include <numeric>

Go to the source code of this file.

Classes
class	CCompressedSparsePattern< Index_t >
	A simple class to store adjacency information in a compressed format suitable for sparse matrix operations. If built for row-major storage the inner indices are column indices and the pattern should be used as (row,icol), otherwise as (col,irow). More...
struct	CCompressedSparsePattern< Index_t >::CInnerIter
	Type to allow range for loops over inner indices. More...
struct	GridColor< T >
	A way to represent one grid color that allows range-for syntax. More...
struct	DummyGridColor< T >
	A way to represent natural coloring {0,1,2,...,size-1} with zero overhead (behaves like looping with an integer index, after optimization...). More...
struct	DummyGridColor< T >::IteratorLikeInt

Typedefs
template<typename Index_t >
using	CEdgeToNonZeroMap = C2DContainer< unsigned long, Index_t, StorageType::RowMajor, 64, DynamicSize, 2 >
	Alias a type of container as the edge map class, this is a N by 2 container that maps the two sparse entries referenced by an edge (ij and ji) to two non zero entries of a sparse pattern.
using	CCompressedSparsePatternUL = CCompressedSparsePattern< su2uint >
using	CCompressedSparsePatternL = CCompressedSparsePattern< su2int >
using	CEdgeToNonZeroMapUL = CEdgeToNonZeroMap< su2uint >

Enumerations
enum class	ConnectivityType { ConnectivityType::FiniteVolume = 0 , ConnectivityType::FiniteElement = 1 }
	In FVM points are connected by the edges (faces) of the grid. In FEM, two points are connected if they have an element in common. More...

Functions
template<class Geometry_t , typename Index_t >
CCompressedSparsePattern< Index_t >	buildCSRPattern (Geometry_t &geometry, ConnectivityType type, Index_t fillLvl)
	Build a sparse pattern from geometry information, of type FVM or FEM, for a given fill-level. At fill-level N, the immediate neighbors of the points in level N-1 are also considered neighbors of the base point. The resulting pattern is that of A^{N+1} where A is the sparse matrix of immediate neighbors.
template<typename Index_t >
CCompressedSparsePattern< Index_t >	buildLowerPattern (const CCompressedSparsePattern< Index_t > &csr)
	Extract the strictly-lower part of a symmetric compressed sparse pattern. For each row i, the lower entries are those at positions [outerPtr[i], diagPtr[i]).
template<typename Index_t >
CCompressedSparsePattern< Index_t >	buildUpperPattern (const CCompressedSparsePattern< Index_t > &csr)
	Extract the strictly-upper part of a symmetric compressed sparse pattern. For each row i, the upper entries are those at positions (diagPtr[i], outerPtr[i+1]).
template<typename Index_t >
void	buildLUTransposeMaps (const CCompressedSparsePattern< Index_t > &pattern_l, const CCompressedSparsePattern< Index_t > &pattern_u, su2vector< Index_t > &l_to_u, su2vector< Index_t > &u_to_l)
	Build bijective maps between strictly-lower (L) and strictly-upper (U) non-zero entries that are each other's transposes. Requires a symmetric pattern. l_to_u[k_l] = k_u such that U-entry k_u is the transpose of L-entry k_l, and vice-versa.
template<class T = CCompressedSparsePatternUL, class Index_t = typename T::IndexType>
T	createNaturalColoring (Index_t numInnerIndexes)
	Create the natural coloring (equivalent to the normal sequential loop order) for a given number of inner indexes.
template<typename Color_t = unsigned char, size_t MaxColors = 255, size_t MaxMB = 128, class T >
T	colorSparsePattern (const T &pattern, size_t groupSize=1, bool includeOuterIdx=false, bool balanceColors=false, std::vector< Color_t > *indexColor=nullptr)
	Color contiguous groups of outer indices of a sparse pattern such that within each color, any two groups do not have inner indices in common.
template<class SparsePattern >
su2double	coloringEfficiency (const SparsePattern &coloring, int numThreads, int chunkSize)
	Computes the efficiency of a grid coloring for given number of threads and chunk size.
template<class T >
T	computeLevels (const T &pattern)
	Compute the levels for the lower part of a sparse pattern. For example, corresponding to the dependencies of forward substitution.

Detailed Description

Functions and classes to build/represent sparse graphs or sparse patterns.

Author

P. Gomes

Version

8.5.0 "Harrier"

SU2 Project Website: https://su2code.github.io

The SU2 Project is maintained by the SU2 Foundation (http://su2foundation.org)

Copyright 2012-2026, SU2 Contributors (cf. AUTHORS.md)

SU2 is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

SU2 is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with SU2. If not, see http://www.gnu.org/licenses/.