Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
graph_m4ri.h
Go to the documentation of this file.
1 #ifndef GRAPH_H
2 #define GRAPH_H
3 
4 #include <structure.h>
5 #include <graph_model.h>
6 #include <iostream>
7 #include <data/matrix_pool.h>
8 
9 struct mzd_t;
10 
11 namespace frechet { namespace reach {
12 
13 //class GraphModel;
14 class Graph;
15 typedef boost::shared_ptr<Graph> GraphPtr;
16 
17 /* Factory methods
18 */
19 GraphPtr newGraph(const GraphModel::ptr model);
20 GraphPtr newGraph(const GraphModel::ptr model, IndexRange hmask);
22 
38 class Graph
39 {
40 public:
41  typedef boost::shared_ptr<Graph> ptr;
42 protected:
45  mzd_t* mtx[2][2];
46 
73 
78  mutable int diagonalElement;
79 
80  //@deprecated friend class CGraph;
81 public:
88  struct Origin {
90  enum {
92  RG,
95  } operation;
97  int blevel;
99  int succesors;
102  int i,j;
112  } origin;
113 
114 protected:
135 
140  Graph(const GraphModel::ptr amodel);
146  Graph(const GraphModel::ptr amodel, IndexRange range);
152  Graph(const GraphModel::ptr amodel, Structure& str);
153 public:
158  Graph(const Graph& that);
163  Graph(Graph&& that);
164 
165 public:
169  virtual ~Graph();
170 
174  void allocateAll();
181  mzd_t* allocate(Orientation o1, Orientation o2);
182 
187  const IndexRange& hmask() const { return mask[HORIZONTAL]; }
194  Rect rect(Orientation o1, Orientation o2) const;
198  const GraphModel::ptr graphModel() const { return model; }
199 
205  void setOriginPlacement(int di, int dj);
211  void setOriginRG(int i);
234  void printOrigin(std::ostream& out) const;
235 
241  Graph& operator= (const Graph& that);
247  Graph& operator= (Graph&& that);
253  bool operator== (const Graph& that) const;
254 
265  void add_edge(Orientation ori_from, int i_from,
266  Orientation ori_to, int i_to);
273  void add_range(IndexRange r_from, IndexRange r_to);
274  //void add_range(IndexRange r_form, IndexRangePair r_to);
283  bool contains_edge(Orientation ori_from, int i_from,
284  Orientation ori_to, int i_to) const;
291  bool contains_edge(IndexRange r_from, IndexRange r_to) const;
298  bool empty(Orientation o1, Orientation o2) const;
305  bool zero(Orientation o1, Orientation o2) const;
309  virtual void finalize();
313  void releaseIfZero();
314 
318  virtual void release();
324  virtual void release(Orientation o1, Orientation o2);
331  virtual void release(Orientation o1, Orientation o2, MatrixPool* pool);
332 
346  int find_next1(Orientation o1, int i, Orientation o2, int j) const;
355  int find_next0(Orientation o1, int i, Orientation o2, int j) const;
364  IndexRange find_next_range(Orientation o1, int i, Orientation o2, int j) const;
365 
376  virtual void combine (const Graph* P);
377 
385  Graph::ptr merge2(const Graph* B, MatrixPool* pool=nullptr) const;
386  // this_VV := A_VV * B_VV (@see setOrigin)
394  virtual void merge2(const Graph* A, const Graph* B, MatrixPool* pool=nullptr);
395 
403  Graph::ptr merge3(const Graph* B, MatrixPool* pool=nullptr) const;
411  virtual void merge3(const Graph* A, const Graph* B, MatrixPool* pool=nullptr);
417  virtual void queryDiagonalElement() const;
422  virtual int foundDiagonalElement() const;
423 
429  virtual void synchToGpu() { /*no-op. implemented by GraphCL */ }
432  virtual void synchFromGpu() { /*no-op. implemented by GraphCL */ }
434  virtual void resetConditions() { /*no-op. implemented by GraphCL */ }
446  double memory(Orientation ori1, Orientation ori2) const;
453  double density(Orientation ori1, Orientation ori2) const;
454 
458  double memory() const;
462  double density() const;
463 
472  void clear();
478  void clear(Orientation ori1, Orientation ori2);
484  bool is_upper_triangular(Orientation ori1, Orientation ori2) const;
489  static bool is_upper_triangular(const mzd_t* mzd);
496  void print(std::ostream& out, Orientation o1, Orientation o2) const;
499 protected:
504  void copy(const Graph& that);
509  void swap(Graph& that);
510 
516  void copy(const Structure& str, Orientation ori);
522  static void print(std::ostream& out, const mzd_t* M);
523 
524 public:
530  static bool is_adjacent_to(const Graph& A, const Graph& B);
531 
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);
567 
575  static int find_next1(mzd_t* M, int row, int i);
583  static int find_next0(mzd_t* M, int row, int i);
586 };
587 
588 
589 
590 } } // namespace frecht::reach
591 
592 #endif // GRAPH_H
int find_next0(Orientation o1, int i, Orientation o2, int j) const
find the next missing edge in a sub-graph
Definition: graph_m4ri.cpp:695
void print(std::ostream &out, Orientation o1, Orientation o2) const
print a sub-adjacancy matrix
Definition: graph_m4ri.cpp:781
Graph::ptr P
valid placement applied to the graph
Definition: graph_m4ri.h:110
mzd_t * allocate(Orientation o1, Orientation o2)
allocate an adjacancy sub-matrix (one of four parts)
Definition: graph_m4ri.cpp:85
int i
if this is a reachability graph: column range in free-space. this = RG(i,j), or CRG(i,...
Definition: graph_m4ri.h:102
void copy(const Graph &)
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...
Definition: graph_m4ri.cpp:419
virtual void synchToGpu()
implemented by GraphCL; copy matrix data to GPU memory
Definition: graph_m4ri.h:430
global definitions for all algorithms.
mzd_t * mtx[2][2]
adjacency matrix (M4RI structure) split into four parts to allow for memory savings.
Definition: graph_m4ri.h:45
boost::shared_ptr< GraphModel > ptr
smart pointer to a GraphModel object
Definition: graph_model.h:307
boost::shared_ptr< Graph > GraphPtr
Definition: graph_m4ri.h:14
int diagonalElement
result of call to searchDiagonalElement
Definition: graph_m4ri.h:78
virtual void synchFromGpu()
implemented by GraphCL; copy matrix data backt to CPU memory
Definition: graph_m4ri.h:432
void releaseIfZero()
release memory that is not neeeded (empty sub-graphs)
Definition: graph_m4ri.cpp:210
bool zero(Orientation o1, Orientation o2) const
empty test for one of the four sub-graphs
Definition: graph_m4ri.cpp:501
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...
Definition: graph_m4ri.cpp:142
bool empty(Orientation o1, Orientation o2) const
empty test for one of the four sub-graphs
Definition: graph_m4ri.cpp:496
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
Definition: graph_m4ri.cpp:662
static void clear_row(mzd_t *M, int row)
clear a row in a Boolean matrix
GraphPtr newGraph(const GraphModel::ptr model)
Definition: graph_cl.cpp:12
virtual void release()
release memory for all parts of the adjacancy matrix
Definition: graph_m4ri.cpp:203
a very simple Rectangle structure, with integer boundaries.
Definition: types.h:35
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...
double memory() const
Definition: graph_m4ri.cpp:627
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)
Definition: graph_m4ri.cpp:79
void setOriginRG(int i)
this graph represents a reachability graph, it was created from a reachability structure
Definition: graph_m4ri.cpp:116
void setOriginPlacement(int di, int dj)
this graph represents a set of valid placements
Definition: graph_m4ri.cpp:104
a range of node indices in a Reachability Graph
Definition: graph_model.h:17
void setOriginCombine(Graph::ptr P)
a sub-set of valid placements is applied to the graph
Definition: graph_m4ri.cpp:157
Orientation
Segment Orientation.
Definition: boundary.h:31
boost::shared_ptr< Graph > ptr
Definition: graph_m4ri.h:41
this is a rechability graph, constructed from a reachability structure
Definition: graph_m4ri.h:92
memory pool for matrix objects (M4RI matrices mzd_t* and OpenCL matrices clm4rm_t*)
Definition: matrix_pool.h:26
Graph(const GraphModel &model, graph_t *ag)
Definition: graph_boost.cpp:10
Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure,...
Definition: graph_boost.h:39
void add_range(IndexRange r_from, IndexRange r_to)
add a set of edges to the graph, covering a range of nodes
Definition: graph_m4ri.cpp:506
this graph is the result of a MERGE operation (transitive closure) on two graphs
Definition: graph_m4ri.h:93
const GraphModel::ptr model
Definition: graph_m4ri.h:76
How was this graph constructed? This info is useful for visualisation & debugging....
Definition: graph_m4ri.h:88
#define str(S)
double density() const
Definition: graph_m4ri.cpp:636
IndexRange find_next_range(Orientation o1, int i, Orientation o2, int j) const
find a range of consecutive edges in a sub-graph
Definition: graph_m4ri.cpp:710
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.
Definition: graph_m4ri.cpp:128
void add_edge(int i, int j)
this graph represents a set of valid placements
Definition: graph_m4ri.h:91
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
Definition: graph_m4ri.cpp:679
static bool has_bits(mzd_t *M, int row, int i, int j)
query bits in a Boolean matrix
Definition: graph_m4ri.cpp:585
Graph::ptr A
if this graph was constructed as transitive closure: original graphs this = MERGE(A,...
Definition: graph_m4ri.h:106
int blevel
bottom-level (for topologial sorting; leaves = blevel 0
Definition: graph_m4ri.h:97
virtual void queryDiagonalElement() const
find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result o...
Definition: graph_m4ri.cpp:437
const GraphModel & model
Definition: graph_boost.h:55
static void set_bits(mzd_t *M, int row, int i, int j)
set some bits in a Boolean matrix
Definition: graph_m4ri.cpp:556
const GraphModel::ptr graphModel() const
Definition: graph_m4ri.h:198
The Reachability Structure; maintains a list of intervals on the border of Free Space,...
Definition: structure.h:32
const IndexRange & hmask() const
horizontal range covered by this graph
Definition: graph_m4ri.h:187
virtual void resetConditions()
implemented by GraphCL
Definition: graph_m4ri.h:434
int succesors
number of successors
Definition: graph_m4ri.h:99
void printOrigin(std::ostream &out) const
debug output
Definition: graph_m4ri.cpp:162
virtual void finalize()
release memory that is not neeeded (empty sub-graphs)
Definition: graph_m4ri.cpp:199
Rect rect(Orientation o1, Orientation o2) const
range covered by this graph
Definition: graph_m4ri.cpp:94
static bool is_adjacent_to(const Graph &A, const Graph &B)
Definition: graph_m4ri.cpp:775
Graph & operator=(const Graph &)
Definition: graph_boost.cpp:64
this graph is the result of a MERGE operation (transitive closure) on three graphs
Definition: graph_m4ri.h:94
enum frechet::reach::Graph::Origin::@7 operation
IndexRange mask[2]
Definition: graph_m4ri.h:72
virtual int foundDiagonalElement() const
Definition: graph_m4ri.cpp:450
bool operator==(const Graph &that) const
comparison operator
Definition: graph_m4ri.cpp:240