Dune::Assembler::Experimental Namespace Reference

Classes
class	Barrier
	A barrier primitive for multi-threaded code. More...
class	ColoredRangeExecutor
	Utility for implementing parallel algorithms based on colored ranges. More...

Functions
template<class Range >
static auto	rangeSegment (Range &range, std::size_t i, std::size_t n)
	Split range into uniform segments.
template<class Adjacency , class SeedNodesContainer >
auto	computeColoring (const Adjacency &adjacency, SeedNodesContainer &&seedNodes)
	Compute a graph coloring from neighboring information.
template<class Adjacency , class T >
auto	computeColoring (const Adjacency &adjacency, std::initializer_list< T > seedIndices)
	Compute a graph coloring from neighboring information.
template<class Adjacency >
auto	computeColoring (const Adjacency &adjacency)
	Compute a graph coloring from neighboring information.
template<class CliqueList >
auto	cliqueListToAdjacency (const CliqueList &cliqueList, std::size_t size, bool verbose=false)
	Compute an adjacency list from a clique list.
template<class GridView , class ElementMapper , class size_type = uint32_t>
auto	vertexBasedElementAdjacency (const GridView &gridView, const ElementMapper &elementMapper, bool verbose=false)
	Compute a vertex based adjacency list.
template<class GridView , class size_type = uint32_t>
auto	vertexBasedElementAdjacency (const GridView &gridView, bool verbose=false)
	Compute a vertex based element adjacency list.
template<class GridView , class SubEntityLayout , class ElementMapper , class size_type = uint32_t>
auto	subEntityBasedElementAdjacency (const GridView &gridView, const SubEntityLayout &subEntityLayout, const ElementMapper &elementMapper)
	Compute a layout based adjacency list.
template<class GridView , class SubEntityLayout , class size_type = uint32_t>
auto	subEntityBasedElementAdjacency (const GridView &gridView, const SubEntityLayout &subEntityLayout)
	Compute a layout based element adjacency list.
template<class GridView , class size_type >
auto	coloredElementRange (const GridView &gridView, const std::vector< size_type > &coloring)
	Compute a colored range of the elements in the gridView from coloring.
template<class GridView , class size_type = uint32_t>
auto	coloredElementRange (const GridView &gridView, bool verbose=false)
	Compute a colored range of the elements in the gridView.
template<class ElementRange , class Basis >
bool	checkOverlapFree (const ElementRange &elementRange, const Basis &basis)
	Check if given element range is overlap free.

Function Documentation

checkOverlapFree()

template<class ElementRange , class Basis >

bool Dune::Assembler::Experimental::checkOverlapFree	(	const ElementRange &	elementRange,
		const Basis &	basis
	)

Check if given element range is overlap free.

The function exists for debugging purposes: It checks if the given elementRange is overlap free in the sense that for any pair of elements in the range, the set of associated global indices in the given basis is disjoint. The function will print out diagnostic information if an overlap is detected.

Returns

True is no overlap is detected, otherwise false.

cliqueListToAdjacency()

template<class CliqueList >

auto Dune::Assembler::Experimental::cliqueListToAdjacency	(	const CliqueList &	cliqueList,
		std::size_t	size,
		bool	verbose = false
	)

Compute an adjacency list from a clique list.

This will construct the adjacency list of the graph induced by the clique list, i.e. the minimal graph containing all given cliques. Notice that a clique of a graph is a complete subgraph. The clique list is provided as a range of ranges: Each entry in the outer range models a clique. Each clique is represented by a range of vertex indices. For a given range cliqueList the resulting graph will have an edge (i,j) iff there is a clique k, such that cliqueList[k] contains i and j.

The created graph is returned as adjacency list in the form of a range of ranges.

If the verbose mode is enabled, this computes and prints out the number of the largest clique which is a lower bound for the chromatic number of the graph (i.e. the minimal number of colores required in a coloring).

Parameters

cliqueList	Range of cliques to be added to the graph
size	Number of nodes in the graph.
verbose	Flag to enable verbose mode (default=false)

coloredElementRange() [1/2]

template<class GridView , class size_type = uint32_t>

auto Dune::Assembler::Experimental::coloredElementRange	(	const GridView &	gridView,
		bool	verbose = false
	)

Compute a colored range of the elements in the gridView.

This is a short cut that subsequently computes a vertex based adjacency list for the elements in the grid view, a coloring for the induced element graph, and finally the resulting colored element range of the grid view. The exact return type is explained in the documentation of coloredElementRange(). If verbose mode is used, timing of each operation are printed to std::cout.

This colors the element graph \(G\), where two elements are connected if they share a vertex. Notice that the resulting coloring is quasi-optimal in the sense that the number of used colors \(C\) is bounded by \(C \leq 1+\chi(G)2^d\) where \(\chi(G)\) is the chromatic number (i.e. the optimal number of colors):

Assume that the number of colors used by the algorithm is \(C\). By construction the algorithm guarantees \( C \leq 1+\Delta(G) \) where \(\Delta(G)\) is the maximal nodal degree of \(G\). Now let \(k\) the maximal number of elements sharing a vertex. Then \(k\) is a lower bound for the clique number \(\omega(G)\) (i.e. the size of largest fully connected subgraph) and thus for the chromatic number \(\chi(G)\) (i.e. the optimal number of colors). Each element has at most \(2^d\) vertices and thus at most \(k2^d\) neighbors, i.e. we have \(\Delta(G) <= k2^d\). Finally we arrive at \(k \leq \omega(G) \leq \chi(G) \leq C \leq \Delta(G)+1 \leq 1+k2^d\) and hence \(C \leq 1+\chi(G)2^d \leq \chi(G)(2^d+1)\).

Notice that even for planar 2d grids the element graph is not planar and thus we may need more than 4 colors.

Template Parameters

size_type

Type used to store indices (default=uint32_t)

Parameters

gridView	The grid view to decompose into a colored range
verbose	Flag to enable verbose mode (default=false)

Returns

Colored range of elements into chucks represented by std::vector<ElementRange>

coloredElementRange() [2/2]

template<class GridView , class size_type >

auto Dune::Assembler::Experimental::coloredElementRange	(	const GridView &	gridView,
		const std::vector< size_type > &	coloring
	)

Compute a colored range of the elements in the gridView from coloring.

This computes a vector containing one element range per color. Each element range is a range all elements from the gridView that share the respective color. Hence the outer size is the number of used colors, while the sum of the inner sizes is the total number of elements in the gridView. Internally each element range is stored as std::vector<EntitySeed> and stored EntitySeeds are transformed to Entities on the fly during traversal.

Parameters

gridView	GridView whose elements should be distributed
coloring	A std::vector<size_type> representing a coloring as provided by computeColoring()

Returns

Colored range of elements into chucks represented by std::vector<ElementRange>

computeColoring() [1/3]

template<class Adjacency >

auto Dune::Assembler::Experimental::computeColoring

(

const Adjacency &

adjacency

)

Compute a graph coloring from neighboring information.

This computes a coloring for a set of nodes with given neighboring relation using a simple greedy advancing front algorithm.

The input graph is represented as follows: Each node corresponds to an index. These indices are zero-based, consecutive, and stored as size_type. The adjacency of the graph is passed as an adjacency list which has to be provided as a range of ranges. Where, for a node index i, adjacency[i] is the range of indices of neighboring nodes. While the outer range must be a random access range providing a size() method, the inter ranges only need to be forward ranges.

The algorithm initializes a queue with the seed node 0. In an advancing front sweep the algorithm processes entries from the queue until it is empty. Each entry is colored with the next free color not used by any of it's neighbors, followed by adding all non-processed neighbors to the queue.

If the queue is empty, the first non-processed node is searched and added to the queue to start the next sweep. This is done until there are no non-processed nodes left.

The number of needed sweeps corresponds to the number of connected components in the graph. If there are many connected components the search for non-processed noded can be avoided, by passing a container with seed nodes as additional argument.

Parameters

adjacency

Adjacency list of the graph

Returns

A std::vector<size_type> containing the color of each node index

computeColoring() [2/3]

template<class Adjacency , class SeedNodesContainer >

auto Dune::Assembler::Experimental::computeColoring	(	const Adjacency &	adjacency,
		SeedNodesContainer &&	seedNodes
	)

Compute a graph coloring from neighboring information.

This computes a coloring for a set of nodes with given adjacency using a simple greedy advancing front algorithm.

The input graph is represented as follows: Each node corresponds to an index. These indices are zero-based, consecutive, and stored as size_type. The adjacency of the graph is passed as an adjacency list which has to be provided as a range of ranges. Where, for a node index i, adjacency[i] is the range of indices of neighboring nodes. While the outer range must be a random access range providing a size() method, the inter ranges only need to be forward ranges.

This overload allows to additionally pass a container of seed nodes. The algorithm is the same as for the overload without this argument, but the internal queue is initialized with the given seed nodes instead of 0. This may improve performance if there are many connected components. Passing an empty container leads to the same behaviour as passing none.

Parameters

adjacency	Adjacency list of the graph
seedNodes	Container with seed nodes to be used for advancing front method.

Returns

A std::vector<size_type> containing the color of each node index

computeColoring() [3/3]

template<class Adjacency , class T >

auto Dune::Assembler::Experimental::computeColoring	(	const Adjacency &	adjacency,
		std::initializer_list< T >	seedIndices
	)

Compute a graph coloring from neighboring information.

This computes a coloring for a set of nodes with given adjacency using a simple greedy advancing front algorithm.

The input graph is represented as follows: Each node corresponds to an index. These indices are zero-based, consecutive, and stored as size_type. The adjacency of the graph is passed as an adjacency list which has to be provided as a range of ranges. Where, for a node index i, adjacency[i] is the range of indices of neighboring nodes. While the outer range must be a random access range providing a size() method, the inter ranges only need to be forward ranges.

This overload allows to additionally pass a container of seed nodes using a braced initializer list. It stores the entries in a std::vector and forwards this to the overload with templated SeedNodesContainer.

Parameters

adjacency	Adjacency list of the graph
seedNodes	std::initializer_list with seed nodes to be used for advancing front method.

Returns

A std::vector<size_type> containing the color of each node index

rangeSegment()

template<class Range >

static auto Dune::Assembler::Experimental::rangeSegment ( Range &  range, std::size_t  i, std::size_t  n  )

static

Split range into uniform segments.

Given a range, this returns a range-view of the i-th of n contiguous subranges of approximately the same size range.size()/n. To ensure that this is O(1) the passed range should provide random access iterators.

Parameters

range	The (random access) range that should be split
i	Index of this segment
n	Number of segments

Returns

A view given by Dune::IteratorRange

subEntityBasedElementAdjacency() [1/2]

template<class GridView , class SubEntityLayout , class size_type = uint32_t>

auto Dune::Assembler::Experimental::subEntityBasedElementAdjacency	(	const GridView &	gridView,
		const SubEntityLayout &	subEntityLayout
	)

Compute a layout based element adjacency list.

This identifies each element with its index in terms of a MultipleCodimMultipleGeomTypeMapper(..., mcmgElementLayout()) and returns the corresponding adjacency list.

Elements are considered to be neighbors if they share a subentity that is enabled by the given layout callback. The callback models the interface of the MultipleCodimMultipleGeomTypeMapper.

The produced adjacency list corresponds to a graph where grid element chunks are the nodes and subenitites are edges between adjacent element chunks.

Template Parameters

size_type

Type used to store indices (default=uint32_t)

Parameters

gridView	The underlying grid view
subEntityLayout	Layout class to select subentities

subEntityBasedElementAdjacency() [2/2]

template<class GridView , class SubEntityLayout , class ElementMapper , class size_type = uint32_t>

auto Dune::Assembler::Experimental::subEntityBasedElementAdjacency	(	const GridView &	gridView,
		const SubEntityLayout &	subEntityLayout,
		const ElementMapper &	elementMapper
	)

Compute a layout based adjacency list.

This uses a mapper to map elements to an index and returns the corresponding adjacency list. The mapper must provide elementMapper.index(element) and elementMapper.size() methods. It is allowed to map several elements to the same index. Then all elements sharing an index are treated as a element chunks.

Element chunks are considered to be neighbors if they share a subentity that is enabled by the given layout callback. The callback models the interface of the MultipleCodimMultipleGeomTypeMapper.

The produced adjacency list corresponds to a graph where grid element chunks are the nodes and subenitites are edges between adjacent element chunks.

Template Parameters

size_type

Type used to store indices (default=uint32_t)

Parameters

gridView	The underlying grid view
subEntityLayout	Layout class to select subentities
elementMapper	A mapper associating elements to indices

vertexBasedElementAdjacency() [1/2]

template<class GridView , class size_type = uint32_t>

auto Dune::Assembler::Experimental::vertexBasedElementAdjacency	(	const GridView &	gridView,
		bool	verbose = false
	)

Compute a vertex based element adjacency list.

This identifies each element with its index in terms of a MultipleCodimMultipleGeomTypeMapper(..., mcmgElementLayout()) and returns the corresponding adjacency list.

Elements are considered to be neighbors if they share a vertex. Notice that this automatically includes the case that elements share a subentity of any codimension.

The produced adjacency list corresponds to a graph where grid elements are the nodes and grid vertices are edges between adjacent elements. This is similar to, but not identical to the dual graph of the grid, because the latter only considers elements with shared facets as neighbors.

If the verbose mode is enabled, this computes and prints out the number of the largest found clique in the element graph which is a lower bound for the chromatic number of the graph (i.e. the minimal number of colores required in a coloring).

Template Parameters

size_type

Type used to store indices (default=uint32_t)

Parameters

gridView	The underlying grid view
verbose	Flag to enable verbose mode (default=false)

vertexBasedElementAdjacency() [2/2]

template<class GridView , class ElementMapper , class size_type = uint32_t>

auto Dune::Assembler::Experimental::vertexBasedElementAdjacency	(	const GridView &	gridView,
		const ElementMapper &	elementMapper,
		bool	verbose = false
	)

Compute a vertex based adjacency list.

This uses a mapper to map elements to an index and returns the corresponding adjacency list. The mapper must provide elementMapper.index(element) and elementMapper.size() methods. It is allowed to map several elements to the same index. Then all elements sharing an index are treated as a element chunks.

Element chunks are considered to be neighbors if they share a vertex. Notice that this automatically includes the case that elements share a subentity of any codimension.

The produced adjacency list corresponds to a graph where grid element chunks are the nodes and grid vertices are edges between adjacent element chunks.

If the verbose mode is enabled, this computes and prints out the number of the largest found clique in the element graph which is a lower bound for the chromatic number of the graph (i.e. the minimal number of colores required in a coloring).

Template Parameters

size_type

Type used to store indices (default=uint32_t)

Parameters

gridView	The underlying grid view
elementMapper	A mapper associating elements to indices
verbose	Flag to enable verbose mode (default=false)