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