1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/graph_utility.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,425 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +#ifndef BOOST_GRAPH_UTILITY_HPP
1.15 +#define BOOST_GRAPH_UTILITY_HPP
1.16 +
1.17 +#include <stdlib.h>
1.18 +#include <iostream>
1.19 +#include <algorithm>
1.20 +#include <assert.h>
1.21 +#include <boost/config.hpp>
1.22 +#include <boost/tuple/tuple.hpp>
1.23 +
1.24 +#if !defined BOOST_NO_SLIST
1.25 +# ifdef BOOST_SLIST_HEADER
1.26 +# include BOOST_SLIST_HEADER
1.27 +# else
1.28 +# include <slist>
1.29 +# endif
1.30 +#endif
1.31 +
1.32 +#include <boost/graph/graph_traits.hpp>
1.33 +#include <boost/graph/properties.hpp>
1.34 +#include <boost/pending/container_traits.hpp>
1.35 +#include <boost/graph/depth_first_search.hpp>
1.36 +// iota moved to detail/algorithm.hpp
1.37 +#include <boost/detail/algorithm.hpp>
1.38 +
1.39 +namespace boost {
1.40 +
1.41 + // Provide an undirected graph interface alternative to the
1.42 + // the source() and target() edge functions.
1.43 + template <class UndirectedGraph>
1.44 + inline
1.45 + std::pair<typename graph_traits<UndirectedGraph>::vertex_descriptor,
1.46 + typename graph_traits<UndirectedGraph>::vertex_descriptor>
1.47 + incident(typename graph_traits<UndirectedGraph>::edge_descriptor e,
1.48 + UndirectedGraph& g)
1.49 + {
1.50 + return std::make_pair(source(e,g), target(e,g));
1.51 + }
1.52 +
1.53 + // Provide an undirected graph interface alternative
1.54 + // to the out_edges() function.
1.55 + template <class Graph>
1.56 + inline
1.57 + std::pair<typename graph_traits<Graph>::out_edge_iterator,
1.58 + typename graph_traits<Graph>::out_edge_iterator>
1.59 + incident_edges(typename graph_traits<Graph>::vertex_descriptor u,
1.60 + Graph& g)
1.61 + {
1.62 + return out_edges(u, g);
1.63 + }
1.64 +
1.65 + template <class Graph>
1.66 + inline typename graph_traits<Graph>::vertex_descriptor
1.67 + opposite(typename graph_traits<Graph>::edge_descriptor e,
1.68 + typename graph_traits<Graph>::vertex_descriptor v,
1.69 + const Graph& g)
1.70 + {
1.71 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.72 + if (v == source(e, g))
1.73 + return target(e, g);
1.74 + else if (v == target(e, g))
1.75 + return source(e, g);
1.76 + else
1.77 + return vertex_descriptor();
1.78 + }
1.79 +
1.80 + //===========================================================================
1.81 + // Some handy predicates
1.82 +
1.83 + template <typename Vertex, typename Graph>
1.84 + struct incident_from_predicate {
1.85 + incident_from_predicate(Vertex u, const Graph& g)
1.86 + : m_u(u), m_g(g) { }
1.87 + template <class Edge>
1.88 + bool operator()(const Edge& e) const {
1.89 + return source(e, m_g) == m_u;
1.90 + }
1.91 + Vertex m_u;
1.92 + const Graph& m_g;
1.93 + };
1.94 + template <typename Vertex, typename Graph>
1.95 + inline incident_from_predicate<Vertex, Graph>
1.96 + incident_from(Vertex u, const Graph& g) {
1.97 + return incident_from_predicate<Vertex, Graph>(u, g);
1.98 + }
1.99 +
1.100 + template <typename Vertex, typename Graph>
1.101 + struct incident_to_predicate {
1.102 + incident_to_predicate(Vertex u, const Graph& g)
1.103 + : m_u(u), m_g(g) { }
1.104 + template <class Edge>
1.105 + bool operator()(const Edge& e) const {
1.106 + return target(e, m_g) == m_u;
1.107 + }
1.108 + Vertex m_u;
1.109 + const Graph& m_g;
1.110 + };
1.111 + template <typename Vertex, typename Graph>
1.112 + inline incident_to_predicate<Vertex, Graph>
1.113 + incident_to(Vertex u, const Graph& g) {
1.114 + return incident_to_predicate<Vertex, Graph>(u, g);
1.115 + }
1.116 +
1.117 + template <typename Vertex, typename Graph>
1.118 + struct incident_on_predicate {
1.119 + incident_on_predicate(Vertex u, const Graph& g)
1.120 + : m_u(u), m_g(g) { }
1.121 + template <class Edge>
1.122 + bool operator()(const Edge& e) const {
1.123 + return source(e, m_g) == m_u || target(e, m_g) == m_u;
1.124 + }
1.125 + Vertex m_u;
1.126 + const Graph& m_g;
1.127 + };
1.128 + template <typename Vertex, typename Graph>
1.129 + inline incident_on_predicate<Vertex, Graph>
1.130 + incident_on(Vertex u, const Graph& g) {
1.131 + return incident_on_predicate<Vertex, Graph>(u, g);
1.132 + }
1.133 +
1.134 + template <typename Vertex, typename Graph>
1.135 + struct connects_predicate {
1.136 + connects_predicate(Vertex u, Vertex v, const Graph& g)
1.137 + : m_u(u), m_v(v), m_g(g) { }
1.138 + template <class Edge>
1.139 + bool operator()(const Edge& e) const {
1.140 + if (is_directed(m_g))
1.141 + return source(e, m_g) == m_u && target(e, m_g) == m_v;
1.142 + else
1.143 + return (source(e, m_g) == m_u && target(e, m_g) == m_v)
1.144 + || (source(e, m_g) == m_v && target(e, m_g) == m_u);
1.145 + }
1.146 + Vertex m_u, m_v;
1.147 + const Graph& m_g;
1.148 + };
1.149 + template <typename Vertex, typename Graph>
1.150 + inline connects_predicate<Vertex, Graph>
1.151 + connects(Vertex u, Vertex v, const Graph& g) {
1.152 + return connects_predicate<Vertex, Graph>(u, v, g);
1.153 + }
1.154 +
1.155 +
1.156 + // Need to convert all of these printing functions to take an ostream object
1.157 + // -JGS
1.158 +
1.159 + template <class IncidenceGraph, class Name>
1.160 + void print_in_edges(const IncidenceGraph& G, Name name)
1.161 + {
1.162 + typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
1.163 + for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
1.164 + std::cout << get(name,*ui) << " <-- ";
1.165 + typename graph_traits<IncidenceGraph>
1.166 + ::in_edge_iterator ei, ei_end;
1.167 + for(tie(ei,ei_end) = in_edges(*ui,G); ei != ei_end; ++ei)
1.168 + std::cout << get(name,source(*ei,G)) << " ";
1.169 + std::cout << std::endl;
1.170 + }
1.171 + }
1.172 +
1.173 + template <class IncidenceGraph, class Name>
1.174 + void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag)
1.175 + {
1.176 + typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
1.177 + for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
1.178 + std::cout << get(name,*ui) << " --> ";
1.179 + typename graph_traits<IncidenceGraph>
1.180 + ::out_edge_iterator ei, ei_end;
1.181 + for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
1.182 + std::cout << get(name,target(*ei,G)) << " ";
1.183 + std::cout << std::endl;
1.184 + }
1.185 + }
1.186 + template <class IncidenceGraph, class Name>
1.187 + void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag)
1.188 + {
1.189 + typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
1.190 + for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
1.191 + std::cout << get(name,*ui) << " <--> ";
1.192 + typename graph_traits<IncidenceGraph>
1.193 + ::out_edge_iterator ei, ei_end;
1.194 + for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
1.195 + std::cout << get(name,target(*ei,G)) << " ";
1.196 + std::cout << std::endl;
1.197 + }
1.198 + }
1.199 + template <class IncidenceGraph, class Name>
1.200 + void print_graph(const IncidenceGraph& G, Name name)
1.201 + {
1.202 + typedef typename graph_traits<IncidenceGraph>
1.203 + ::directed_category Cat;
1.204 + print_graph_dispatch(G, name, Cat());
1.205 + }
1.206 + template <class IncidenceGraph>
1.207 + void print_graph(const IncidenceGraph& G) {
1.208 + print_graph(G, get(vertex_index, G));
1.209 + }
1.210 +
1.211 + template <class EdgeListGraph, class Name>
1.212 + void print_edges(const EdgeListGraph& G, Name name)
1.213 + {
1.214 + typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
1.215 + for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
1.216 + std::cout << "(" << get(name, source(*ei, G))
1.217 + << "," << get(name, target(*ei, G)) << ") ";
1.218 + std::cout << std::endl;
1.219 + }
1.220 +
1.221 + template <class EdgeListGraph, class VertexName, class EdgeName>
1.222 + void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename)
1.223 + {
1.224 + typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
1.225 + for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
1.226 + std::cout << get(ename, *ei) << "(" << get(vname, source(*ei, G))
1.227 + << "," << get(vname, target(*ei, G)) << ") ";
1.228 + std::cout << std::endl;
1.229 + }
1.230 +
1.231 + template <class VertexListGraph, class Name>
1.232 + void print_vertices(const VertexListGraph& G, Name name)
1.233 + {
1.234 + typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end;
1.235 + for (tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi)
1.236 + std::cout << get(name,*vi) << " ";
1.237 + std::cout << std::endl;
1.238 + }
1.239 +
1.240 + template <class Graph, class Vertex>
1.241 + bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
1.242 + {
1.243 + typedef typename graph_traits<Graph>::edge_descriptor
1.244 + edge_descriptor;
1.245 + typename graph_traits<Graph>::adjacency_iterator vi, viend,
1.246 + adj_found;
1.247 + tie(vi, viend) = adjacent_vertices(a, g);
1.248 + adj_found = std::find(vi, viend, b);
1.249 + if (adj_found == viend)
1.250 + return false;
1.251 +
1.252 + typename graph_traits<Graph>::out_edge_iterator oi, oiend,
1.253 + out_found;
1.254 + tie(oi, oiend) = out_edges(a, g);
1.255 + out_found = std::find_if(oi, oiend, incident_to(b, g));
1.256 + if (out_found == oiend)
1.257 + return false;
1.258 +
1.259 + typename graph_traits<Graph>::in_edge_iterator ii, iiend,
1.260 + in_found;
1.261 + tie(ii, iiend) = in_edges(b, g);
1.262 + in_found = std::find_if(ii, iiend, incident_from(a, g));
1.263 + if (in_found == iiend)
1.264 + return false;
1.265 +
1.266 + return true;
1.267 + }
1.268 + template <class Graph, class Vertex>
1.269 + bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
1.270 + {
1.271 + typedef typename graph_traits<Graph>::edge_descriptor
1.272 + edge_descriptor;
1.273 + typename graph_traits<Graph>::adjacency_iterator vi, viend, found;
1.274 + tie(vi, viend) = adjacent_vertices(a, g);
1.275 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
1.276 + // Getting internal compiler error with std::find()
1.277 + found = viend;
1.278 + for (; vi != viend; ++vi)
1.279 + if (*vi == b) {
1.280 + found = vi;
1.281 + break;
1.282 + }
1.283 +#else
1.284 + found = std::find(vi, viend, b);
1.285 +#endif
1.286 + if ( found == viend )
1.287 + return false;
1.288 +
1.289 + typename graph_traits<Graph>::out_edge_iterator oi, oiend,
1.290 + out_found;
1.291 + tie(oi, oiend) = out_edges(a, g);
1.292 +
1.293 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
1.294 + // Getting internal compiler error with std::find()
1.295 + out_found = oiend;
1.296 + for (; oi != oiend; ++oi)
1.297 + if (target(*oi, g) == b) {
1.298 + out_found = oi;
1.299 + break;
1.300 + }
1.301 +#else
1.302 + out_found = std::find_if(oi, oiend, incident_to(b, g));
1.303 +#endif
1.304 + if (out_found == oiend)
1.305 + return false;
1.306 + return true;
1.307 + }
1.308 + template <class Graph, class Vertex>
1.309 + bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
1.310 + {
1.311 + return is_adj_dispatch(g, a, b, directed_tag());
1.312 + }
1.313 +
1.314 + template <class Graph, class Vertex>
1.315 + bool is_adjacent(Graph& g, Vertex a, Vertex b) {
1.316 + typedef typename graph_traits<Graph>::directed_category Cat;
1.317 + return is_adj_dispatch(g, a, b, Cat());
1.318 + }
1.319 +
1.320 + template <class Graph, class Edge>
1.321 + bool in_edge_set(Graph& g, Edge e)
1.322 + {
1.323 + typename Graph::edge_iterator ei, ei_end, found;
1.324 + tie(ei, ei_end) = edges(g);
1.325 + found = std::find(ei, ei_end, e);
1.326 + return found != ei_end;
1.327 + }
1.328 +
1.329 + template <class Graph, class Vertex>
1.330 + bool in_vertex_set(Graph& g, Vertex v)
1.331 + {
1.332 + typename Graph::vertex_iterator vi, vi_end, found;
1.333 + tie(vi, vi_end) = vertices(g);
1.334 + found = std::find(vi, vi_end, v);
1.335 + return found != vi_end;
1.336 + }
1.337 +
1.338 + template <class Graph, class Vertex>
1.339 + bool in_edge_set(Graph& g, Vertex u, Vertex v)
1.340 + {
1.341 + typename Graph::edge_iterator ei, ei_end;
1.342 + for (tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
1.343 + if (source(*ei,g) == u && target(*ei,g) == v)
1.344 + return true;
1.345 + return false;
1.346 + }
1.347 +
1.348 + // is x a descendant of y?
1.349 + template <typename ParentMap>
1.350 + inline bool is_descendant
1.351 + (typename property_traits<ParentMap>::value_type x,
1.352 + typename property_traits<ParentMap>::value_type y,
1.353 + ParentMap parent)
1.354 + {
1.355 + if (get(parent, x) == x) // x is the root of the tree
1.356 + return false;
1.357 + else if (get(parent, x) == y)
1.358 + return true;
1.359 + else
1.360 + return is_descendant(get(parent, x), y, parent);
1.361 + }
1.362 +
1.363 + // is y reachable from x?
1.364 + template <typename IncidenceGraph, typename VertexColorMap>
1.365 + inline bool is_reachable
1.366 + (typename graph_traits<IncidenceGraph>::vertex_descriptor x,
1.367 + typename graph_traits<IncidenceGraph>::vertex_descriptor y,
1.368 + const IncidenceGraph& g,
1.369 + VertexColorMap color) // should start out white for every vertex
1.370 + {
1.371 + typedef typename property_traits<VertexColorMap>::value_type ColorValue;
1.372 + dfs_visitor<> vis;
1.373 + depth_first_visit(g, x, vis, color);
1.374 + return get(color, y) != color_traits<ColorValue>::white();
1.375 + }
1.376 +
1.377 + // Is the undirected graph connected?
1.378 + // Is the directed graph strongly connected?
1.379 + template <typename VertexListGraph, typename VertexColorMap>
1.380 + inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
1.381 + {
1.382 + typedef typename property_traits<VertexColorMap>::value_type ColorValue;
1.383 + typedef color_traits<ColorValue> Color;
1.384 + typename graph_traits<VertexListGraph>::vertex_iterator
1.385 + ui, ui_end, vi, vi_end, ci, ci_end;
1.386 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
1.387 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.388 + if (*ui != *vi) {
1.389 + for (tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci)
1.390 + put(color, *ci, Color::white());
1.391 + if (! is_reachable(*ui, *vi, color))
1.392 + return false;
1.393 + }
1.394 + return true;
1.395 + }
1.396 +
1.397 + template <typename Graph>
1.398 + bool is_self_loop
1.399 + (typename graph_traits<Graph>::edge_descriptor e,
1.400 + const Graph& g)
1.401 + {
1.402 + return source(e, g) == target(e, g);
1.403 + }
1.404 +
1.405 +
1.406 + template <class T1, class T2>
1.407 + std::pair<T1,T2>
1.408 + make_list(const T1& t1, const T2& t2)
1.409 + { return std::make_pair(t1, t2); }
1.410 +
1.411 + template <class T1, class T2, class T3>
1.412 + std::pair<T1,std::pair<T2,T3> >
1.413 + make_list(const T1& t1, const T2& t2, const T3& t3)
1.414 + { return std::make_pair(t1, std::make_pair(t2, t3)); }
1.415 +
1.416 + template <class T1, class T2, class T3, class T4>
1.417 + std::pair<T1,std::pair<T2,std::pair<T3,T4> > >
1.418 + make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4)
1.419 + { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); }
1.420 +
1.421 + template <class T1, class T2, class T3, class T4, class T5>
1.422 + std::pair<T1,std::pair<T2,std::pair<T3,std::pair<T4,T5> > > >
1.423 + make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
1.424 + { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }
1.425 +
1.426 +} /* namespace boost */
1.427 +
1.428 +#endif /* BOOST_GRAPH_UTILITY_HPP*/