BALL 1.5.0
Loading...
Searching...
No Matches
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
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
40
41namespace 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 {
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 {
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 {
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>
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
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_;
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>
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
STL namespace.
@ vertex_orig_ptr
@ vertex_atom_ptr
BOOST_INSTALL_PROPERTY(vertex, atom_ptr)
void eliminateVertex(typename GraphTraits< UndirectedGraph >::VertexType &vertex, UndirectedGraph &graph)
EditableVertexCopier< Graph1, Graph2 > makeEditableVertexCopier(const Graph1 &g1, Graph2 &g2)
EditableEdgeCopier< Graph1, Graph2 > makeEditableEdgeCopier(const Graph1 &g1, Graph2 &g2)
UndoEliminateOperation< UndirectedGraph > eliminateVertexUndoable(typename GraphTraits< UndirectedGraph >::VertexType const &vertex, UndirectedGraph &graph)
void deepCopy(const UndirectedGraph &src, UndirectedGraph &target)
UndoEliminateOperation(UndirectedGraph &graph, VertexType const &a)
std::vector< EdgeProperties > & getEdgeProperties()
std::vector< EdgeProperties > edge_properties_
boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
std::vector< std::pair< int, int > > & getEdges()
boost::property_traits< typenameboost::property_map< UndirectedGraph, boost::vertex_all_t >::type >::value_type VertexProperties
boost::graph_traits< UndirectedGraph >::edge_descriptor EdgeType
boost::property_traits< typenameboost::property_map< UndirectedGraph, boost::edge_all_t >::type >::value_type EdgeProperties
std::vector< std::pair< int, int > > edges_
IllegalStateException(const char *file, int line, String message)
UnconnectedGraphException(const char *file, int line, BALL::String computation)
UnconnectedGraphException(const char *file, int line)
boost::graph_traits< Graph >::edge_descriptor EdgeType
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
boost::graph_traits< Graph >::vertex_iterator VertexIterator
boost::graph_traits< Graph >::adjacency_iterator NeighbourIterator
boost::graph_traits< Graph >::vertex_descriptor VertexType
void operator()(const Edge1 &e1, Edge2 &e2) const
EditableEdgeCopier(const Graph1 &, Graph2 &g2)
boost::property_map< Graph2, boost::edge_orig_ptr_t >::type edge_orig_map
void operator()(const Vertex1 &v1, Vertex2 &v2) const
boost::property_map< Graph2, boost::vertex_orig_ptr_t >::type vertex_orig_map
EditableVertexCopier(const Graph1 &g1_, Graph2 &g2_)
PostOrderFolding(Tree &tree, Functor &f)
Tree::children_iterator ChildrenIterator
std::vector< To >::iterator ArgumentIterator
boost::shared_ptr< std::vector< To > > return_stack_
void postorder(Node n, Tree &t)
#define BALL_EXPORT