1 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
2 #define BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
4 #ifndef BALL_COMMON_GLOBAL_H
8 #ifndef BALL_COMMON_EXCEPTION_H
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>
69 template <
class Graph>
73 typedef typename boost::graph_traits<Graph>::vertex_descriptor
VertexType;
76 typedef typename boost::graph_traits<Graph>::edge_descriptor
EdgeType;
81 typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
83 boost::property<boost::vertex_index_t, int> >,
88 template <
typename Graph1,
typename Graph2>
95 template <
typename Edge1,
typename Edge2>
101 mutable typename boost::property_map<Graph2, boost::edge_orig_ptr_t>::type
edge_orig_map;
104 template <
typename Graph1,
typename Graph2>
111 template <
typename Graph1,
typename Graph2>
120 template <
typename Vertex1,
typename Vertex2>
124 boost::put(boost::vertex_index,
g2, v2, boost::get(boost::vertex_index,
g1, v1));
127 mutable typename boost::property_map<Graph2, boost::vertex_orig_ptr_t>::type
vertex_orig_map;
132 template <
typename Graph1,
typename Graph2>
144 template <
class UndirectedGraph>
149 for (tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai)
152 for (; bi != ai_end; ++bi)
153 if (*bi != *ai && !boost::edge(*ai, *bi, graph).second)
154 boost::add_edge(*ai, *bi, graph);
157 boost::clear_vertex(vertex, graph);
158 boost::remove_vertex(vertex, graph);
169 template <
class UndirectedGraph>
171 UndirectedGraph& graph)
176 for (tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai)
178 result.
getNeighbours().push_back(boost::get(boost::vertex_index, graph, *ai));
180 typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph, boost::edge_all_t>::type>::value_type EdgeProperties;
182 result.
getEdgeProperties().push_back(boost::get(boost::edge_all_t(), graph, boost::edge(vertex, *ai, graph).first));
185 for (; bi != ai_end; ++bi)
187 if (!boost::edge(*ai, *bi, graph).second)
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)));
196 boost::clear_vertex(vertex, graph);
197 boost::remove_vertex(vertex, graph);
211 template <
class UndirectedGraph>
215 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor
VertexType;
216 typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor
EdgeType;
219 typedef typename boost::property_traits<
typename boost::property_map<UndirectedGraph,
221 typedef typename boost::property_traits<
typename boost::property_map<UndirectedGraph,
249 std::vector<std::pair<int, int> >
edges_;
255 template <
class UndirectedGraph>
266 template <
class UndirectedGraph>
273 template <
class UndirectedGraph>
283 VertexType v = boost::add_vertex(vertex_properties_, *graph);
285 std::map<int, VertexType> index_to_vertex;
286 BGL_FORALL_VERTICES_T(v, *graph, UndirectedGraph)
288 index_to_vertex[boost::get(boost::vertex_index, *graph, v)] = v;
291 for (
Position i=0; i<neighbours_.size(); ++i)
293 boost::add_edge(v, index_to_vertex[neighbours_[i]], edge_properties_[i], *graph);
296 for (
Position i=0; i<edges_.size(); ++i)
298 boost::remove_edge(index_to_vertex[edges_[i].first], index_to_vertex[edges_[i].second], *graph);
304 template <
class UndirectedGraph>
305 void deepCopy(
const UndirectedGraph& src, UndirectedGraph& target)
307 typedef std::map<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor,
int> VertexIndexMap;
308 typedef boost::associative_property_map<VertexIndexMap> VertexIndexPropertyMap;
310 VertexIndexMap vertex_map;
311 VertexIndexPropertyMap vertex_property_map(vertex_map);
313 typename boost::graph_traits<UndirectedGraph>::vertices_size_type count = 0;
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++;
319 boost::copy_graph(src, target, vertex_index_map(vertex_property_map));
322 template <
class Tree,
class From,
class To,
class Functor>
331 :
return_stack_(boost::shared_ptr<std::vector<To> >(new std::vector<To>())),
335 boost::traverse_tree(root(*
tree_), *
tree_, *
this);
343 template <
class Node>
348 template <
class Node>
353 template <
class Node>
357 boost::tie(c_i, c_end) = children(n, t);
359 bool is_leaf = (c_i == c_end);
366 for (; c_i != c_end; ++c_i)
372 To value = (*f_)(n, begin_arg, end_arg);
374 if (begin_arg != end_arg)
392 #endif // BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H