Boost C++ Libraries

boost/graph/graph_utility.hpp

//
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//
#ifndef BOOST_GRAPH_UTILITY_HPP
#define BOOST_GRAPH_UTILITY_HPP

#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <boost/config.hpp>
#include <boost/tuple/tuple.hpp>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/pending/container_traits.hpp>
#include <boost/graph/depth_first_search.hpp>
// iota moved to detail/algorithm.hpp
#include <boost/detail/algorithm.hpp>

namespace boost {

  // Provide an undirected graph interface alternative to the
  // the source() and target() edge functions.
  template <class UndirectedGraph>
  inline 
  std::pair<typename graph_traits<UndirectedGraph>::vertex_descriptor,
            typename graph_traits<UndirectedGraph>::vertex_descriptor>
  incident(typename graph_traits<UndirectedGraph>::edge_descriptor e,
           UndirectedGraph& g)
  {
    return std::make_pair(source(e,g), target(e,g));
  }

  // Provide an undirected graph interface alternative
  // to the out_edges() function.
  template <class Graph>
  inline 
  std::pair<typename graph_traits<Graph>::out_edge_iterator,
            typename graph_traits<Graph>::out_edge_iterator>
  incident_edges(typename graph_traits<Graph>::vertex_descriptor u,
                 Graph& g)
  {
    return out_edges(u, g);
  }

  template <class Graph>
  inline typename graph_traits<Graph>::vertex_descriptor
  opposite(typename graph_traits<Graph>::edge_descriptor e,
           typename graph_traits<Graph>::vertex_descriptor v,
           const Graph& g)
  {
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
    if (v == source(e, g))
      return target(e, g);
    else if (v == target(e, g))
      return source(e, g);
    else
      return vertex_descriptor();
  }

  //===========================================================================
  // Some handy predicates

  template <typename Vertex, typename Graph>
  struct incident_from_predicate {
    incident_from_predicate(Vertex u, const Graph& g)
      : m_u(u), m_g(g) { }
    template <class Edge>
    bool operator()(const Edge& e) const {
      return source(e, m_g) == m_u;
    }
    Vertex m_u;
    const Graph& m_g;
  };
  template <typename Vertex, typename Graph>
  inline incident_from_predicate<Vertex, Graph>
  incident_from(Vertex u, const Graph& g) {
    return incident_from_predicate<Vertex, Graph>(u, g);
  }
  
  template <typename Vertex, typename Graph>
  struct incident_to_predicate {
    incident_to_predicate(Vertex u, const Graph& g)
      : m_u(u), m_g(g) { }
    template <class Edge>
    bool operator()(const Edge& e) const {
      return target(e, m_g) == m_u;
    }
    Vertex m_u;
    const Graph& m_g;
  };
  template <typename Vertex, typename Graph>
  inline incident_to_predicate<Vertex, Graph>
  incident_to(Vertex u, const Graph& g) {
    return incident_to_predicate<Vertex, Graph>(u, g);
  }

  template <typename Vertex, typename Graph>
  struct incident_on_predicate {
    incident_on_predicate(Vertex u, const Graph& g)
      : m_u(u), m_g(g) { }
    template <class Edge>
    bool operator()(const Edge& e) const {
      return source(e, m_g) == m_u || target(e, m_g) == m_u;
    }
    Vertex m_u;
    const Graph& m_g;
  };
  template <typename Vertex, typename Graph>
  inline incident_on_predicate<Vertex, Graph>
  incident_on(Vertex u, const Graph& g) {
    return incident_on_predicate<Vertex, Graph>(u, g);
  }
  
  template <typename Vertex, typename Graph>
  struct connects_predicate {
    connects_predicate(Vertex u, Vertex v, const Graph& g)
      : m_u(u), m_v(v), m_g(g) { }
    template <class Edge>
    bool operator()(const Edge& e) const {
      if (is_directed(m_g))
        return source(e, m_g) == m_u && target(e, m_g) == m_v;
      else
        return (source(e, m_g) == m_u && target(e, m_g) == m_v)
          || (source(e, m_g) == m_v && target(e, m_g) == m_u);
    }
    Vertex m_u, m_v;
    const Graph& m_g;
  };
  template <typename Vertex, typename Graph>
  inline connects_predicate<Vertex, Graph>
  connects(Vertex u, Vertex v, const Graph& g) {
          return connects_predicate<Vertex, Graph>(u, v, g);
  }


  // Need to convert all of these printing functions to take an ostream object
  // -JGS

  template <class IncidenceGraph, class Name>
  void print_in_edges(const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
  {
    typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
    for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
      os << get(name,*ui) << " <-- ";
      typename graph_traits<IncidenceGraph>
        ::in_edge_iterator ei, ei_end;
      for(boost::tie(ei,ei_end) = in_edges(*ui,G); ei != ei_end; ++ei)
        os << get(name,source(*ei,G)) << " ";
      os << '\n';
    }
  }

  template <class IncidenceGraph, class Name>
  void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag, std::ostream& os = std::cout)
  {
    typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
    for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
      os << get(name,*ui) << " --> ";
      typename graph_traits<IncidenceGraph>
        ::out_edge_iterator ei, ei_end;
      for(boost::tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
        os << get(name,target(*ei,G)) << " ";
      os << '\n';
    }
  }
  template <class IncidenceGraph, class Name>
  void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag, std::ostream& os = std::cout)
  {
    typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
    for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
      os << get(name,*ui) << " <--> ";
      typename graph_traits<IncidenceGraph>
        ::out_edge_iterator ei, ei_end;
      for(boost::tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
        os << get(name,target(*ei,G)) << " ";
      os << '\n';
    }
  }
  template <class IncidenceGraph, class Name>
  void print_graph(const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
  {
    typedef typename graph_traits<IncidenceGraph>
      ::directed_category Cat;
    print_graph_dispatch(G, name, Cat(), os);
  }
  template <class IncidenceGraph>
  void print_graph(const IncidenceGraph& G, std::ostream& os = std::cout) {
    print_graph(G, get(vertex_index, G), os);
  }

  template <class EdgeListGraph, class Name>
  void print_edges(const EdgeListGraph& G, Name name, std::ostream& os = std::cout)
  {
    typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
      os << "(" << get(name, source(*ei, G))
                << "," << get(name, target(*ei, G)) << ") ";
    os << '\n';
  }

  template <class EdgeListGraph, class VertexName, class EdgeName>
  void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename, std::ostream& os = std::cout)
  {
    typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
      os << get(ename, *ei) << "(" << get(vname, source(*ei, G))
                << "," << get(vname, target(*ei, G)) << ") ";
    os << '\n';
  }

  template <class VertexListGraph, class Name>
  void print_vertices(const VertexListGraph& G, Name name, std::ostream& os = std::cout)
  {
    typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end;
    for (boost::tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi)
      os << get(name,*vi) << " ";
    os << '\n';
  }

  template <class Graph, class Vertex>
  bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
  {
    typename graph_traits<Graph>::adjacency_iterator vi, viend, 
      adj_found;
    boost::tie(vi, viend) = adjacent_vertices(a, g);
    adj_found = std::find(vi, viend, b);
    if (adj_found == viend)
      return false;  

    typename graph_traits<Graph>::out_edge_iterator oi, oiend, 
      out_found;
    boost::tie(oi, oiend) = out_edges(a, g);
    out_found = std::find_if(oi, oiend, incident_to(b, g));
    if (out_found == oiend)
      return false;

    typename graph_traits<Graph>::in_edge_iterator ii, iiend, 
      in_found;
    boost::tie(ii, iiend) = in_edges(b, g);
    in_found = std::find_if(ii, iiend, incident_from(a, g));
    if (in_found == iiend)
      return false;

    return true;
  }
  template <class Graph, class Vertex>
  bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
  {
    typename graph_traits<Graph>::adjacency_iterator vi, viend, found;
    boost::tie(vi, viend) = adjacent_vertices(a, g);
    found = std::find(vi, viend, b);
    if ( found == viend )
      return false;

    typename graph_traits<Graph>::out_edge_iterator oi, oiend, 
      out_found;
    boost::tie(oi, oiend) = out_edges(a, g);

    out_found = std::find_if(oi, oiend, incident_to(b, g));
    if (out_found == oiend)
      return false;
    return true;
  }
  template <class Graph, class Vertex>
  bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
  {
    return is_adj_dispatch(g, a, b, directed_tag());
  }

  template <class Graph, class Vertex>
  bool is_adjacent(Graph& g, Vertex a, Vertex b) {
    typedef typename graph_traits<Graph>::directed_category Cat;
    return is_adj_dispatch(g, a, b, Cat());
  }

  template <class Graph, class Edge>
  bool in_edge_set(Graph& g, Edge e)
  {
    typename Graph::edge_iterator ei, ei_end, found;
    boost::tie(ei, ei_end) = edges(g);
    found = std::find(ei, ei_end, e);
    return found != ei_end;
  }

  template <class Graph, class Vertex>
  bool in_vertex_set(Graph& g, Vertex v)
  {
    typename Graph::vertex_iterator vi, vi_end, found;
    boost::tie(vi, vi_end) = vertices(g);
    found = std::find(vi, vi_end, v);
    return found != vi_end;
  }

  template <class Graph, class Vertex>
  bool in_edge_set(Graph& g, Vertex u, Vertex v)
  {
    typename Graph::edge_iterator ei, ei_end;
    for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
      if (source(*ei,g) == u && target(*ei,g) == v)
        return true;
    return false;
  }

  // is x a descendant of y?
  template <typename ParentMap>
  inline bool is_descendant
  (typename property_traits<ParentMap>::value_type x,
   typename property_traits<ParentMap>::value_type y,
   ParentMap parent) 
  {
    if (get(parent, x) == x) // x is the root of the tree
      return false;
    else if (get(parent, x) == y)
      return true;
    else
      return is_descendant(get(parent, x), y, parent);
  }

  // is y reachable from x?
  template <typename IncidenceGraph, typename VertexColorMap>
  inline bool is_reachable
    (typename graph_traits<IncidenceGraph>::vertex_descriptor x,
     typename graph_traits<IncidenceGraph>::vertex_descriptor y,
     const IncidenceGraph& g,
     VertexColorMap color) // should start out white for every vertex
  {
    typedef typename property_traits<VertexColorMap>::value_type ColorValue;
    dfs_visitor<> vis;
    depth_first_visit(g, x, vis, color);
    return get(color, y) != color_traits<ColorValue>::white();
  }

  // Is the undirected graph connected?
  // Is the directed graph strongly connected?
  template <typename VertexListGraph, typename VertexColorMap>
  inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
  {
    typedef typename property_traits<VertexColorMap>::value_type ColorValue;
    typedef color_traits<ColorValue> Color;
    typename graph_traits<VertexListGraph>::vertex_iterator 
      ui, ui_end, vi, vi_end, ci, ci_end;
    for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
      for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
        if (*ui != *vi) {
          for (boost::tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci) 
            put(color, *ci, Color::white());
          if (! is_reachable(*ui, *vi, g, color))
            return false;
        }
    return true;
  }

  template <typename Graph>
  bool is_self_loop
    (typename graph_traits<Graph>::edge_descriptor e,
     const Graph& g)
  {
    return source(e, g) == target(e, g);
  }


  template <class T1, class T2>
  std::pair<T1,T2> 
  make_list(const T1& t1, const T2& t2) 
    { return std::make_pair(t1, t2); }

  template <class T1, class T2, class T3>
  std::pair<T1,std::pair<T2,T3> > 
  make_list(const T1& t1, const T2& t2, const T3& t3)
    { return std::make_pair(t1, std::make_pair(t2, t3)); }

  template <class T1, class T2, class T3, class T4>
  std::pair<T1,std::pair<T2,std::pair<T3,T4> > > 
  make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4)
    { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); }

  template <class T1, class T2, class T3, class T4, class T5>
  std::pair<T1,std::pair<T2,std::pair<T3,std::pair<T4,T5> > > > 
  make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
    { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }

  namespace graph {
    
    // Functor for remove_parallel_edges: edge property of the removed edge is added to the remaining
    template <typename EdgeProperty>
    struct add_removed_edge_property
    {
      add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
      
      template <typename Edge>
      void operator() (Edge stay, Edge away)
      {
        put(ep, stay, get(ep, stay) + get(ep, away));
      }
      EdgeProperty  ep;
    };

    // Same as above: edge property is capacity here
    template <typename Graph>
    struct add_removed_edge_capacity
      : add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type>
    {
      typedef add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type> base;
      add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
    };    

    template <typename Graph>
    bool has_no_vertices(const Graph& g) {
      typedef typename boost::graph_traits<Graph>::vertex_iterator vi;
      std::pair<vi, vi> p = vertices(g);
      return (p.first == p.second);
    }

    template <typename Graph>
    bool has_no_edges(const Graph& g) {
      typedef typename boost::graph_traits<Graph>::edge_iterator ei;
      std::pair<ei, ei> p = edges(g);
      return (p.first == p.second);
    }

    template <typename Graph>
    bool has_no_out_edges(const typename boost::graph_traits<Graph>::vertex_descriptor& v, const Graph& g) {
      typedef typename boost::graph_traits<Graph>::out_edge_iterator ei;
      std::pair<ei, ei> p = out_edges(v, g);
      return (p.first == p.second);
    }

  } // namespace graph

  #include <boost/graph/iteration_macros.hpp>

  template <class PropertyIn, class PropertyOut, class Graph>
  void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
  {
    BGL_FORALL_VERTICES_T(u, g, Graph)
      put(p_out, u, get(p_in, g));
  }

  template <class PropertyIn, class PropertyOut, class Graph>
  void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
  {
    BGL_FORALL_EDGES_T(e, g, Graph)
      put(p_out, e, get(p_in, g));
  }

  // Return true if property_map1 and property_map2 differ
  // for any of the vertices in graph.
  template <typename PropertyMapFirst,
            typename PropertyMapSecond,
            typename Graph>
  bool are_property_maps_different
  (const PropertyMapFirst property_map1,
   const PropertyMapSecond property_map2,
   const Graph& graph) {
  
    BGL_FORALL_VERTICES_T(vertex, graph, Graph) {
      if (get(property_map1, vertex) !=
          get(property_map2, vertex)) {

        return (true);
      }
    }

    return (false);
  }

} /* namespace boost */

#endif /* BOOST_GRAPH_UTILITY_HPP*/