boost/graph/graph_utility.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11 #ifndef BOOST_GRAPH_UTILITY_HPP
  12 #define BOOST_GRAPH_UTILITY_HPP
  13
  14 #include <stdlib.h>
  15 #include <iostream>
  16 #include <algorithm>
  17 #include <assert.h>
  18 #include <boost/config.hpp>
  19 #include <boost/tuple/tuple.hpp>
  20
  21 #if !defined BOOST_NO_SLIST
  22 #  ifdef BOOST_SLIST_HEADER
  23 #    include BOOST_SLIST_HEADER
  24 #  else
  25 #    include <slist>
  26 #  endif
  27 #endif
  28
  29 #include <boost/graph/graph_traits.hpp>
  30 #include <boost/graph/properties.hpp>
  31 #include <boost/pending/container_traits.hpp>
  32 #include <boost/graph/depth_first_search.hpp>
  33 // iota moved to detail/algorithm.hpp
  34 #include <boost/detail/algorithm.hpp>
  35
  36 namespace boost {
  37
  38   // Provide an undirected graph interface alternative to the
  39   // the source() and target() edge functions.
  40   template <class UndirectedGraph>
  41   inline
  42   std::pair<typename graph_traits<UndirectedGraph>::vertex_descriptor,
  43             typename graph_traits<UndirectedGraph>::vertex_descriptor>
  44   incident(typename graph_traits<UndirectedGraph>::edge_descriptor e,
  45            UndirectedGraph& g)
  46   {
  47     return std::make_pair(source(e,g), target(e,g));
  48   }
  49
  50   // Provide an undirected graph interface alternative
  51   // to the out_edges() function.
  52   template <class Graph>
  53   inline
  54   std::pair<typename graph_traits<Graph>::out_edge_iterator,
  55             typename graph_traits<Graph>::out_edge_iterator>
  56   incident_edges(typename graph_traits<Graph>::vertex_descriptor u,
  57                  Graph& g)
  58   {
  59     return out_edges(u, g);
  60   }
  61
  62   template <class Graph>
  63   inline typename graph_traits<Graph>::vertex_descriptor
  64   opposite(typename graph_traits<Graph>::edge_descriptor e,
  65            typename graph_traits<Graph>::vertex_descriptor v,
  66            const Graph& g)
  67   {
  68     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  69     if (v == source(e, g))
  70       return target(e, g);
  71     else if (v == target(e, g))
  72       return source(e, g);
  73     else
  74       return vertex_descriptor();
  75   }
  76
  77   //===========================================================================
  78   // Some handy predicates
  79
  80   template <typename Vertex, typename Graph>
  81   struct incident_from_predicate {
  82     incident_from_predicate(Vertex u, const Graph& g)
  83       : m_u(u), m_g(g) { }
  84     template <class Edge>
  85     bool operator()(const Edge& e) const {
  86       return source(e, m_g) == m_u;
  87     }
  88     Vertex m_u;
  89     const Graph& m_g;
  90   };
  91   template <typename Vertex, typename Graph>
  92   inline incident_from_predicate<Vertex, Graph>
  93   incident_from(Vertex u, const Graph& g) {
  94     return incident_from_predicate<Vertex, Graph>(u, g);
  95   }
  96
  97   template <typename Vertex, typename Graph>
  98   struct incident_to_predicate {
  99     incident_to_predicate(Vertex u, const Graph& g)
 100       : m_u(u), m_g(g) { }
 101     template <class Edge>
 102     bool operator()(const Edge& e) const {
 103       return target(e, m_g) == m_u;
 104     }
 105     Vertex m_u;
 106     const Graph& m_g;
 107   };
 108   template <typename Vertex, typename Graph>
 109   inline incident_to_predicate<Vertex, Graph>
 110   incident_to(Vertex u, const Graph& g) {
 111     return incident_to_predicate<Vertex, Graph>(u, g);
 112   }
 113
 114   template <typename Vertex, typename Graph>
 115   struct incident_on_predicate {
 116     incident_on_predicate(Vertex u, const Graph& g)
 117       : m_u(u), m_g(g) { }
 118     template <class Edge>
 119     bool operator()(const Edge& e) const {
 120       return source(e, m_g) == m_u || target(e, m_g) == m_u;
 121     }
 122     Vertex m_u;
 123     const Graph& m_g;
 124   };
 125   template <typename Vertex, typename Graph>
 126   inline incident_on_predicate<Vertex, Graph>
 127   incident_on(Vertex u, const Graph& g) {
 128     return incident_on_predicate<Vertex, Graph>(u, g);
 129   }
 130
 131   template <typename Vertex, typename Graph>
 132   struct connects_predicate {
 133     connects_predicate(Vertex u, Vertex v, const Graph& g)
 134       : m_u(u), m_v(v), m_g(g) { }
 135     template <class Edge>
 136     bool operator()(const Edge& e) const {
 137       if (is_directed(m_g))
 138         return source(e, m_g) == m_u && target(e, m_g) == m_v;
 139       else
 140         return (source(e, m_g) == m_u && target(e, m_g) == m_v)
 141           || (source(e, m_g) == m_v && target(e, m_g) == m_u);
 142     }
 143     Vertex m_u, m_v;
 144     const Graph& m_g;
 145   };
 146   template <typename Vertex, typename Graph>
 147   inline connects_predicate<Vertex, Graph>
 148   connects(Vertex u, Vertex v, const Graph& g) {
 149           return connects_predicate<Vertex, Graph>(u, v, g);
 150   }
 151
 152
 153   // Need to convert all of these printing functions to take an ostream object
 154   // -JGS
 155
 156   template <class IncidenceGraph, class Name>
 157   void print_in_edges(const IncidenceGraph& G, Name name)
 158   {
 159     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
 160     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
 161       std::cout << get(name,*ui) << " <-- ";
 162       typename graph_traits<IncidenceGraph>
 163         ::in_edge_iterator ei, ei_end;
 164       for(tie(ei,ei_end) = in_edges(*ui,G); ei != ei_end; ++ei)
 165         std::cout << get(name,source(*ei,G)) << " ";
 166       std::cout << std::endl;
 167     }
 168   }
 169
 170   template <class IncidenceGraph, class Name>
 171   void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag)
 172   {
 173     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
 174     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
 175       std::cout << get(name,*ui) << " --> ";
 176       typename graph_traits<IncidenceGraph>
 177         ::out_edge_iterator ei, ei_end;
 178       for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
 179         std::cout << get(name,target(*ei,G)) << " ";
 180       std::cout << std::endl;
 181     }
 182   }
 183   template <class IncidenceGraph, class Name>
 184   void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag)
 185   {
 186     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
 187     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
 188       std::cout << get(name,*ui) << " <--> ";
 189       typename graph_traits<IncidenceGraph>
 190         ::out_edge_iterator ei, ei_end;
 191       for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
 192         std::cout << get(name,target(*ei,G)) << " ";
 193       std::cout << std::endl;
 194     }
 195   }
 196   template <class IncidenceGraph, class Name>
 197   void print_graph(const IncidenceGraph& G, Name name)
 198   {
 199     typedef typename graph_traits<IncidenceGraph>
 200       ::directed_category Cat;
 201     print_graph_dispatch(G, name, Cat());
 202   }
 203   template <class IncidenceGraph>
 204   void print_graph(const IncidenceGraph& G) {
 205     print_graph(G, get(vertex_index, G));
 206   }
 207
 208   template <class EdgeListGraph, class Name>
 209   void print_edges(const EdgeListGraph& G, Name name)
 210   {
 211     typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
 212     for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
 213       std::cout << "(" << get(name, source(*ei, G))
 214                 << "," << get(name, target(*ei, G)) << ") ";
 215     std::cout << std::endl;
 216   }
 217
 218   template <class EdgeListGraph, class VertexName, class EdgeName>
 219   void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename)
 220   {
 221     typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
 222     for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
 223       std::cout << get(ename, *ei) << "(" << get(vname, source(*ei, G))
 224                 << "," << get(vname, target(*ei, G)) << ") ";
 225     std::cout << std::endl;
 226   }
 227
 228   template <class VertexListGraph, class Name>
 229   void print_vertices(const VertexListGraph& G, Name name)
 230   {
 231     typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end;
 232     for (tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi)
 233       std::cout << get(name,*vi) << " ";
 234     std::cout << std::endl;
 235   }
 236
 237   template <class Graph, class Vertex>
 238   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
 239   {
 240     typedef typename graph_traits<Graph>::edge_descriptor
 241       edge_descriptor;
 242     typename graph_traits<Graph>::adjacency_iterator vi, viend,
 243       adj_found;
 244     tie(vi, viend) = adjacent_vertices(a, g);
 245     adj_found = std::find(vi, viend, b);
 246     if (adj_found == viend)
 247       return false;
 248
 249     typename graph_traits<Graph>::out_edge_iterator oi, oiend,
 250       out_found;
 251     tie(oi, oiend) = out_edges(a, g);
 252     out_found = std::find_if(oi, oiend, incident_to(b, g));
 253     if (out_found == oiend)
 254       return false;
 255
 256     typename graph_traits<Graph>::in_edge_iterator ii, iiend,
 257       in_found;
 258     tie(ii, iiend) = in_edges(b, g);
 259     in_found = std::find_if(ii, iiend, incident_from(a, g));
 260     if (in_found == iiend)
 261       return false;
 262
 263     return true;
 264   }
 265   template <class Graph, class Vertex>
 266   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
 267   {
 268     typedef typename graph_traits<Graph>::edge_descriptor
 269       edge_descriptor;
 270     typename graph_traits<Graph>::adjacency_iterator vi, viend, found;
 271     tie(vi, viend) = adjacent_vertices(a, g);
 272 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
 273     // Getting internal compiler error with std::find()
 274     found = viend;
 275     for (; vi != viend; ++vi)
 276       if (*vi == b) {
 277         found = vi;
 278         break;
 279       }
 280 #else
 281     found = std::find(vi, viend, b);
 282 #endif
 283     if ( found == viend )
 284       return false;
 285
 286     typename graph_traits<Graph>::out_edge_iterator oi, oiend,
 287       out_found;
 288     tie(oi, oiend) = out_edges(a, g);
 289
 290 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
 291     // Getting internal compiler error with std::find()
 292     out_found = oiend;
 293     for (; oi != oiend; ++oi)
 294       if (target(*oi, g) == b) {
 295         out_found = oi;
 296         break;
 297       }
 298 #else
 299     out_found = std::find_if(oi, oiend, incident_to(b, g));
 300 #endif
 301     if (out_found == oiend)
 302       return false;
 303     return true;
 304   }
 305   template <class Graph, class Vertex>
 306   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
 307   {
 308     return is_adj_dispatch(g, a, b, directed_tag());
 309   }
 310
 311   template <class Graph, class Vertex>
 312   bool is_adjacent(Graph& g, Vertex a, Vertex b) {
 313     typedef typename graph_traits<Graph>::directed_category Cat;
 314     return is_adj_dispatch(g, a, b, Cat());
 315   }
 316
 317   template <class Graph, class Edge>
 318   bool in_edge_set(Graph& g, Edge e)
 319   {
 320     typename Graph::edge_iterator ei, ei_end, found;
 321     tie(ei, ei_end) = edges(g);
 322     found = std::find(ei, ei_end, e);
 323     return found != ei_end;
 324   }
 325
 326   template <class Graph, class Vertex>
 327   bool in_vertex_set(Graph& g, Vertex v)
 328   {
 329     typename Graph::vertex_iterator vi, vi_end, found;
 330     tie(vi, vi_end) = vertices(g);
 331     found = std::find(vi, vi_end, v);
 332     return found != vi_end;
 333   }
 334
 335   template <class Graph, class Vertex>
 336   bool in_edge_set(Graph& g, Vertex u, Vertex v)
 337   {
 338     typename Graph::edge_iterator ei, ei_end;
 339     for (tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
 340       if (source(*ei,g) == u && target(*ei,g) == v)
 341         return true;
 342     return false;
 343   }
 344
 345   // is x a descendant of y?
 346   template <typename ParentMap>
 347   inline bool is_descendant
 348   (typename property_traits<ParentMap>::value_type x,
 349    typename property_traits<ParentMap>::value_type y,
 350    ParentMap parent)
 351   {
 352     if (get(parent, x) == x) // x is the root of the tree
 353       return false;
 354     else if (get(parent, x) == y)
 355       return true;
 356     else
 357       return is_descendant(get(parent, x), y, parent);
 358   }
 359
 360   // is y reachable from x?
 361   template <typename IncidenceGraph, typename VertexColorMap>
 362   inline bool is_reachable
 363     (typename graph_traits<IncidenceGraph>::vertex_descriptor x,
 364      typename graph_traits<IncidenceGraph>::vertex_descriptor y,
 365      const IncidenceGraph& g,
 366      VertexColorMap color) // should start out white for every vertex
 367   {
 368     typedef typename property_traits<VertexColorMap>::value_type ColorValue;
 369     dfs_visitor<> vis;
 370     depth_first_visit(g, x, vis, color);
 371     return get(color, y) != color_traits<ColorValue>::white();
 372   }
 373
 374   // Is the undirected graph connected?
 375   // Is the directed graph strongly connected?
 376   template <typename VertexListGraph, typename VertexColorMap>
 377   inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
 378   {
 379     typedef typename property_traits<VertexColorMap>::value_type ColorValue;
 380     typedef color_traits<ColorValue> Color;
 381     typename graph_traits<VertexListGraph>::vertex_iterator
 382       ui, ui_end, vi, vi_end, ci, ci_end;
 383     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
 384       for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 385         if (*ui != *vi) {
 386           for (tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci)
 387             put(color, *ci, Color::white());
 388           if (! is_reachable(*ui, *vi, g, color))
 389             return false;
 390         }
 391     return true;
 392   }
 393
 394   template <typename Graph>
 395   bool is_self_loop
 396     (typename graph_traits<Graph>::edge_descriptor e,
 397      const Graph& g)
 398   {
 399     return source(e, g) == target(e, g);
 400   }
 401
 402
 403   template <class T1, class T2>
 404   std::pair<T1,T2>
 405   make_list(const T1& t1, const T2& t2)
 406     { return std::make_pair(t1, t2); }
 407
 408   template <class T1, class T2, class T3>
 409   std::pair<T1,std::pair<T2,T3> >
 410   make_list(const T1& t1, const T2& t2, const T3& t3)
 411     { return std::make_pair(t1, std::make_pair(t2, t3)); }
 412
 413   template <class T1, class T2, class T3, class T4>
 414   std::pair<T1,std::pair<T2,std::pair<T3,T4> > >
 415   make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4)
 416     { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); }
 417
 418   template <class T1, class T2, class T3, class T4, class T5>
 419   std::pair<T1,std::pair<T2,std::pair<T3,std::pair<T4,T5> > > >
 420   make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
 421     { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }
 422
 423   namespace graph {
 424
 425     // Functor for remove_parallel_edges: edge property of the removed edge is added to the remaining
 426     template <typename EdgeProperty>
 427     struct add_removed_edge_property
 428     {
 429       add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
 430
 431       template <typename Edge>
 432       void operator() (Edge stay, Edge away)
 433       {
 434         put(ep, stay, get(ep, stay) + get(ep, away));
 435       }
 436       EdgeProperty  ep;
 437     };
 438
 439     // Same as above: edge property is capacity here
 440     template <typename Graph>
 441     struct add_removed_edge_capacity
 442       : add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type>
 443     {
 444       typedef add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type> base;
 445       add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
 446     };
 447
 448   } // namespace graph
 449
 450 } /* namespace boost */
 451
 452 #endif /* BOOST_GRAPH_UTILITY_HPP*/