11 namespace frechet {
namespace reach {
15 typedef boost::shared_ptr<Graph>
GraphPtr;
41 typedef boost::shared_ptr<Graph>
ptr;
522 static void print(std::ostream& out,
const mzd_t* M);
543 static void set_bits(mzd_t* M,
int row,
int i,
int j);
552 static bool has_bits(mzd_t* M,
int row,
int i,
int j);
558 static void clear_row(mzd_t* M,
int row);
566 static void and_row(mzd_t* M,
int r, mzd_t* M2,
int r2);
575 static int find_next1(mzd_t* M,
int row,
int i);
583 static int find_next0(mzd_t* M,
int row,
int i);
int find_next0(Orientation o1, int i, Orientation o2, int j) const
find the next missing edge in a sub-graph
void print(std::ostream &out, Orientation o1, Orientation o2) const
print a sub-adjacancy matrix
Graph::ptr P
valid placement applied to the graph
mzd_t * allocate(Orientation o1, Orientation o2)
allocate an adjacancy sub-matrix (one of four parts)
int i
if this is a reachability graph: column range in free-space. this = RG(i,j), or CRG(i,...
static void and_row(mzd_t *M, int r, mzd_t *M2, int r2)
apply bitwise and of two matrix rows
virtual void combine(const Graph *P)
apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AN...
virtual void synchToGpu()
implemented by GraphCL; copy matrix data to GPU memory
global definitions for all algorithms.
mzd_t * mtx[2][2]
adjacency matrix (M4RI structure) split into four parts to allow for memory savings.
boost::shared_ptr< GraphModel > ptr
smart pointer to a GraphModel object
boost::shared_ptr< Graph > GraphPtr
int diagonalElement
result of call to searchDiagonalElement
virtual void synchFromGpu()
implemented by GraphCL; copy matrix data backt to CPU memory
void releaseIfZero()
release memory that is not neeeded (empty sub-graphs)
bool zero(Orientation o1, Orientation o2) const
empty test for one of the four sub-graphs
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...
bool empty(Orientation o1, Orientation o2) const
empty test for one of the four sub-graphs
bool contains_edge(Orientation ori_from, int i_from, Orientation ori_to, int i_to) const
check if an edge is present
bool is_upper_triangular(Orientation ori1, Orientation ori2) const
static void clear_row(mzd_t *M, int row)
clear a row in a Boolean matrix
GraphPtr newGraph(const GraphModel::ptr model)
virtual void release()
release memory for all parts of the adjacancy matrix
a very simple Rectangle structure, with integer boundaries.
Graph::ptr merge2(const Graph *B, MatrixPool *pool=nullptr) const
apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a mat...
Graph::ptr merge3(const Graph *B, MatrixPool *pool=nullptr) const
apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs...
void allocateAll()
allocate data for adjacenty matrixes (all four parts)
void setOriginRG(int i)
this graph represents a reachability graph, it was created from a reachability structure
void setOriginPlacement(int di, int dj)
this graph represents a set of valid placements
a range of node indices in a Reachability Graph
void setOriginCombine(Graph::ptr P)
a sub-set of valid placements is applied to the graph
Orientation
Segment Orientation.
boost::shared_ptr< Graph > ptr
this is a rechability graph, constructed from a reachability structure
memory pool for matrix objects (M4RI matrices mzd_t* and OpenCL matrices clm4rm_t*)
Graph(const GraphModel &model, graph_t *ag)
Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure,...
void add_range(IndexRange r_from, IndexRange r_to)
add a set of edges to the graph, covering a range of nodes
this graph is the result of a MERGE operation (transitive closure) on two graphs
const GraphModel::ptr model
How was this graph constructed? This info is useful for visualisation & debugging....
IndexRange find_next_range(Orientation o1, int i, Orientation o2, int j) const
find a range of consecutive edges in a sub-graph
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.
void add_edge(int i, int j)
this graph represents a set of valid placements
struct frechet::reach::Graph::Origin origin
int find_next1(Orientation o1, int i, Orientation o2, int j) const
find the next edge in a sub-graph
static bool has_bits(mzd_t *M, int row, int i, int j)
query bits in a Boolean matrix
Graph::ptr A
if this graph was constructed as transitive closure: original graphs this = MERGE(A,...
int blevel
bottom-level (for topologial sorting; leaves = blevel 0
virtual void queryDiagonalElement() const
find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result o...
static void set_bits(mzd_t *M, int row, int i, int j)
set some bits in a Boolean matrix
const GraphModel::ptr graphModel() const
The Reachability Structure; maintains a list of intervals on the border of Free Space,...
const IndexRange & hmask() const
horizontal range covered by this graph
virtual void resetConditions()
implemented by GraphCL
int succesors
number of successors
void printOrigin(std::ostream &out) const
debug output
virtual void finalize()
release memory that is not neeeded (empty sub-graphs)
Rect rect(Orientation o1, Orientation o2) const
range covered by this graph
static bool is_adjacent_to(const Graph &A, const Graph &B)
Graph & operator=(const Graph &)
this graph is the result of a MERGE operation (transitive closure) on three graphs
enum frechet::reach::Graph::Origin::@7 operation
virtual int foundDiagonalElement() const
bool operator==(const Graph &that) const
comparison operator