![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
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
Theoretically, asymptotically better for dense Graphs: transitive closure based an Boolean Matrix Multiplication. However, implementation is more difficult.
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.
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< Graph > | ptr |
typedef boost::shared_ptr< Graph > | ptr |
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 |
Graph & | operator= (const Graph &) |
Graph & | operator= (Graph &&) |
Graph & | operator+= (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 IndexRange & | hmask () 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... | |
Graph & | operator= (const Graph &that) |
assigment operator More... | |
Graph & | operator= (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, Name > | Index |
typedef boost::adjacency_list< boost::setS, boost::listS, boost::directedS, Index > | graph_t |
typedef boost::graph_traits< graph_t >::vertex_descriptor | vertex_t |
typedef boost::unordered_map< int, vertex_t > | Index2VertexMap |
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_t * | g |
Index2VertexMap | i2v |
const GraphModel & | model |
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) |
|
private |
Definition at line 44 of file graph_boost.h.
|
private |
Definition at line 43 of file graph_boost.h.
|
private |
Definition at line 49 of file graph_boost.h.
|
private |
Definition at line 42 of file graph_boost.h.
typedef boost::shared_ptr<Graph> frechet::reach::Graph::ptr |
Definition at line 41 of file graph_m4ri.h.
typedef boost::shared_ptr<Graph> frechet::reach::Graph::ptr |
Definition at line 59 of file graph_boost.h.
|
private |
Definition at line 50 of file graph_boost.h.
|
private |
Definition at line 46 of file graph_boost.h.
|
private |
Definition at line 10 of file graph_boost.cpp.
frechet::reach::Graph::Graph | ( | const GraphModel & | model | ) |
Definition at line 16 of file graph_boost.cpp.
frechet::reach::Graph::Graph | ( | const GraphModel & | model, |
Structure & | str, | ||
int | i0 | ||
) |
Definition at line 21 of file graph_boost.cpp.
frechet::reach::Graph::Graph | ( | const Graph & | that | ) |
Definition at line 37 of file graph_boost.cpp.
frechet::reach::Graph::Graph | ( | Graph && | that | ) |
Definition at line 43 of file graph_boost.cpp.
frechet::reach::Graph::~Graph | ( | ) |
Definition at line 49 of file graph_boost.cpp.
|
protected |
empty constructor
amodel | maps intervals to nodes |
Definition at line 23 of file graph_m4ri.cpp.
|
protected |
constructor with column range
amodel | maps intervals to nodes |
range | column range covered by the graph |
Definition at line 35 of file graph_m4ri.cpp.
|
protected |
constructor from reachability structure
amodel | maps intervals to nodes |
str | a reachability structure |
Definition at line 45 of file graph_m4ri.cpp.
Graph::Graph | ( | const Graph & | that | ) |
Graph::Graph | ( | Graph && | that | ) |
move constructor
that | graph to copy from, empty on return |
Definition at line 73 of file graph_m4ri.cpp.
|
virtual |
destructor, releases memory
Definition at line 99 of file graph_m4ri.cpp.
void frechet::reach::Graph::add_edge | ( | int | i, |
int | j | ||
) |
Definition at line 147 of file graph_boost.cpp.
void frechet::reach::Graph::add_edge | ( | Orientation | ori_from, |
int | i_from, | ||
Orientation | ori_to, | ||
int | i_to | ||
) |
add an edge to the graph
ori_from | source orientention (horizontal or vertical) |
i_from | source node (=column or row) |
ori_to | destination orientation (horizontal or vertical) |
i_to | destination node (=column or row) |
void Graph::add_range | ( | IndexRange | r_from, |
IndexRange | r_to | ||
) |
add a set of edges to the graph, covering a range of nodes
r_from | source nodes |
r_to | destination nodes |
Definition at line 506 of file graph_m4ri.cpp.
mzd_t * Graph::allocate | ( | Orientation | o1, |
Orientation | o2 | ||
) |
allocate an adjacancy sub-matrix (one of four parts)
o1 | horizontal part |
o2 | vertical part |
Definition at line 85 of file graph_m4ri.cpp.
void Graph::allocateAll | ( | ) |
allocate data for adjacenty matrixes (all four parts)
Definition at line 79 of file graph_m4ri.cpp.
|
static |
apply bitwise and of two matrix rows
M | source Boolean matrix in M4RI format |
r | matrix row |
M2 | a Boolean matrix in M4RI format |
r2 | matrix row |
void frechet::reach::Graph::clear | ( | ) |
Definition at line 94 of file graph_boost.cpp.
void Graph::clear | ( | ) |
remove all edges
Definition at line 649 of file graph_m4ri.cpp.
void frechet::reach::Graph::clear | ( | Orientation | ori1, |
Orientation | ori2 | ||
) |
remove all edges of a sub-graph
ori1 | horizontal part |
ori2 | vertical part |
|
static |
clear a row in a Boolean matrix
M | a Boolean matrix in M4RI format |
row | matrix row |
|
virtual |
apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AND oepration: (*this)_VV &= that_VV
P | a set of valid placements |
Reimplemented in frechet::reach::GraphCL.
Definition at line 419 of file graph_m4ri.cpp.
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
ori_from | source orientention (horizontal or vertical) |
i_from | source node (=column or row) |
ori_to | destination orientation (horizontal or vertical) |
i_to | destination node (=column or row) |
bool frechet::reach::Graph::contains_edge | ( | IndexRange | r_from, |
IndexRange | r_to | ||
) | const |
check a range of edges
r_from | source nodes |
r_to | destination nodes |
|
private |
Definition at line 102 of file graph_boost.cpp.
Definition at line 117 of file graph_boost.cpp.
|
protected |
|
protected |
copy reachability info from Structure to Graph
str | a reachability structure |
ori | horizontal or vertical |
Definition at line 299 of file graph_m4ri.cpp.
double Graph::density | ( | Orientation | ori1, |
Orientation | ori2 | ||
) | const |
compute the density (amount of set edges) of an adjacancy matrix
ori1 | horizontal part |
ori2 | vertical part |
Definition at line 619 of file graph_m4ri.cpp.
double Graph::density | ( | ) | const |
Definition at line 636 of file graph_m4ri.cpp.
int frechet::reach::Graph::edges | ( | ) | const |
Definition at line 59 of file graph_boost.cpp.
bool Graph::empty | ( | Orientation | o1, |
Orientation | o2 | ||
) | const |
empty test for one of the four sub-graphs
o1 | source orientention (horizontal or vertical) |
o2 | destination orientation (horizontal or vertical) |
Definition at line 496 of file graph_m4ri.cpp.
|
virtual |
release memory that is not neeeded (empty sub-graphs)
Reimplemented in frechet::reach::GraphCL.
Definition at line 199 of file graph_m4ri.cpp.
int Graph::find_next0 | ( | Orientation | o1, |
int | i, | ||
Orientation | o2, | ||
int | j | ||
) | const |
find the next missing edge in a sub-graph
o1 | horizontal part |
i | start column |
o2 | vertical part |
j | start row |
Definition at line 695 of file graph_m4ri.cpp.
|
static |
find next cleared bit in a Boolean matrix
M | a Boolean matrix in M4RI format |
row | matrix row |
i | column |
int Graph::find_next1 | ( | Orientation | o1, |
int | i, | ||
Orientation | o2, | ||
int | j | ||
) | const |
find the next edge in a sub-graph
o1 | horizontal part |
i | start column |
o2 | vertical part |
j | start row |
Definition at line 679 of file graph_m4ri.cpp.
|
static |
find next set bit in a Boolean matrix
M | a Boolean matrix in M4RI format |
row | matrix row |
i | column |
IndexRange Graph::find_next_range | ( | Orientation | o1, |
int | i, | ||
Orientation | o2, | ||
int | j | ||
) | const |
find a range of consecutive edges in a sub-graph
o1 | horizontal part |
i | start column |
o2 | vertical part |
j | start row |
Definition at line 710 of file graph_m4ri.cpp.
|
virtual |
Reimplemented in frechet::reach::GraphCL.
Definition at line 450 of file graph_m4ri.cpp.
|
inline |
Definition at line 198 of file graph_m4ri.h.
|
static |
query bits in a Boolean matrix
M | a Boolean matrix in M4RI format |
row | matrix row |
i | first column |
j | last column (exclusive) |
Definition at line 585 of file graph_m4ri.cpp.
|
inline |
horizontal range covered by this graph
Definition at line 187 of file graph_m4ri.h.
A | a graph |
B | another graph |
Definition at line 775 of file graph_m4ri.cpp.
bool Graph::is_upper_triangular | ( | Orientation | ori1, |
Orientation | ori2 | ||
) | const |
ori1 | horizontal part |
ori2 | vertical part |
Definition at line 662 of file graph_m4ri.cpp.
|
static |
mzd | a boolean matrix (in M4RI format) |
double Graph::memory | ( | Orientation | ori1, |
Orientation | ori2 | ||
) | const |
compute the memory footprint of an adjacancy matrix
ori1 | horizontal part |
ori2 | vertical part |
Definition at line 612 of file graph_m4ri.cpp.
double Graph::memory | ( | ) | const |
Definition at line 627 of file graph_m4ri.cpp.
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
B | another graph |
pool | pool of re-cycled matrixes (optional) |
|
virtual |
apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*this)_VV = *A_VV * *B_VV
A | a graph |
B | another graph |
pool | pool of re-cycled matrixes (optional) |
Reimplemented in frechet::reach::GraphCL.
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
B | another graph |
pool |
|
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
A | a graph |
B | another graph |
pool | pool of re-cycled matrixes (optional) |
Reimplemented in frechet::reach::GraphCL.
frechet::reach::Graph & frechet::reach::Graph::operator+= | ( | const Graph & | B | ) |
Definition at line 77 of file graph_boost.cpp.
frechet::reach::Graph & frechet::reach::Graph::operator= | ( | const Graph & | that | ) |
Definition at line 64 of file graph_boost.cpp.
frechet::reach::Graph & frechet::reach::Graph::operator= | ( | Graph && | that | ) |
Definition at line 71 of file graph_boost.cpp.
assigment operator
that | graph to copy from |
Definition at line 227 of file graph_m4ri.cpp.
move assigment operator
that | graph to copy from; empty on return |
Definition at line 234 of file graph_m4ri.cpp.
bool Graph::operator== | ( | const Graph & | that | ) | const |
comparison operator
that | graph to compare with |
Definition at line 240 of file graph_m4ri.cpp.
void Graph::print | ( | std::ostream & | out, |
Orientation | o1, | ||
Orientation | o2 | ||
) | const |
print a sub-adjacancy matrix
out | output stream |
o1 | horizontal part |
o2 | vertical part |
Definition at line 781 of file graph_m4ri.cpp.
|
staticprotected |
print a Boolean matrix
out | output stream |
M | a boolean matrix (in M4RI format) |
Definition at line 786 of file graph_m4ri.cpp.
void Graph::printOrigin | ( | std::ostream & | out | ) | const |
debug output
Definition at line 162 of file graph_m4ri.cpp.
|
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.
frechet::Rect Graph::rect | ( | Orientation | o1, |
Orientation | o2 | ||
) | const |
range covered by this graph
o1 | horizontal part |
o2 | vertical part |
Definition at line 94 of file graph_m4ri.cpp.
|
virtual |
release memory for all parts of the adjacancy matrix
Definition at line 203 of file graph_m4ri.cpp.
|
virtual |
release memory for one part of the adjacancy matrix
o1 | horizontal part |
o2 | vertical part |
Reimplemented in frechet::reach::GraphCL.
Definition at line 218 of file graph_m4ri.cpp.
|
virtual |
release memory for one part of the adjacancy matrix
o1 | horizontal part |
o2 | vertical part |
pool | a pool of re-cycled matrix data |
Reimplemented in frechet::reach::GraphCL.
Definition at line 798 of file graph_m4ri.cpp.
void Graph::releaseIfZero | ( | ) |
release memory that is not neeeded (empty sub-graphs)
Definition at line 210 of file graph_m4ri.cpp.
|
inlinevirtual |
implemented by GraphCL
Reimplemented in frechet::reach::GraphCL.
Definition at line 434 of file graph_m4ri.h.
|
static |
set some bits in a Boolean matrix
M | a Boolean matrix in M4RI format |
row | matrix row |
i | first column |
j | last column (exclusive) |
Definition at line 556 of file graph_m4ri.cpp.
void Graph::setOriginCombine | ( | Graph::ptr | P | ) |
a sub-set of valid placements is applied to the graph
P | a set of valid placements |
Definition at line 157 of file graph_m4ri.cpp.
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.
A | first successor |
B | seocnd succssor |
Definition at line 128 of file graph_m4ri.cpp.
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.
A | first successor |
B | seocnd succssor |
Definition at line 142 of file graph_m4ri.cpp.
void Graph::setOriginPlacement | ( | int | di, |
int | dj | ||
) |
this graph represents a set of valid placements
di | first diagonal endpoint |
dj | second diagonal endpoint |
Definition at line 104 of file graph_m4ri.cpp.
void Graph::setOriginRG | ( | int | i | ) |
this graph represents a reachability graph, it was created from a reachability structure
i | free-space column |
Definition at line 116 of file graph_m4ri.cpp.
|
private |
Definition at line 108 of file graph_boost.cpp.
|
protected |
swap graph
that | grap to swap with; holds *this on return |
Definition at line 290 of file graph_m4ri.cpp.
|
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.
|
inlinevirtual |
implemented by GraphCL; copy matrix data to GPU memory
Reimplemented in frechet::reach::GraphCL.
Definition at line 430 of file graph_m4ri.h.
frechet::reach::Graph::ptr frechet::reach::Graph::transitiveClosure | ( | ) | const |
Definition at line 157 of file graph_boost.cpp.
void frechet::reach::Graph::transitiveClosureInPlace | ( | ) |
Definition at line 164 of file graph_boost.cpp.
|
private |
Definition at line 131 of file graph_boost.cpp.
int frechet::reach::Graph::vertices | ( | ) | const |
Definition at line 54 of file graph_boost.cpp.
bool Graph::zero | ( | Orientation | o1, |
Orientation | o2 | ||
) | const |
empty test for one of the four sub-graphs
o1 | source orientention (horizontal or vertical) |
o2 | destination orientation (horizontal or vertical) |
Definition at line 501 of file graph_m4ri.cpp.
|
friend |
static, empty constructor
model | maps intervals to nodes |
|
friend |
static constructor with column range
model | maps intervals to nodes |
hmask | column range covered by the graph |
|
friend |
static constructor from reachability structure
model | maps intervals to nodes |
str | a reachability structure |
|
mutableprotected |
result of call to searchDiagonalElement
Definition at line 78 of file graph_m4ri.h.
|
private |
Definition at line 52 of file graph_boost.h.
|
private |
Definition at line 53 of file graph_boost.h.
|
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.
|
private |
Definition at line 55 of file graph_boost.h.
|
protected |
mapping from intervals -> graph nodes = rows and columns of the adjacancy matrix
Definition at line 76 of file graph_m4ri.h.
|
protected |
adjacency matrix (M4RI structure) split into four parts to allow for memory savings.
Definition at line 45 of file graph_m4ri.h.
struct frechet::reach::Graph::Origin frechet::reach::Graph::origin |