Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::reach::Graph Class Reference

Detailed Description

Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure, broken down to the most fine-grained intervals.

Represents a Reachability Graph. Vertices correspond to Boundary intervals that are connected to every reachable interval on the opposite side.

Graphs can be merged.

Transitive Closure: uses boost::Graph O(|V||E|) which is pretty good for sparse graphs (|E| << n^2) see https://www.boost.org/doc/libs/1_48_0/libs/graph/doc/transitive_closure.html

  • would profit somewhat from persisted condensation graphs

Theoretically, asymptotically better for dense Graphs: transitive closure based an Boolean Matrix Multiplication. However, implementation is more difficult.

  • strongly connected components form the condensation graph (persist!)
  • sort in topological order
  • divide & conquer recursively, see https://www.cs.bgu.ac.il/~dinitz/Course/SS-12/transitiveClosure.pdf
  • finally, uses BMM. M4RI(E) is a good candidate for BMM, but it can't operate on sub-matrices; requires some copying. maybe, it would pay-off for large matrices.

We should also consider "dynamic" algorithms for transitive closure. Asymptotically similar, but may be more efficient in keeping data structures.

Mapping from reachability intervals to graph nodes is managed by GraphModel.

Graphs can be merged (transitive closure).

Memory layout of adjacancy matrixes is explained below. Boolean matrixes are modelled by M4RI.

Author
Peter Schäfer

Definition at line 39 of file graph_boost.h.

#include <graph_boost.h>

Inherited by frechet::reach::GraphCL.

Classes

struct  Origin
 How was this graph constructed? This info is useful for visualisation & debugging. And for constructing a topologoically sorted list of tasks. (see frechet::poly::AlgorithmTopoSort). More...
 

Public Types

typedef boost::shared_ptr< Graphptr
 
typedef boost::shared_ptr< Graphptr
 

Public Member Functions

 Graph (const GraphModel &model)
 
 Graph (const GraphModel &model, Structure &str, int i0)
 
 Graph (const Graph &)
 
 Graph (Graph &&)
 
 ~Graph ()
 
int vertices () const
 
int edges () const
 
Graphoperator= (const Graph &)
 
Graphoperator= (Graph &&)
 
Graphoperator+= (const Graph &)
 
Graph::ptr transitiveClosure () const
 
void transitiveClosureInPlace ()
 
void add_edge (int i, int j)
 
void clear ()
 
 Graph (const Graph &that)
 copy constructor More...
 
 Graph (Graph &&that)
 move constructor More...
 
virtual ~Graph ()
 destructor, releases memory More...
 
void allocateAll ()
 allocate data for adjacenty matrixes (all four parts) More...
 
mzd_t * allocate (Orientation o1, Orientation o2)
 allocate an adjacancy sub-matrix (one of four parts) More...
 
const IndexRangehmask () const
 horizontal range covered by this graph More...
 
Rect rect (Orientation o1, Orientation o2) const
 range covered by this graph More...
 
const GraphModel::ptr graphModel () const
 
void setOriginPlacement (int di, int dj)
 this graph represents a set of valid placements More...
 
void setOriginRG (int i)
 this graph represents a reachability graph, it was created from a reachability structure More...
 
void setOriginMerge2 (Graph::ptr A, Graph::ptr B)
 this graph is the transitive closure of two other graphs. It is the result of a MERGE operation. More...
 
void setOriginMerge3 (Graph::ptr A, Graph::ptr B)
 this graph is the transitive closure of two other graphs. It is the result of a final MERGE operation. More...
 
void setOriginCombine (Graph::ptr P)
 a sub-set of valid placements is applied to the graph More...
 
void printOrigin (std::ostream &out) const
 debug output More...
 
Graphoperator= (const Graph &that)
 assigment operator More...
 
Graphoperator= (Graph &&that)
 move assigment operator More...
 
bool operator== (const Graph &that) const
 comparison operator More...
 
Edit and Query operations
void add_edge (Orientation ori_from, int i_from, Orientation ori_to, int i_to)
 add an edge to the graph More...
 
void add_range (IndexRange r_from, IndexRange r_to)
 add a set of edges to the graph, covering a range of nodes More...
 
bool contains_edge (Orientation ori_from, int i_from, Orientation ori_to, int i_to) const
 check if an edge is present More...
 
bool contains_edge (IndexRange r_from, IndexRange r_to) const
 check a range of edges More...
 
bool empty (Orientation o1, Orientation o2) const
 empty test for one of the four sub-graphs More...
 
bool zero (Orientation o1, Orientation o2) const
 empty test for one of the four sub-graphs More...
 
virtual void finalize ()
 release memory that is not neeeded (empty sub-graphs) More...
 
void releaseIfZero ()
 release memory that is not neeeded (empty sub-graphs) More...
 
virtual void release ()
 release memory for all parts of the adjacancy matrix More...
 
virtual void release (Orientation o1, Orientation o2)
 release memory for one part of the adjacancy matrix More...
 
virtual void release (Orientation o1, Orientation o2, MatrixPool *pool)
 release memory for one part of the adjacancy matrix More...
 
Iterator methods
int find_next1 (Orientation o1, int i, Orientation o2, int j) const
 find the next edge in a sub-graph More...
 
int find_next0 (Orientation o1, int i, Orientation o2, int j) const
 find the next missing edge in a sub-graph More...
 
IndexRange find_next_range (Orientation o1, int i, Orientation o2, int j) const
 find a range of consecutive edges in a sub-graph More...
 
Bulk operations
virtual void combine (const Graph *P)
 apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AND oepration: (*this)_VV &= that_VV More...
 
Graph::ptr merge2 (const Graph *B, MatrixPool *pool=nullptr) const
 apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*result)_VV = (*this)_VV * that_VV More...
 
virtual void merge2 (const Graph *A, const Graph *B, MatrixPool *pool=nullptr)
 apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*this)_VV = *A_VV * *B_VV More...
 
Graph::ptr merge3 (const Graph *B, MatrixPool *pool=nullptr) const
 apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*result)_HH = (*this)_HV * that_VV * (*this)_VH More...
 
virtual void merge3 (const Graph *A, const Graph *B, MatrixPool *pool=nullptr)
 apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: this_HH = A_HV * B_VV * A_VH More...
 
virtual void queryDiagonalElement () const
 find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result of this method, call foundDiagonalElement. (reason: we also want to perform this query asynchronously on a GPU). More...
 
virtual int foundDiagonalElement () const
 
stubs for derived classes
virtual void synchToGpu ()
 implemented by GraphCL; copy matrix data to GPU memory More...
 
virtual void synchFromGpu ()
 implemented by GraphCL; copy matrix data backt to CPU memory More...
 
virtual void resetConditions ()
 implemented by GraphCL More...
 
Memory Diaganotics
double memory (Orientation ori1, Orientation ori2) const
 compute the memory footprint of an adjacancy matrix More...
 
double density (Orientation ori1, Orientation ori2) const
 compute the density (amount of set edges) of an adjacancy matrix More...
 
double memory () const
 
double density () const
 

Static Public Member Functions

static bool is_adjacent_to (const Graph &A, const Graph &B)
 
for unit tests
static void set_bits (mzd_t *M, int row, int i, int j)
 set some bits in a Boolean matrix More...
 
static bool has_bits (mzd_t *M, int row, int i, int j)
 query bits in a Boolean matrix More...
 
static void clear_row (mzd_t *M, int row)
 clear a row in a Boolean matrix More...
 
static void and_row (mzd_t *M, int r, mzd_t *M2, int r2)
 apply bitwise and of two matrix rows More...
 
static int find_next1 (mzd_t *M, int row, int i)
 find next set bit in a Boolean matrix More...
 
static int find_next0 (mzd_t *M, int row, int i)
 find next cleared bit in a Boolean matrix More...
 

Public Attributes

struct frechet::reach::Graph::Origin origin
 

Protected Member Functions

 Graph (const GraphModel::ptr amodel)
 empty constructor More...
 
 Graph (const GraphModel::ptr amodel, IndexRange range)
 constructor with column range More...
 
 Graph (const GraphModel::ptr amodel, Structure &str)
 constructor from reachability structure More...
 
void copy (const Graph &that)
 copy graph More...
 
void swap (Graph &that)
 swap graph More...
 
void copy (const Structure &str, Orientation ori)
 copy reachability info from Structure to Graph More...
 

Static Protected Member Functions

static void print (std::ostream &out, const mzd_t *M)
 print a Boolean matrix More...
 

Protected Attributes

mzd_t * mtx [2][2]
 adjacency matrix (M4RI structure) split into four parts to allow for memory savings. More...
 
IndexRange mask [2]
 
const GraphModel::ptr model
 
int diagonalElement
 result of call to searchDiagonalElement More...
 

Private Types

typedef boost::property< boost::vertex_name_t, int > Name
 
typedef boost::property< boost::vertex_index_t, std::size_t, NameIndex
 
typedef boost::adjacency_list< boost::setS, boost::listS, boost::directedS, Indexgraph_t
 
typedef boost::graph_traits< graph_t >::vertex_descriptor vertex_t
 
typedef boost::unordered_map< int, vertex_tIndex2VertexMap
 
typedef boost::property_map< graph_t, boost::vertex_index_t >::type Vertex2IndexMap
 

Private Member Functions

 Graph (const GraphModel &model, graph_t *ag)
 
void copy (const Graph &)
 
void swap (Graph &)
 
vertex_t vertex (int i)
 
void copy (const Structure &str, Pointer i1, Pointer i2)
 

Private Attributes

graph_tg
 
Index2VertexMap i2v
 
const GraphModelmodel
 

Friends

GraphPtr frechet::reach::newGraph (const GraphModel::ptr model)
 static, empty constructor More...
 
GraphPtr frechet::reach::newGraph (const GraphModel::ptr model, IndexRange hmask)
 static constructor with column range More...
 
GraphPtr frechet::reach::newGraph (const GraphModel::ptr model, Structure &str)
 static constructor from reachability structure More...
 

Debugging

void clear ()
 remove all edges More...
 
void clear (Orientation ori1, Orientation ori2)
 remove all edges of a sub-graph More...
 
bool is_upper_triangular (Orientation ori1, Orientation ori2) const
 
void print (std::ostream &out, Orientation o1, Orientation o2) const
 print a sub-adjacancy matrix More...
 
static bool is_upper_triangular (const mzd_t *mzd)
 

Member Typedef Documentation

◆ graph_t

typedef boost::adjacency_list< boost::setS, boost::listS, boost::directedS, Index > frechet::reach::Graph::graph_t
private

Definition at line 44 of file graph_boost.h.

◆ Index

typedef boost::property<boost::vertex_index_t, std::size_t, Name> frechet::reach::Graph::Index
private

Definition at line 43 of file graph_boost.h.

◆ Index2VertexMap

typedef boost::unordered_map<int,vertex_t> frechet::reach::Graph::Index2VertexMap
private

Definition at line 49 of file graph_boost.h.

◆ Name

typedef boost::property<boost::vertex_name_t, int> frechet::reach::Graph::Name
private

Definition at line 42 of file graph_boost.h.

◆ ptr [1/2]

typedef boost::shared_ptr<Graph> frechet::reach::Graph::ptr

Definition at line 41 of file graph_m4ri.h.

◆ ptr [2/2]

typedef boost::shared_ptr<Graph> frechet::reach::Graph::ptr

Definition at line 59 of file graph_boost.h.

◆ Vertex2IndexMap

typedef boost::property_map<graph_t,boost::vertex_index_t>::type frechet::reach::Graph::Vertex2IndexMap
private

Definition at line 50 of file graph_boost.h.

◆ vertex_t

typedef boost::graph_traits< graph_t >::vertex_descriptor frechet::reach::Graph::vertex_t
private

Definition at line 46 of file graph_boost.h.

Constructor & Destructor Documentation

◆ Graph() [1/10]

frechet::reach::Graph::Graph ( const GraphModel model,
graph_t ag 
)
private

Definition at line 10 of file graph_boost.cpp.

◆ Graph() [2/10]

frechet::reach::Graph::Graph ( const GraphModel model)

Definition at line 16 of file graph_boost.cpp.

◆ Graph() [3/10]

frechet::reach::Graph::Graph ( const GraphModel model,
Structure str,
int  i0 
)

Definition at line 21 of file graph_boost.cpp.

◆ Graph() [4/10]

frechet::reach::Graph::Graph ( const Graph that)

Definition at line 37 of file graph_boost.cpp.

◆ Graph() [5/10]

frechet::reach::Graph::Graph ( Graph &&  that)

Definition at line 43 of file graph_boost.cpp.

◆ ~Graph() [1/2]

frechet::reach::Graph::~Graph ( )

Definition at line 49 of file graph_boost.cpp.

◆ Graph() [6/10]

Graph::Graph ( const GraphModel::ptr  amodel)
protected

empty constructor

Parameters
amodelmaps intervals to nodes

Definition at line 23 of file graph_m4ri.cpp.

◆ Graph() [7/10]

Graph::Graph ( const GraphModel::ptr  amodel,
IndexRange  range 
)
protected

constructor with column range

Parameters
amodelmaps intervals to nodes
rangecolumn range covered by the graph

Definition at line 35 of file graph_m4ri.cpp.

◆ Graph() [8/10]

Graph::Graph ( const GraphModel::ptr  amodel,
Structure str 
)
protected

constructor from reachability structure

Parameters
amodelmaps intervals to nodes
stra reachability structure

Definition at line 45 of file graph_m4ri.cpp.

◆ Graph() [9/10]

Graph::Graph ( const Graph that)

copy constructor

Parameters
thatgraph to copy from

Definition at line 67 of file graph_m4ri.cpp.

◆ Graph() [10/10]

Graph::Graph ( Graph &&  that)

move constructor

Parameters
thatgraph to copy from, empty on return

Definition at line 73 of file graph_m4ri.cpp.

◆ ~Graph() [2/2]

Graph::~Graph ( )
virtual

destructor, releases memory

Definition at line 99 of file graph_m4ri.cpp.

Member Function Documentation

◆ add_edge() [1/2]

void frechet::reach::Graph::add_edge ( int  i,
int  j 
)

Definition at line 147 of file graph_boost.cpp.

◆ add_edge() [2/2]

void frechet::reach::Graph::add_edge ( Orientation  ori_from,
int  i_from,
Orientation  ori_to,
int  i_to 
)

add an edge to the graph

Parameters
ori_fromsource orientention (horizontal or vertical)
i_fromsource node (=column or row)
ori_todestination orientation (horizontal or vertical)
i_todestination node (=column or row)

◆ add_range()

void Graph::add_range ( IndexRange  r_from,
IndexRange  r_to 
)

add a set of edges to the graph, covering a range of nodes

Parameters
r_fromsource nodes
r_todestination nodes

Definition at line 506 of file graph_m4ri.cpp.

◆ allocate()

mzd_t * Graph::allocate ( Orientation  o1,
Orientation  o2 
)

allocate an adjacancy sub-matrix (one of four parts)

Parameters
o1horizontal part
o2vertical part
Returns
pointer to a M4RI boolean matrix

Definition at line 85 of file graph_m4ri.cpp.

◆ allocateAll()

void Graph::allocateAll ( )

allocate data for adjacenty matrixes (all four parts)

Definition at line 79 of file graph_m4ri.cpp.

◆ and_row()

static void frechet::reach::Graph::and_row ( mzd_t *  M,
int  r,
mzd_t *  M2,
int  r2 
)
static

apply bitwise and of two matrix rows

Parameters
Msource Boolean matrix in M4RI format
rmatrix row
M2a Boolean matrix in M4RI format
r2matrix row

◆ clear() [1/3]

void frechet::reach::Graph::clear ( )

Definition at line 94 of file graph_boost.cpp.

◆ clear() [2/3]

void Graph::clear ( )

remove all edges

Definition at line 649 of file graph_m4ri.cpp.

◆ clear() [3/3]

void frechet::reach::Graph::clear ( Orientation  ori1,
Orientation  ori2 
)

remove all edges of a sub-graph

Parameters
ori1horizontal part
ori2vertical part

◆ clear_row()

static void frechet::reach::Graph::clear_row ( mzd_t *  M,
int  row 
)
static

clear a row in a Boolean matrix

Parameters
Ma Boolean matrix in M4RI format
rowmatrix row

◆ combine()

void Graph::combine ( const Graph P)
virtual

apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AND oepration: (*this)_VV &= that_VV

Parameters
Pa set of valid placements

Reimplemented in frechet::reach::GraphCL.

Definition at line 419 of file graph_m4ri.cpp.

◆ contains_edge() [1/2]

bool frechet::reach::Graph::contains_edge ( Orientation  ori_from,
int  i_from,
Orientation  ori_to,
int  i_to 
) const

check if an edge is present

Parameters
ori_fromsource orientention (horizontal or vertical)
i_fromsource node (=column or row)
ori_todestination orientation (horizontal or vertical)
i_todestination node (=column or row)
Returns
true, if the edge is present

◆ contains_edge() [2/2]

bool frechet::reach::Graph::contains_edge ( IndexRange  r_from,
IndexRange  r_to 
) const

check a range of edges

Parameters
r_fromsource nodes
r_todestination nodes
Returns
true, if at least one is edge is present in the queries range

◆ copy() [1/4]

void frechet::reach::Graph::copy ( const Graph B)
private

Definition at line 102 of file graph_boost.cpp.

◆ copy() [2/4]

void frechet::reach::Graph::copy ( const Structure str,
Pointer  i1,
Pointer  i2 
)
private

Definition at line 117 of file graph_boost.cpp.

◆ copy() [3/4]

void Graph::copy ( const Graph that)
protected

copy graph

Parameters
thatgraph to copy from

Definition at line 258 of file graph_m4ri.cpp.

◆ copy() [4/4]

void Graph::copy ( const Structure str,
Orientation  ori 
)
protected

copy reachability info from Structure to Graph

Parameters
stra reachability structure
orihorizontal or vertical

Definition at line 299 of file graph_m4ri.cpp.

◆ density() [1/2]

double Graph::density ( Orientation  ori1,
Orientation  ori2 
) const

compute the density (amount of set edges) of an adjacancy matrix

Parameters
ori1horizontal part
ori2vertical part
Returns
relative density

Definition at line 619 of file graph_m4ri.cpp.

◆ density() [2/2]

double Graph::density ( ) const
Returns
the density (amount of set edges) of all adjacancy matrixes

Definition at line 636 of file graph_m4ri.cpp.

◆ edges()

int frechet::reach::Graph::edges ( ) const

Definition at line 59 of file graph_boost.cpp.

◆ empty()

bool Graph::empty ( Orientation  o1,
Orientation  o2 
) const

empty test for one of the four sub-graphs

Parameters
o1source orientention (horizontal or vertical)
o2destination orientation (horizontal or vertical)
Returns
true if the sub-graph is missing

Definition at line 496 of file graph_m4ri.cpp.

◆ finalize()

void Graph::finalize ( )
virtual

release memory that is not neeeded (empty sub-graphs)

Reimplemented in frechet::reach::GraphCL.

Definition at line 199 of file graph_m4ri.cpp.

◆ find_next0() [1/2]

int Graph::find_next0 ( Orientation  o1,
int  i,
Orientation  o2,
int  j 
) const

find the next missing edge in a sub-graph

Parameters
o1horizontal part
istart column
o2vertical part
jstart row
Returns
the next missing edge in the sub-graph, or INT_MAX if there is none

Definition at line 695 of file graph_m4ri.cpp.

◆ find_next0() [2/2]

static int frechet::reach::Graph::find_next0 ( mzd_t *  M,
int  row,
int  i 
)
static

find next cleared bit in a Boolean matrix

Parameters
Ma Boolean matrix in M4RI format
rowmatrix row
icolumn
Returns
column of next cleared bit in row, or INT_MAX if there is none

◆ find_next1() [1/2]

int Graph::find_next1 ( Orientation  o1,
int  i,
Orientation  o2,
int  j 
) const

find the next edge in a sub-graph

Parameters
o1horizontal part
istart column
o2vertical part
jstart row
Returns
the next edge in the sub-graph, or INT_MAX if there is none

Definition at line 679 of file graph_m4ri.cpp.

◆ find_next1() [2/2]

static int frechet::reach::Graph::find_next1 ( mzd_t *  M,
int  row,
int  i 
)
static

find next set bit in a Boolean matrix

Parameters
Ma Boolean matrix in M4RI format
rowmatrix row
icolumn
Returns
column of next set bit in row, or INT_MAX if there is none

◆ find_next_range()

IndexRange Graph::find_next_range ( Orientation  o1,
int  i,
Orientation  o2,
int  j 
) const

find a range of consecutive edges in a sub-graph

Parameters
o1horizontal part
istart column
o2vertical part
jstart row
Returns
next consecutive range of edges, or an empty range if there are none

Definition at line 710 of file graph_m4ri.cpp.

◆ foundDiagonalElement()

int Graph::foundDiagonalElement ( ) const
virtual
Returns
the result of the last call to queryDiagonalElement. Or -1 if the diagonal is empty.

Reimplemented in frechet::reach::GraphCL.

Definition at line 450 of file graph_m4ri.cpp.

◆ graphModel()

const GraphModel::ptr frechet::reach::Graph::graphModel ( ) const
inline
Returns
model that maps reachability intervals for graph nodes

Definition at line 198 of file graph_m4ri.h.

◆ has_bits()

bool Graph::has_bits ( mzd_t *  M,
int  row,
int  i,
int  j 
)
static

query bits in a Boolean matrix

Parameters
Ma Boolean matrix in M4RI format
rowmatrix row
ifirst column
jlast column (exclusive)
Returns
true if at least one bit is set

Definition at line 585 of file graph_m4ri.cpp.

◆ hmask()

const IndexRange& frechet::reach::Graph::hmask ( ) const
inline

horizontal range covered by this graph

Returns
range of nodes that is covered by this graph

Definition at line 187 of file graph_m4ri.h.

◆ is_adjacent_to()

bool Graph::is_adjacent_to ( const Graph A,
const Graph B 
)
static
Parameters
Aa graph
Banother graph
Returns
true if the column ranges of both graphs are adjacent

Definition at line 775 of file graph_m4ri.cpp.

◆ is_upper_triangular() [1/2]

bool Graph::is_upper_triangular ( Orientation  ori1,
Orientation  ori2 
) const
Parameters
ori1horizontal part
ori2vertical part
Returns
true if the sub-adjancy matrix is an upper triangular matrix

Definition at line 662 of file graph_m4ri.cpp.

◆ is_upper_triangular() [2/2]

static bool frechet::reach::Graph::is_upper_triangular ( const mzd_t *  mzd)
static
Parameters
mzda boolean matrix (in M4RI format)
Returns
true if the matrix is an upper triangular matrix

◆ memory() [1/2]

double Graph::memory ( Orientation  ori1,
Orientation  ori2 
) const

compute the memory footprint of an adjacancy matrix

Parameters
ori1horizontal part
ori2vertical part
Returns
memory, in Bytes, used by a (sub-)adjacancy matrix

Definition at line 612 of file graph_m4ri.cpp.

◆ memory() [2/2]

double Graph::memory ( ) const
Returns
the memory footprint for all adjacancy matrixes

Definition at line 627 of file graph_m4ri.cpp.

◆ merge2() [1/2]

Graph::ptr frechet::reach::Graph::merge2 ( const Graph B,
MatrixPool pool = nullptr 
) const

apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*result)_VV = (*this)_VV * that_VV

Parameters
Banother graph
poolpool of re-cycled matrixes (optional)
Returns
a newly created graph representing the result of the MERGE operation

◆ merge2() [2/2]

virtual void frechet::reach::Graph::merge2 ( const Graph A,
const Graph B,
MatrixPool pool = nullptr 
)
virtual

apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*this)_VV = *A_VV * *B_VV

Parameters
Aa graph
Banother graph
poolpool of re-cycled matrixes (optional)

Reimplemented in frechet::reach::GraphCL.

◆ merge3() [1/2]

Graph::ptr frechet::reach::Graph::merge3 ( const Graph B,
MatrixPool pool = nullptr 
) const

apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*result)_HH = (*this)_HV * that_VV * (*this)_VH

Parameters
Banother graph
pool
Returns
a newly created graph representing the result of the MERGE operation

◆ merge3() [2/2]

virtual void frechet::reach::Graph::merge3 ( const Graph A,
const Graph B,
MatrixPool pool = nullptr 
)
virtual

apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: this_HH = A_HV * B_VV * A_VH

Parameters
Aa graph
Banother graph
poolpool of re-cycled matrixes (optional)

Reimplemented in frechet::reach::GraphCL.

◆ operator+=()

frechet::reach::Graph & frechet::reach::Graph::operator+= ( const Graph B)

Definition at line 77 of file graph_boost.cpp.

◆ operator=() [1/4]

frechet::reach::Graph & frechet::reach::Graph::operator= ( const Graph that)

Definition at line 64 of file graph_boost.cpp.

◆ operator=() [2/4]

frechet::reach::Graph & frechet::reach::Graph::operator= ( Graph &&  that)

Definition at line 71 of file graph_boost.cpp.

◆ operator=() [3/4]

Graph & Graph::operator= ( const Graph that)

assigment operator

Parameters
thatgraph to copy from
Returns
reference to this, after assignment

Definition at line 227 of file graph_m4ri.cpp.

◆ operator=() [4/4]

Graph & Graph::operator= ( Graph &&  that)

move assigment operator

Parameters
thatgraph to copy from; empty on return
Returns
reference to this, after assignment

Definition at line 234 of file graph_m4ri.cpp.

◆ operator==()

bool Graph::operator== ( const Graph that) const

comparison operator

Parameters
thatgraph to compare with
Returns
true if both graphs are equal

Definition at line 240 of file graph_m4ri.cpp.

◆ print() [1/2]

void Graph::print ( std::ostream &  out,
Orientation  o1,
Orientation  o2 
) const

print a sub-adjacancy matrix

Parameters
outoutput stream
o1horizontal part
o2vertical part

Definition at line 781 of file graph_m4ri.cpp.

◆ print() [2/2]

void Graph::print ( std::ostream &  out,
const mzd_t *  M 
)
staticprotected

print a Boolean matrix

Parameters
outoutput stream
Ma boolean matrix (in M4RI format)

Definition at line 786 of file graph_m4ri.cpp.

◆ printOrigin()

void Graph::printOrigin ( std::ostream &  out) const

debug output

Definition at line 162 of file graph_m4ri.cpp.

◆ queryDiagonalElement()

void Graph::queryDiagonalElement ( ) const
virtual

find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result of this method, call foundDiagonalElement. (reason: we also want to perform this query asynchronously on a GPU).

Reimplemented in frechet::reach::GraphCL.

Definition at line 437 of file graph_m4ri.cpp.

◆ rect()

frechet::Rect Graph::rect ( Orientation  o1,
Orientation  o2 
) const

range covered by this graph

Parameters
o1horizontal part
o2vertical part
Returns
range of nodes that is covered by this one part of the adjacancy matrix

Definition at line 94 of file graph_m4ri.cpp.

◆ release() [1/3]

void Graph::release ( )
virtual

release memory for all parts of the adjacancy matrix

Definition at line 203 of file graph_m4ri.cpp.

◆ release() [2/3]

void Graph::release ( Orientation  o1,
Orientation  o2 
)
virtual

release memory for one part of the adjacancy matrix

Parameters
o1horizontal part
o2vertical part

Reimplemented in frechet::reach::GraphCL.

Definition at line 218 of file graph_m4ri.cpp.

◆ release() [3/3]

void Graph::release ( Orientation  o1,
Orientation  o2,
MatrixPool pool 
)
virtual

release memory for one part of the adjacancy matrix

Parameters
o1horizontal part
o2vertical part
poola pool of re-cycled matrix data

Reimplemented in frechet::reach::GraphCL.

Definition at line 798 of file graph_m4ri.cpp.

◆ releaseIfZero()

void Graph::releaseIfZero ( )

release memory that is not neeeded (empty sub-graphs)

Definition at line 210 of file graph_m4ri.cpp.

◆ resetConditions()

virtual void frechet::reach::Graph::resetConditions ( )
inlinevirtual

implemented by GraphCL

Reimplemented in frechet::reach::GraphCL.

Definition at line 434 of file graph_m4ri.h.

◆ set_bits()

void Graph::set_bits ( mzd_t *  M,
int  row,
int  i,
int  j 
)
static

set some bits in a Boolean matrix

Parameters
Ma Boolean matrix in M4RI format
rowmatrix row
ifirst column
jlast column (exclusive)

Definition at line 556 of file graph_m4ri.cpp.

◆ setOriginCombine()

void Graph::setOriginCombine ( Graph::ptr  P)

a sub-set of valid placements is applied to the graph

Parameters
Pa set of valid placements

Definition at line 157 of file graph_m4ri.cpp.

◆ setOriginMerge2()

void Graph::setOriginMerge2 ( Graph::ptr  A,
Graph::ptr  B 
)

this graph is the transitive closure of two other graphs. It is the result of a MERGE operation.

Parameters
Afirst successor
Bseocnd succssor

Definition at line 128 of file graph_m4ri.cpp.

◆ setOriginMerge3()

void Graph::setOriginMerge3 ( Graph::ptr  A,
Graph::ptr  B 
)

this graph is the transitive closure of two other graphs. It is the result of a final MERGE operation.

Parameters
Afirst successor
Bseocnd succssor

Definition at line 142 of file graph_m4ri.cpp.

◆ setOriginPlacement()

void Graph::setOriginPlacement ( int  di,
int  dj 
)

this graph represents a set of valid placements

Parameters
difirst diagonal endpoint
djsecond diagonal endpoint

Definition at line 104 of file graph_m4ri.cpp.

◆ setOriginRG()

void Graph::setOriginRG ( int  i)

this graph represents a reachability graph, it was created from a reachability structure

Parameters
ifree-space column

Definition at line 116 of file graph_m4ri.cpp.

◆ swap() [1/2]

void frechet::reach::Graph::swap ( Graph that)
private

Definition at line 108 of file graph_boost.cpp.

◆ swap() [2/2]

void Graph::swap ( Graph that)
protected

swap graph

Parameters
thatgrap to swap with; holds *this on return

Definition at line 290 of file graph_m4ri.cpp.

◆ synchFromGpu()

virtual void frechet::reach::Graph::synchFromGpu ( )
inlinevirtual

implemented by GraphCL; copy matrix data backt to CPU memory

Reimplemented in frechet::reach::GraphCL.

Definition at line 432 of file graph_m4ri.h.

◆ synchToGpu()

virtual void frechet::reach::Graph::synchToGpu ( )
inlinevirtual

implemented by GraphCL; copy matrix data to GPU memory

Reimplemented in frechet::reach::GraphCL.

Definition at line 430 of file graph_m4ri.h.

◆ transitiveClosure()

frechet::reach::Graph::ptr frechet::reach::Graph::transitiveClosure ( ) const

Definition at line 157 of file graph_boost.cpp.

◆ transitiveClosureInPlace()

void frechet::reach::Graph::transitiveClosureInPlace ( )

Definition at line 164 of file graph_boost.cpp.

◆ vertex()

frechet::reach::Graph::vertex_t frechet::reach::Graph::vertex ( int  i)
private

Definition at line 131 of file graph_boost.cpp.

◆ vertices()

int frechet::reach::Graph::vertices ( ) const

Definition at line 54 of file graph_boost.cpp.

◆ zero()

bool Graph::zero ( Orientation  o1,
Orientation  o2 
) const

empty test for one of the four sub-graphs

Parameters
o1source orientention (horizontal or vertical)
o2destination orientation (horizontal or vertical)
Returns
true if the sub-graph is missing, or empty

Definition at line 501 of file graph_m4ri.cpp.

Friends And Related Function Documentation

◆ frechet::reach::newGraph [1/3]

static, empty constructor

Parameters
modelmaps intervals to nodes
Returns
a newly created, empty graph

◆ frechet::reach::newGraph [2/3]

GraphPtr frechet::reach::newGraph ( const GraphModel::ptr  model,
IndexRange  hmask 
)
friend

static constructor with column range

Parameters
modelmaps intervals to nodes
hmaskcolumn range covered by the graph
Returns
a newly created, empty graph

◆ frechet::reach::newGraph [3/3]

GraphPtr frechet::reach::newGraph ( const GraphModel::ptr  model,
Structure str 
)
friend

static constructor from reachability structure

Parameters
modelmaps intervals to nodes
stra reachability structure
Returns
a newly created graph that represents the reachability structure

Member Data Documentation

◆ diagonalElement

int frechet::reach::Graph::diagonalElement
mutableprotected

result of call to searchDiagonalElement

Definition at line 78 of file graph_m4ri.h.

◆ g

graph_t* frechet::reach::Graph::g
private

Definition at line 52 of file graph_boost.h.

◆ i2v

Index2VertexMap frechet::reach::Graph::i2v
private

Definition at line 53 of file graph_boost.h.

◆ mask

IndexRange frechet::reach::Graph::mask[2]
protected

RG(i,j) describes only a curve segment of P (and possibly all of Q). Adjacacency matrices are somewhat sparse, like this:

        +--+            +-----------------------
        |//|            |//////////////////////
        +--+            +-----------------------
                        |
                        |
--------+--+------------+-----------------------
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /

RG(i,i+1) is only about 25% dense. Later, RG(i,j) become denser.

Merge operations (transitive closure) are ony between adjacent ranges of (i,j) - (j,h)

We can save storage space, multiplication must be adjusted accordingly

Definition at line 72 of file graph_m4ri.h.

◆ model [1/2]

const GraphModel& frechet::reach::Graph::model
private

Definition at line 55 of file graph_boost.h.

◆ model [2/2]

const GraphModel::ptr frechet::reach::Graph::model
protected

mapping from intervals -> graph nodes = rows and columns of the adjacancy matrix

Definition at line 76 of file graph_m4ri.h.

◆ mtx

mzd_t* frechet::reach::Graph::mtx[2][2]
protected

adjacency matrix (M4RI structure) split into four parts to allow for memory savings.

Definition at line 45 of file graph_m4ri.h.

◆ origin

struct frechet::reach::Graph::Origin frechet::reach::Graph::origin

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