BALL  1.5.0
graphAlgorithms.h
Go to the documentation of this file.
1 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
2 #define BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
3 
4 #ifndef BALL_COMMON_GLOBAL_H
5 # include <BALL/COMMON/global.h>
6 #endif
7 
8 #ifndef BALL_COMMON_EXCEPTION_H
9 # include <BALL/COMMON/exception.h>
10 #endif
11 
12 #ifndef BALL_DATATYPE_STRING_H
13 # include <BALL/DATATYPE/string.h>
14 #endif
15 
16 #include <boost/graph/properties.hpp>
17 #include <boost/graph/graph_traits.hpp>
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/graph/tree_traits.hpp>
20 #include <boost/graph/iteration_macros.hpp>
21 #include <boost/graph/copy.hpp>
22 #include <boost/shared_ptr.hpp>
23 
24 #include <iostream>
25 
26 namespace boost
27 {
30 
33 
34  BOOST_INSTALL_PROPERTY(vertex, atom_ptr);
35  BOOST_INSTALL_PROPERTY(vertex, orig_ptr);
36 
37  BOOST_INSTALL_PROPERTY(edge, bond_ptr);
38  BOOST_INSTALL_PROPERTY(edge, orig_ptr);
39 }
40 
41 namespace BALL
42 {
43  namespace GRAPH
44  {
45  template <class UndirectedGraph> class UndoEliminateOperation;
46 
54  {
55  public:
56  IllegalStateException(const char* file, int line, String message);
57  };
58 
64  {
65  public:
66  UnconnectedGraphException(const char * file, int line);
67  UnconnectedGraphException(const char * file, int line, BALL::String computation);
68  };
69 
73  template <class Graph>
75  {
76  public:
77  typedef typename boost::graph_traits<Graph>::vertex_descriptor VertexType;
78  typedef typename boost::graph_traits<Graph>::vertex_iterator VertexIterator;
79  typedef typename boost::graph_traits<Graph>::adjacency_iterator NeighbourIterator;
80  typedef typename boost::graph_traits<Graph>::edge_descriptor EdgeType;
81 
82  // this defines an editable version of the graph, i.e., a graph with list-based storage types
83  // that has property maps on the edges and vertices pointing to edges and vertices of an instance
84  // of the original graph type
85  typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
86  boost::property<boost::vertex_orig_ptr_t, VertexType,
87  boost::property<boost::vertex_index_t, int> >,
88  boost::property<boost::edge_orig_ptr_t, EdgeType> > EditableGraph;
89 
90  };
91 
92  template <typename Graph1, typename Graph2>
94  {
95  EditableEdgeCopier(const Graph1& /*g1*/, Graph2& g2)
96  : edge_orig_map(get(boost::edge_orig_ptr, g2))
97  {}
98 
99  template <typename Edge1, typename Edge2>
100  void operator()(const Edge1& e1, Edge2& e2) const
101  {
102  put(edge_orig_map, e2, e1);
103  }
104 
105  mutable typename boost::property_map<Graph2, boost::edge_orig_ptr_t>::type edge_orig_map;
106  };
107 
108  template <typename Graph1, typename Graph2>
110  makeEditableEdgeCopier(const Graph1& g1, Graph2& g2)
111  {
112  return EditableEdgeCopier<Graph1,Graph2>(g1, g2);
113  }
114 
115  template <typename Graph1, typename Graph2>
117  {
118  EditableVertexCopier(const Graph1& g1_, Graph2& g2_)
119  : vertex_orig_map(get(boost::vertex_orig_ptr, g2_)),
120  g1(g1_),
121  g2(g2_)
122  {}
123 
124  template <typename Vertex1, typename Vertex2>
125  void operator()(const Vertex1& v1, Vertex2& v2) const
126  {
127  boost::put(vertex_orig_map, v2, v1);
128  boost::put(boost::vertex_index, g2, v2, boost::get(boost::vertex_index, g1, v1));
129  }
130 
131  mutable typename boost::property_map<Graph2, boost::vertex_orig_ptr_t>::type vertex_orig_map;
132  Graph1 const& g1;
133  Graph2& g2;
134  };
135 
136  template <typename Graph1, typename Graph2>
138  makeEditableVertexCopier(const Graph1& g1, Graph2& g2)
139  {
141  }
142 
148  template <class UndirectedGraph>
149  void eliminateVertex(typename GraphTraits<UndirectedGraph>::VertexType& vertex, UndirectedGraph& graph)
150  {
151  typename GraphTraits<UndirectedGraph>::NeighbourIterator ai, bi, ai_end;
152 
153  for (boost::tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai)
154  {
155  bi = ai; ++bi;
156  for (; bi != ai_end; ++bi)
157  if (*bi != *ai && !boost::edge(*ai, *bi, graph).second)
158  boost::add_edge(*ai, *bi, graph);
159  }
160 
161  boost::clear_vertex(vertex, graph);
162  boost::remove_vertex(vertex, graph);
163  }
164 
173  template <class UndirectedGraph>
175  UndirectedGraph& graph)
176  {
177  typename GraphTraits<UndirectedGraph>::NeighbourIterator ai, bi, ai_end;
178  UndoEliminateOperation<UndirectedGraph> result(graph, vertex);
179 
180  for (boost::tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai)
181  {
182  result.getNeighbours().push_back(boost::get(boost::vertex_index, graph, *ai));
183 
184  result.getEdgeProperties().push_back(boost::get(boost::edge_all_t(), graph, boost::edge(vertex, *ai, graph).first));
185 
186  bi = ai; ++bi;
187  for (; bi != ai_end; ++bi)
188  {
189  if (!boost::edge(*ai, *bi, graph).second)
190  {
191  boost::add_edge(*ai, *bi, graph);
192  result.getEdges().push_back(std::make_pair(boost::get(boost::vertex_index, graph, *ai),
193  boost::get(boost::vertex_index, graph, *bi)));
194  }
195  }
196  }
197 
198  boost::clear_vertex(vertex, graph);
199  boost::remove_vertex(vertex, graph);
200 
201  return result;
202  }
203 
213  template <class UndirectedGraph>
214  class UndoEliminateOperation
215  {
216  public:
217  typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor VertexType;
218  typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor EdgeType;
219  typedef typename boost::graph_traits<UndirectedGraph>::adjacency_iterator NeighbourIterator;
220 
221  typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph,
222  boost::vertex_all_t>::type>::value_type VertexProperties;
223  typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph,
224  boost::edge_all_t>::type>::value_type EdgeProperties;
225 
229  UndoEliminateOperation(UndirectedGraph& graph, VertexType const& a);
230 
235 
241  VertexType undo();
242 
243  std::vector<std::pair<int, int> >& getEdges() { return edges_; }
244  std::vector<EdgeProperties>& getEdgeProperties() { return edge_properties_; }
245  std::vector<int>& getNeighbours() { return neighbours_; }
246 
247  protected:
248  UndirectedGraph* graph;
251  std::vector<std::pair<int, int> > edges_;
252  std::vector<EdgeProperties> edge_properties_;
253  std::vector<int> neighbours_;
254  bool applied;
255  };
256 
257  template <class UndirectedGraph>
259  : graph(&ugraph),
260  vertex(a),
261  edges_(),
262  neighbours_(),
263  applied(true)
264  {
265  vertex_properties_ = boost::get(boost::vertex_all_t(), ugraph, a);
266  }
267 
268  template <class UndirectedGraph>
271  {
272  return vertex;
273  }
274 
275  template <class UndirectedGraph>
277  {
278  if (!applied)
279  {
280  throw IllegalStateException(__FILE__, __LINE__, "Can't undo an elimination twice");
281  }
282 
283  applied = false;
284 
285  VertexType v = boost::add_vertex(vertex_properties_, *graph);
286 
287  std::map<int, VertexType> index_to_vertex;
288  BGL_FORALL_VERTICES_T(v, *graph, UndirectedGraph)
289  {
290  index_to_vertex[boost::get(boost::vertex_index, *graph, v)] = v;
291  }
292 
293  for (Position i=0; i<neighbours_.size(); ++i)
294  {
295  boost::add_edge(v, index_to_vertex[neighbours_[i]], edge_properties_[i], *graph);
296  }
297 
298  for (Position i=0; i<edges_.size(); ++i)
299  {
300  boost::remove_edge(index_to_vertex[edges_[i].first], index_to_vertex[edges_[i].second], *graph);
301  }
302 
303  return v;
304  }
305 
306  template <class UndirectedGraph>
307  void deepCopy(const UndirectedGraph& src, UndirectedGraph& target)
308  {
309  typedef std::map<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor,int> VertexIndexMap;
310  typedef boost::associative_property_map<VertexIndexMap> VertexIndexPropertyMap;
311 
312  VertexIndexMap vertex_map;
313  VertexIndexPropertyMap vertex_property_map(vertex_map);
314 
315  typename boost::graph_traits<UndirectedGraph>::vertices_size_type count = 0;
316 
317  typename boost::graph_traits<UndirectedGraph>::vertex_iterator vi, vend;
318  for (boost::tie(vi, vend) = boost::vertices(src); vi != vend; ++vi)
319  vertex_map[*vi] = count++;
320 
321  boost::copy_graph(src, target, vertex_index_map(vertex_property_map));
322  }
323 
324  template <class Tree, class From, class To, class Functor>
326  {
327  public:
328  typedef typename Tree::children_iterator ChildrenIterator;
329 
330  typedef typename std::vector<To>::iterator ArgumentIterator;
331 
332  PostOrderFolding(Tree& tree, Functor& f)
333  : return_stack_(boost::shared_ptr<std::vector<To> >(new std::vector<To>())),
334  tree_(&tree),
335  f_(&f)
336  {
337  boost::traverse_tree(root(*tree_), *tree_, *this);
338  }
339 
341  {
342  return *return_stack_->begin();
343  }
344 
345  template <class Node>
346  void preorder(Node, Tree&)
347  {
348  }
349 
350  template <class Node>
351  void inorder(Node, Tree&)
352  {
353  }
354 
355  template <class Node>
356  void postorder(Node n, Tree& t)
357  {
358  ChildrenIterator c_i, c_end;
359  boost::tie(c_i, c_end) = children(n, t);
360 
361  bool is_leaf = (c_i == c_end);
362 
363  ArgumentIterator begin_arg = return_stack_->end();
364  ArgumentIterator end_arg = return_stack_->end();
365 
366  if (!is_leaf)
367  {
368  for (; c_i != c_end; ++c_i)
369  {
370  --begin_arg;
371  }
372  }
373 
374  To value = (*f_)(n, begin_arg, end_arg);
375 
376  if (begin_arg != end_arg)
377  {
378  return_stack_->erase(begin_arg, end_arg);
379  }
380 
381  return_stack_->push_back(value);
382  }
383 
384  protected:
385  boost::shared_ptr<std::vector<To> > return_stack_;
386 
387  Tree* tree_;
388  Functor* f_;
389  };
390 
391  }
392 }
393 
394 #endif // BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
395 
396 
BALL::GRAPH::eliminateVertex
void eliminateVertex(typename GraphTraits< UndirectedGraph >::VertexType &vertex, UndirectedGraph &graph)
Definition: graphAlgorithms.h:149
BALL::GRAPH::PostOrderFolding
Definition: graphAlgorithms.h:325
BALL::GRAPH::UndoEliminateOperation::VertexProperties
boost::property_traits< typename boost::property_map< UndirectedGraph, boost::vertex_all_t >::type >::value_type VertexProperties
Definition: graphAlgorithms.h:222
BALL_EXPORT
#define BALL_EXPORT
Definition: COMMON/global.h:50
BALL::GRAPH::PostOrderFolding::preorder
void preorder(Node, Tree &)
Definition: graphAlgorithms.h:346
BALL::GRAPH::IllegalStateException
Definition: graphAlgorithms.h:52
BALL::GRAPH::PostOrderFolding::ArgumentIterator
std::vector< To >::iterator ArgumentIterator
Definition: graphAlgorithms.h:330
BALL::GRAPH::eliminateVertexUndoable
UndoEliminateOperation< UndirectedGraph > eliminateVertexUndoable(typename GraphTraits< UndirectedGraph >::VertexType const &vertex, UndirectedGraph &graph)
Definition: graphAlgorithms.h:174
BALL::GRAPH::UndoEliminateOperation::graph
UndirectedGraph * graph
Definition: graphAlgorithms.h:248
BALL::GRAPH::EditableEdgeCopier::EditableEdgeCopier
EditableEdgeCopier(const Graph1 &, Graph2 &g2)
Definition: graphAlgorithms.h:95
BALL::GRAPH::EditableVertexCopier
Definition: graphAlgorithms.h:116
boost::vertex_atom_ptr_t
vertex_atom_ptr_t
Definition: graphAlgorithms.h:28
BALL::GRAPH::PostOrderFolding::inorder
void inorder(Node, Tree &)
Definition: graphAlgorithms.h:351
BALL::Exception::GeneralException
Definition: COMMON/exception.h:59
BALL::GRAPH::GraphTraits
Definition: graphAlgorithms.h:74
BALL::GRAPH::UndoEliminateOperation
Definition: graphAlgorithms.h:45
BALL::GRAPH::UndoEliminateOperation::EdgeProperties
boost::property_traits< typename boost::property_map< UndirectedGraph, boost::edge_all_t >::type >::value_type EdgeProperties
Definition: graphAlgorithms.h:224
BALL::GRAPH::UndoEliminateOperation::neighbours_
std::vector< int > neighbours_
Definition: graphAlgorithms.h:253
BALL::GRAPH::UndoEliminateOperation::UndoEliminateOperation
UndoEliminateOperation(UndirectedGraph &graph, VertexType const &a)
Definition: graphAlgorithms.h:258
BALL_SIZE_TYPE
BALL::GRAPH::UndoEliminateOperation::edges_
std::vector< std::pair< int, int > > edges_
Definition: graphAlgorithms.h:251
boost
Definition: graphAlgorithms.h:26
BALL::GRAPH::UndoEliminateOperation::getEliminatedVertex
VertexType & getEliminatedVertex()
Definition: graphAlgorithms.h:270
BALL::GRAPH::EditableVertexCopier::g2
Graph2 & g2
Definition: graphAlgorithms.h:133
BALL::GRAPH::PostOrderFolding::getResult
To getResult()
Definition: graphAlgorithms.h:340
boost::vertex_orig_ptr_t
vertex_orig_ptr_t
Definition: graphAlgorithms.h:29
BALL::GRAPH::makeEditableEdgeCopier
EditableEdgeCopier< Graph1, Graph2 > makeEditableEdgeCopier(const Graph1 &g1, Graph2 &g2)
Definition: graphAlgorithms.h:110
BALL::GRAPH::UndoEliminateOperation::EdgeType
boost::graph_traits< UndirectedGraph >::edge_descriptor EdgeType
Definition: graphAlgorithms.h:218
BALL::GRAPH::PostOrderFolding::f_
Functor * f_
Definition: graphAlgorithms.h:388
BALL::GRAPH::GraphTraits::EditableGraph
boost::adjacency_list< boost::listS, boost::listS, boost::undirectedS, boost::property< boost::vertex_orig_ptr_t, VertexType, boost::property< boost::vertex_index_t, int > >, boost::property< boost::edge_orig_ptr_t, EdgeType > > EditableGraph
Definition: graphAlgorithms.h:88
BALL
Definition: constants.h:12
BALL::GRAPH::EditableVertexCopier::EditableVertexCopier
EditableVertexCopier(const Graph1 &g1_, Graph2 &g2_)
Definition: graphAlgorithms.h:118
BALL::GRAPH::UndoEliminateOperation::undo
VertexType undo()
Definition: graphAlgorithms.h:276
BALL::String
Definition: string.h:56
boost::BOOST_INSTALL_PROPERTY
BOOST_INSTALL_PROPERTY(vertex, atom_ptr)
exception.h
BALL::GRAPH::GraphTraits::VertexIterator
boost::graph_traits< Graph >::vertex_iterator VertexIterator
Definition: graphAlgorithms.h:78
BALL::GRAPH::PostOrderFolding::tree_
Tree * tree_
Definition: graphAlgorithms.h:387
BALL::GRAPH::UndoEliminateOperation::VertexType
boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
Definition: graphAlgorithms.h:217
BALL::GRAPH::UndoEliminateOperation::vertex_properties_
VertexProperties vertex_properties_
Definition: graphAlgorithms.h:250
BALL::GRAPH::deepCopy
void deepCopy(const UndirectedGraph &src, UndirectedGraph &target)
Definition: graphAlgorithms.h:307
boost::edge_orig_ptr_t
edge_orig_ptr_t
Definition: graphAlgorithms.h:32
BALL::GRAPH::UndoEliminateOperation::NeighbourIterator
boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
Definition: graphAlgorithms.h:219
BALL::VIEW::Vertex2
Definition: vertex2.h:32
BALL::GRAPH::PostOrderFolding::return_stack_
boost::shared_ptr< std::vector< To > > return_stack_
Definition: graphAlgorithms.h:385
BALL::GRAPH::UndoEliminateOperation::getEdges
std::vector< std::pair< int, int > > & getEdges()
Definition: graphAlgorithms.h:243
BALL::GRAPH::UndoEliminateOperation::getNeighbours
std::vector< int > & getNeighbours()
Definition: graphAlgorithms.h:245
boost::edge_orig_ptr
Definition: graphAlgorithms.h:32
BALL::GRAPH::UndoEliminateOperation::applied
bool applied
Definition: graphAlgorithms.h:254
boost::edge_bond_ptr
Definition: graphAlgorithms.h:31
BALL::GRAPH::GraphTraits::NeighbourIterator
boost::graph_traits< Graph >::adjacency_iterator NeighbourIterator
Definition: graphAlgorithms.h:79
BALL::GRAPH::EditableVertexCopier::operator()
void operator()(const Vertex1 &v1, Vertex2 &v2) const
Definition: graphAlgorithms.h:125
BALL::GRAPH::makeEditableVertexCopier
EditableVertexCopier< Graph1, Graph2 > makeEditableVertexCopier(const Graph1 &g1, Graph2 &g2)
Definition: graphAlgorithms.h:138
BALL::GRAPH::PostOrderFolding::postorder
void postorder(Node n, Tree &t)
Definition: graphAlgorithms.h:356
BALL::GRAPH::UndoEliminateOperation::edge_properties_
std::vector< EdgeProperties > edge_properties_
Definition: graphAlgorithms.h:252
boost::vertex_orig_ptr
Definition: graphAlgorithms.h:29
string.h
BALL::GRAPH::GraphTraits::VertexType
boost::graph_traits< Graph >::vertex_descriptor VertexType
Definition: graphAlgorithms.h:77
boost::edge_bond_ptr_t
edge_bond_ptr_t
Definition: graphAlgorithms.h:31
BALL::GRAPH::EditableVertexCopier::vertex_orig_map
boost::property_map< Graph2, boost::vertex_orig_ptr_t >::type vertex_orig_map
Definition: graphAlgorithms.h:131
BALL::GRAPH::EditableEdgeCopier
Definition: graphAlgorithms.h:93
BALL::GRAPH::EditableVertexCopier::g1
Graph1 const & g1
Definition: graphAlgorithms.h:132
BALL::GRAPH::UndoEliminateOperation::getEdgeProperties
std::vector< EdgeProperties > & getEdgeProperties()
Definition: graphAlgorithms.h:244
BALL::GRAPH::PostOrderFolding::ChildrenIterator
Tree::children_iterator ChildrenIterator
Definition: graphAlgorithms.h:328
global.h
BALL::GRAPH::UnconnectedGraphException
Definition: graphAlgorithms.h:62
BALL::GRAPH::PostOrderFolding::PostOrderFolding
PostOrderFolding(Tree &tree, Functor &f)
Definition: graphAlgorithms.h:332
BALL::GRAPH::UndoEliminateOperation::vertex
VertexType vertex
Definition: graphAlgorithms.h:249
BALL::GRAPH::GraphTraits::EdgeType
boost::graph_traits< Graph >::edge_descriptor EdgeType
Definition: graphAlgorithms.h:80
BALL::GRAPH::EditableEdgeCopier::operator()
void operator()(const Edge1 &e1, Edge2 &e2) const
Definition: graphAlgorithms.h:100
BALL::GRAPH::EditableEdgeCopier::edge_orig_map
boost::property_map< Graph2, boost::edge_orig_ptr_t >::type edge_orig_map
Definition: graphAlgorithms.h:105
boost::vertex_atom_ptr
Definition: graphAlgorithms.h:28