SAMRAI::hier::BoxGraph

SAMRAI::hier::BoxGraph< DIM > Class Template Reference

#include <source/hierarchy/boxes/BoxGraph.h>

List of all members.

Public Member Functions

 ~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].
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.
void removeIntersections (BoxList< DIM > &list)
 Remove from the dst_box_array the portions that intersect the boxes in src_box_array.
void printGraph (std::ostream &os=tbox::plog)
 Undocumented function, used during development and testing.

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().

Constructor & Destructor Documentation

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 
)

Constructor for use with getSrcOverlapIndices().

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.

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 
)

Constructor for use with removeIntersections().

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.

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 
)

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

The destructor releases privately held resources.

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 
)

Constructor for use with getSrcOverlapIndices().

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.

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 
)

Constructor for use with removeIntersections().

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.

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 
)

Member Function Documentation

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

Compute the indices of boxes from the src_box_array that overlap with the box dst_box_array[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].

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

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.

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.

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

Remove from the dst_box_array the portions that intersect the boxes in src_box_array.

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.

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

Undocumented function, used during development and testing.

The documentation for this class was generated from the following files:
Generated on Thu Jun 18 11:28:27 2009 for SAMRAI by  doxygen 1.5.1