#include <BoxGraph.h>

Inheritance diagram for SAMRAI::hier::BoxGraph< DIM >:

Classes
struct	GraphNode

BoxGraph constructors
enum	Locality { DST_IS_LOCAL, DST_IS_NONLOCAL }

BoxArray< DIM >	d_src_boxes

tbox::Array< int >	d_src_idx

tbox::Array< int >	d_src_map

BoxArray< DIM >	d_dst_boxes

IntVector< DIM >	d_grow_dst_boxes

int	d_sort_dimension

tbox::Array< tbox::Array< int > >	d_adj

tbox::Array< tbox::Array< int > >	d_adj_local

tbox::Pointer< tbox::Timer >	t_setup_total

tbox::Pointer< tbox::Timer >	t_setup_add_edges

tbox::Pointer< tbox::Timer >	t_setup_sort

	BoxGraph (const BoxArray< DIM > &src_box_array, const tbox::Array< tbox::List< IntVector< DIM > > > &src_shifts, const ProcessorMapping &src_mapping, const BoxArray< DIM > &dst_box_array, const IntVector< DIM > &dst_grow=IntVector< DIM >(1), int sort_dimension=-1)
	Constructor for use with getSrcOverlapIndices(). More...

	BoxGraph (const BoxArray< DIM > &src_box_array, const tbox::Array< tbox::List< IntVector< DIM > > > &src_shifts, const BoxArray< DIM > &dst_box_array, const IntVector< DIM > &dst_grow=IntVector< DIM >(1), int sort_dimension=-1)
	Constructor for use with removeIntersections(). More...

	BoxGraph (const BoxArray< DIM > &src_box_array, const BoxArray< DIM > &dst_box_array, const IntVector< DIM > &dst_grow=IntVector< DIM >(1), int sort_dimension=-1)

	~BoxGraph ()

const tbox::Array< int > &	getSrcOverlapIndices (int dst_index)
	Compute the indices of boxes from the src_box_array that overlap with the box dst_box_array[index]. More...

const tbox::Array< int > &	getLocalSrcOverlapIndices (int dst_index)
	Computes the indices of boxes from the src_box_array that overlap with the box dst_box_array[index] and that are mapped to the same processor. More...

void	removeIntersections (BoxList< DIM > &list)
	Remove from the dst_box_array the portions that intersect the boxes in src_box_array. More...

void	printGraph (std::ostream &os=tbox::plog)
	Undocumented function, used during development and testing. More...

	BoxGraph (const BoxGraph< DIM > &)

BoxGraph< DIM > &	operator= (const BoxGraph< DIM > &)

void	addEdges (tbox::Array< typename BoxGraph< DIM >::GraphNode > &src, int src_ct, tbox::Array< typename BoxGraph< DIM >::GraphNode > &dst, int dst_ct, tbox::Array< tbox::List< int > > &adj_lists)

void	buildLocalOverlapArrays ()

void	findBinLimits (int binNumberIN, int dim, tbox::Array< typename BoxGraph< DIM >::GraphNode > &sortedNodesIN, int &firstOUT, int &lastOUT, int &rightEdgeOfBinOUT)

void	findSortDimension ()

void	sortNodeList (tbox::Array< typename BoxGraph< DIM >::GraphNode > &list, int len)

void	sortIndices (tbox::Array< tbox::Array< int > > &graph)

void	buildGraph ()

void	print (tbox::Array< typename BoxGraph< DIM >::GraphNode > &list, int len)

static int	qsortCompare (const void v, const void w)

static int	qsortIntCompare (const void v, const void w)

Detailed Description

template<int DIM>
class SAMRAI::hier::BoxGraph< DIM >

Class BoxGraph is a utility class that provides functionality that can be used to reduce the runtime complexity of certain box calculus operations. Two types of functionality are provided. First, there is a getSrcOverlapIndices() method; second, there is a removeIntersections() method. These are described below.

BoxGraph is designed around the premise that you have two sets of boxes: an array or source boxes (src_box_array), and an array of destination boxes (dst_box_array). The dst boxes are grown by some number of cells in each coordinate direction to determine overlaps with the source boxes. Typically, this is related to the ghost width of that data that resides on AMR hierachy patches that correspond to the boxes. The getSrcOverlapIndices() and getLocalSrcOverlapIndices() methods provide efficient methods to determine which boxes from the src_box_array overlap with a specified box from the dst_box_array.
getSrcOverlapIndices() returns the indices of all source boxes that overlap with a specified destination box. getLocalSrcOverlapIndices() returns the indices of all source boxes that overlap with a specified destination box and are mapped to the same processor as the specified destination box.

The removeIntersections() method is similar in concept to the BoxList<DIM>::removeIntersections() method. Here, however, we operate on the two arrays of boxes that are passed to the constructor. The BoxGraph::removeIntersections() method is functionally equivalent to the following:

*      BoxList<DIM> dst_box_list(dst_box_array);
*      BoxList<DIM> src_box_list(src_box_array);
*      dst_box_list.removeIntersections(src_box_list);
*

Note that the dst_box_array may be the same as the src_box_array. This occurs, for example, during regridding operations when both both levels are the same.

The above sequence of calls, however, has O(N^2) runtime complexity, assuming both arrays of boxes contain N items. This class typically performs removeIntersections in O(N^3/2), although worst case behavior can be shown to be O(N^5/2).

Internally BoxGraph operates by constructing a bipartite graph; (this is performed in the constructor). One set of independent vertices contains a vertex for each box in the src_box_array; the other independent set contains vertices corresponding to the dst_box_array. The graph contains an edge (i,j) if (1) vertices i and j belong to different independent sets; (2) the boxes corresponding to the vertices overlap each other.

Methods in this class were originally designed to improve efficiency in xfer_RefineSchedule<DIM>::generateCommunicationSchedule().

Member Enumeration Documentation

◆ Locality

template<int DIM>

enum SAMRAI::hier::BoxGraph::Locality

private

Enumerator
DST_IS_LOCAL
DST_IS_NONLOCAL

Constructor & Destructor Documentation

◆ BoxGraph() [1/4]

template<int DIM>

SAMRAI::hier::BoxGraph< DIM >::BoxGraph	(	const BoxArray< DIM > &	src_box_array,
		const tbox::Array< tbox::List< IntVector< DIM > > > &	src_shifts,
		const ProcessorMapping &	src_mapping,
		const BoxArray< DIM > &	dst_box_array,
		const IntVector< DIM > &	dst_grow = `IntVector< DIM >(1)`,
		int	sort_dimension = `-1`
	)

This constructor must be used if you will later call BoxGraph::getSrcOverlapIndices(). This constructor can also be used if you will later call BoxGraph::removeIntersections().

Parameters

src_box_array	the array of source boxes.
src_shifts	the amount by which each box is shifted when there are periodic boundary conditions. If there are no periodic boundary conditions you can pass an array of length zero; otherwise the array must contain an entry for each box in src_box_array.
src_mapping	maps each box in src_box_array to a processor.
dst_box_array	the array of destination boxes.
dst_grow	the amount to grow each box in dst_box_array.
sort_dimension	the direction (x, y, z) in which boxes will be sorted when building the graph. This parameter is included for performance tuning and testing; users should use the default setting.

◆ BoxGraph() [2/4]

template<int DIM>

SAMRAI::hier::BoxGraph< DIM >::BoxGraph	(	const BoxArray< DIM > &	src_box_array,
		const tbox::Array< tbox::List< IntVector< DIM > > > &	src_shifts,
		const BoxArray< DIM > &	dst_box_array,
		const IntVector< DIM > &	dst_grow = `IntVector< DIM >(1)`,
		int	sort_dimension = `-1`
	)

This constructor can be used when a BoxGraph object is employed to perform BoxGraph::removeIntersections() operations. It can not be used if you intend to call BoxGraph::getSrcOverlapIndices().

Parameters

src_box_array	the array of source boxes.
src_shifts	the amount by which each box is shifted when there are periodic boundary conditions. If there are no periodic boundary conditions you can pass an array of length zero; otherwise the array must contain an entry for each box in src_box_array.
dst_box_array	the array of destination boxes.
dst_grow	the to grow each box in dst_box_array.
sort_dimension	the direction (x, y, z) in which boxes will be sorted when building the graph. This parameter is included for performance tuning and testing; users should use the default setting.

◆ BoxGraph() [3/4]

template<int DIM>

SAMRAI::hier::BoxGraph< DIM >::BoxGraph	(	const BoxArray< DIM > &	src_box_array,
		const BoxArray< DIM > &	dst_box_array,
		const IntVector< DIM > &	dst_grow = `IntVector< DIM >(1)`,
		int	sort_dimension = `-1`
	)

◆ ~BoxGraph()

template<int DIM>

SAMRAI::hier::BoxGraph< DIM >::~BoxGraph ( )

The destructor releases privately held resources.

◆ BoxGraph() [4/4]

template<int DIM>

SAMRAI::hier::BoxGraph< DIM >::BoxGraph ( const BoxGraph< DIM > & )

private

Member Function Documentation

◆ getSrcOverlapIndices()

template<int DIM>

const tbox::Array<int>& SAMRAI::hier::BoxGraph< DIM >::getSrcOverlapIndices ( int dst_index )

Parameters

dst_index input; the index of the box from the dst_box_array whose overlaps are requested.

Returns: the indices of the boxes from src_box_array that overlap with the box: dst_box_array[index].

◆ getLocalSrcOverlapIndices()

template<int DIM>

const tbox::Array<int>& SAMRAI::hier::BoxGraph< DIM >::getLocalSrcOverlapIndices ( int dst_index )

Parameters

dst_index input; the index of the box from the dst_box_array whose overlaps are requested.

Returns: the indices of the boxes from src_box_array that overlap with the box: dst_box_array[index] and that are mapped to the same processor.

◆ removeIntersections()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::removeIntersections ( BoxList< DIM > & list )

Returns what you would get if you performed the following operations:

*   BoxList<DIM> dst_box_list(dst_box_array);
*   BoxList<DIM> src_box_list(src_box_array);
*   dst_box_list.removeIntersections(src_box_list);
*

Parameters

list	on return, contains the portions of the dst_box_array that remain after removing the intersections with the src_box_array.

◆ printGraph()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::printGraph ( std::ostream & os = tbox::plog )

◆ operator=()

template<int DIM>

BoxGraph<DIM>& SAMRAI::hier::BoxGraph< DIM >::operator= ( const BoxGraph< DIM > & )

private

◆ addEdges()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::addEdges	(	tbox::Array< typename BoxGraph< DIM >::GraphNode > &	src,
		int	src_ct,
		tbox::Array< typename BoxGraph< DIM >::GraphNode > &	dst,
		int	dst_ct,
		tbox::Array< tbox::List< int > > &	adj_lists
	)

private

◆ buildLocalOverlapArrays()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::buildLocalOverlapArrays ( )

private

◆ findBinLimits()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::findBinLimits	(	int	binNumberIN,
		int	dim,
		tbox::Array< typename BoxGraph< DIM >::GraphNode > &	sortedNodesIN,
		int &	firstOUT,
		int &	lastOUT,
		int &	rightEdgeOfBinOUT
	)

private

◆ findSortDimension()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::findSortDimension ( )

private

◆ qsortCompare()

template<int DIM>

static int SAMRAI::hier::BoxGraph< DIM >::qsortCompare	(	const void *	v,
		const void *	w
	)

staticprivate

◆ qsortIntCompare()

template<int DIM>

static int SAMRAI::hier::BoxGraph< DIM >::qsortIntCompare	(	const void *	v,
		const void *	w
	)

staticprivate

◆ sortNodeList()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::sortNodeList	(	tbox::Array< typename BoxGraph< DIM >::GraphNode > &	list,
		int	len
	)

private

◆ sortIndices()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::sortIndices ( tbox::Array< tbox::Array< int > > & graph )

private

◆ buildGraph()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::buildGraph ( )

private

◆ print()

template<int DIM>

void SAMRAI::hier::BoxGraph< DIM >::print	(	tbox::Array< typename BoxGraph< DIM >::GraphNode > &	list,
		int	len
	)

private

Member Data Documentation

◆ d_src_boxes

template<int DIM>

BoxArray<DIM> SAMRAI::hier::BoxGraph< DIM >::d_src_boxes

private

◆ d_src_idx

template<int DIM>

tbox::Array<int> SAMRAI::hier::BoxGraph< DIM >::d_src_idx

private

◆ d_src_map

template<int DIM>

tbox::Array<int> SAMRAI::hier::BoxGraph< DIM >::d_src_map

private

◆ d_dst_boxes

template<int DIM>

BoxArray<DIM> SAMRAI::hier::BoxGraph< DIM >::d_dst_boxes

private

◆ d_grow_dst_boxes

template<int DIM>

IntVector<DIM> SAMRAI::hier::BoxGraph< DIM >::d_grow_dst_boxes

private

◆ d_sort_dimension

template<int DIM>

int SAMRAI::hier::BoxGraph< DIM >::d_sort_dimension

private

◆ d_adj

template<int DIM>

tbox::Array< tbox::Array<int> > SAMRAI::hier::BoxGraph< DIM >::d_adj

private

◆ d_adj_local

template<int DIM>

tbox::Array< tbox::Array<int> > SAMRAI::hier::BoxGraph< DIM >::d_adj_local

private

◆ t_setup_total

template<int DIM>

tbox::Pointer<tbox::Timer> SAMRAI::hier::BoxGraph< DIM >::t_setup_total

private

◆ t_setup_add_edges

template<int DIM>

tbox::Pointer<tbox::Timer> SAMRAI::hier::BoxGraph< DIM >::t_setup_add_edges

private

◆ t_setup_sort

template<int DIM>

tbox::Pointer<tbox::Timer> SAMRAI::hier::BoxGraph< DIM >::t_setup_sort

private

The documentation for this class was generated from the following file:

/samrai/include/BoxGraph.h

Classes

BoxGraph constructors

Detailed Description

template<int DIM> class SAMRAI::hier::BoxGraph< DIM >

Member Enumeration Documentation

◆ Locality

Constructor & Destructor Documentation

◆ BoxGraph() [1/4]

◆ BoxGraph() [2/4]

◆ BoxGraph() [3/4]

◆ ~BoxGraph()

◆ BoxGraph() [4/4]

Member Function Documentation

◆ getSrcOverlapIndices()

◆ getLocalSrcOverlapIndices()

◆ removeIntersections()

◆ printGraph()

◆ operator=()

◆ addEdges()

◆ buildLocalOverlapArrays()

◆ findBinLimits()

◆ findSortDimension()

◆ qsortCompare()

◆ qsortIntCompare()

◆ sortNodeList()

◆ sortIndices()

◆ buildGraph()

◆ print()

Member Data Documentation

◆ d_src_boxes

◆ d_src_idx

◆ d_src_map

◆ d_dst_boxes

◆ d_grow_dst_boxes

◆ d_sort_dimension

◆ d_adj

◆ d_adj_local

◆ t_setup_total

◆ t_setup_add_edges

◆ t_setup_sort

template<int DIM>
class SAMRAI::hier::BoxGraph< DIM >