Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
graph_boost.cpp
Go to the documentation of this file.
1 //
2 // Created by nightrider on 19.08.18.
3 //
4 
5 #include <frechet/reachability/graph.h>
6 #include <boost/graph/transitive_closure.hpp>
7 #include <boost/graph/copy.hpp>
8 #include <boost/graph/graphviz.hpp>
9 
11  : model(amodel), g(ag), i2v()
12 {
13  // TODO if g is not empty, i2v needs to be updated
14 }
15 
17  : Graph(amodel, new graph_t())
18 { }
19 
20 
23  : Graph(amodel)
24 {
25  // unify intervals
26  model.refine(str, i0);
27  // assign indexes to intervals
28  // TODO unless already done by refine !!??
29  model.indexify(str, i0);
30 
31  // insert edges into the graph
32  copy(str, str.left().first(), str.right().first());
33  copy(str, str.bottom().first(), str.top().first());
34  // TODO what about backward pointers ?
35 }
36 
38  : Graph(that.model,nullptr)
39 {
40  copy(that);
41 }
42 
44  : Graph(that.model,nullptr)
45 {
46  swap(that);
47 }
48 
50 {
51  delete g;
52 }
53 
55 {
56  return boost::num_vertices(*g);
57 }
58 
60 {
61  return boost::num_edges(*g);
62 }
63 
65 {
66  Q_ASSERT(&model == &that.model);
67  copy(that);
68  return *this;
69 }
70 
72 {
73  swap(that);
74  return *this;
75 }
76 
78 {
79  Vertex2IndexMap v2i = boost::get(boost::vertex_index,*B.g);
80  boost::graph_traits<graph_t>::edge_iterator ei, ei_end;
81  for (boost::tie(ei, ei_end) = boost::edges(*B.g); ei != ei_end; ++ei)
82  {
83  vertex_t v1 = boost::source(*ei,*g);
84  vertex_t v2 = boost::target(*ei,*g);
85 
86  int i1 = boost::get(v2i,v1);
87  int i2 = boost::get(v2i,v2);
88 
89  this->add_edge(i1,i2);
90  }
91  return *this;
92 }
93 
95 {
96  delete g;
97  g = new graph_t();
98  i2v.clear();
99  //v2i = boost::get(boost::vertex_index,*g);
100 }
101 
103 {
104  clear();
105  operator+= (B);
106 }
107 
109 {
110  Q_ASSERT(&model == &that.model);
111  std::swap(g,that.g);
112  //std::swap(v2i,that.v2i);
113  std::swap(i2v,that.i2v);
114 }
115 
116 
118 {
119  for( ; i1; i1=i1->next(), i2=i2->next())
120  {
121  if (i1->type==NON_ACCESSIBLE) continue;
122  // traverse all reachable intervals
123  StructureIterator i (str, *i1, i2);
124  for( ; i; ++i) {
125  if(i->type==NON_ACCESSIBLE) continue;
126  add_edge(i1->index(), i->index());
127  }
128  }
129 }
130 
132 {
133  vertex_t v;
134  auto f = i2v.find(i);
135 
136  if (f==i2v.end()) {
137  v = boost::add_vertex(Index(i,i),*g);
138  i2v.insert(std::make_pair(i,v));
139  }
140  else {
141  v = f->second;
142  }
143  Q_ASSERT(boost::get(boost::get(boost::vertex_index,*g),v) == i);
144  return v;
145 }
146 
148 {
149  vertex_t v1 = vertex(i);
150  vertex_t v2 = vertex(j);
151  // TODO avoid duplicate edges
152  // boost::adjacency_list < boost::setS is essential !!
153  boost::add_edge(v1,v2,*g);
154 }
155 
156 
158 {
159  boost::adjacency_list<>* tc = new graph_t();
160  boost::transitive_closure (*g,*tc);
161  return Graph::ptr(new Graph(model,(graph_t*)tc));
162 }
163 
165 {
166  // TODO can this work ?? I doubt...
167 // boost::transitive_closure (*g,*g);
168  graph_t* tc = new graph_t();
169  boost::transitive_closure (*g,*tc);
170 
171  delete g;
172  g = tc;
173  // TODO i2v needs to be updated
174 }
175 
Graph & operator+=(const Graph &)
Definition: graph_boost.cpp:77
Index2VertexMap i2v
Definition: graph_boost.h:53
void swap(gpuword **A, gpuword **B)
boost::graph_traits< graph_t >::vertex_descriptor vertex_t
Definition: graph_boost.h:46
void copy(const Graph &)
Graph::ptr transitiveClosure() const
vertex_t vertex(int i)
model the mapping of free-space intervals to nodes in a frechet::reach::Graph.
Definition: graph_boost.h:109
boost::adjacency_list< boost::setS, boost::listS, boost::directedS, Index > graph_t
Definition: graph_boost.h:44
non-accesible. no interval is reachable from this one
Definition: boundary.h:19
The StructureIterator class.
Definition: structure.h:488
void indexify(Structure &str, int i0) const
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
Definition: boundary.h:285
Type type
reachability label
Definition: boundary.h:317
boost::property< boost::vertex_index_t, std::size_t, Name > Index
Definition: graph_boost.h:43
boost::shared_ptr< Graph > ptr
Definition: graph_boost.h:59
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
#define str(S)
void add_edge(int i, int j)
void refine(Structure &str, int i0) const
const GraphModel & model
Definition: graph_boost.h:55
The Reachability Structure; maintains a list of intervals on the border of Free Space,...
Definition: structure.h:32
boost::property_map< graph_t, boost::vertex_index_t >::type Vertex2IndexMap
Definition: graph_boost.h:50
Graph & operator=(const Graph &)
Definition: graph_boost.cpp:64