text: // -*- c++ -*-
  //=======================================================================
  // 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)
  //=======================================================================
  #include <boost/config.hpp>
  #include <iostream>
  
  #include <boost/graph/adjacency_list.hpp>
  
  /*
    Thanks to Dale Gerdemann for this example, which inspired some
    changes to adjacency_list to make this work properly.
   */
  
  /*
    Sample output:
  
    0  --c--> 1   --j--> 1   --c--> 2   --x--> 2  
    1  --c--> 2   --d--> 3  
    2  --t--> 4  
    3  --h--> 4  
    4 
  
    merging vertex 1 into vertex 0
  
    0  --c--> 0   --j--> 0   --c--> 1   --x--> 1   --d--> 2  
    1  --t--> 3  
    2  --h--> 3  
    3 
   */
  
  // merge_vertex(u,v,g):
  // incoming/outgoing edges for v become incoming/outgoing edges for u
  // v is deleted
  template <class Graph, class GetEdgeProperties>
  void merge_vertex
    (typename boost::graph_traits<Graph>::vertex_descriptor u,
     typename boost::graph_traits<Graph>::vertex_descriptor v,
     Graph& g, GetEdgeProperties getp)
  {
    typedef boost::graph_traits<Graph> Traits;
    typename Traits::edge_descriptor e;
    typename Traits::out_edge_iterator out_i, out_end;
    for (tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) {
      e = *out_i;
      typename Traits::vertex_descriptor targ = target(e, g);
      add_edge(u, targ, getp(e), g);
    }
    typename Traits::in_edge_iterator in_i, in_end;
    for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i) {
      e = *in_i;
      typename Traits::vertex_descriptor src = source(e, g);
      add_edge(src, u, getp(e), g);
    }
    clear_vertex(v, g);
    remove_vertex(v, g);
  }
  
  template <class StoredEdge>
  struct order_by_name
    : public std::binary_function<StoredEdge,StoredEdge,bool> 
  {
    bool operator()(const StoredEdge& e1, const StoredEdge& e2) const {
      // Using std::pair operator< as an easy way to get lexicographical
      // compare over tuples.
      return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
        < std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
    }
  };
  struct ordered_set_by_nameS { };
  
  #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  namespace boost {
    template <class ValueType>
    struct container_gen<ordered_set_by_nameS, ValueType> {
      typedef std::set<ValueType, order_by_name<ValueType> > type;
    };
    template <>
    struct parallel_edge_traits<ordered_set_by_nameS> { 
      typedef allow_parallel_edge_tag type;
    };
  }
  #endif
  
  template <class Graph>
  struct get_edge_name {
    get_edge_name(const Graph& g_) : g(g_) { }
  
    template <class Edge>
    boost::property<boost::edge_name_t, char> operator()(Edge e) const {
      return boost::property<boost::edge_name_t, char>(boost::get(boost::edge_name, g, e));
    }
    const Graph& g;
  };
  
  int
  main()
  {
  #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
    std::cout << "This program requires partial specialization." << std::endl;
  #else
    using namespace boost;
    typedef property<edge_name_t, char> EdgeProperty;
    typedef adjacency_list<ordered_set_by_nameS, vecS, bidirectionalS,
      no_property, EdgeProperty> graph_type;
  
    graph_type g;
  
    add_edge(0, 1, EdgeProperty('j'), g);
    add_edge(0, 2, EdgeProperty('c'), g);
    add_edge(0, 2, EdgeProperty('x'), g);
    add_edge(1, 3, EdgeProperty('d'), g);
    add_edge(1, 2, EdgeProperty('c'), g);
    add_edge(1, 3, EdgeProperty('d'), g);
    add_edge(2, 4, EdgeProperty('t'), g);
    add_edge(3, 4, EdgeProperty('h'), g);
    add_edge(0, 1, EdgeProperty('c'), g);
    
    property_map<graph_type, vertex_index_t>::type id = get(vertex_index, g);
    property_map<graph_type, edge_name_t>::type name = get(edge_name, g);
  
    graph_traits<graph_type>::vertex_iterator i, end;
    graph_traits<graph_type>::out_edge_iterator ei, edge_end;
  
    for (boost::tie(i, end) = vertices(g); i != end; ++i) {
      std::cout << id[*i] << " ";
      for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
        std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)] << "  ";
      std::cout << std::endl;
    }
    std::cout << std::endl;
  
    std::cout << "merging vertex 1 into vertex 0" << std::endl << std::endl;
    merge_vertex(0, 1, g, get_edge_name<graph_type>(g));
    
    for (boost::tie(i, end) = vertices(g); i != end; ++i) {
      std::cout << id[*i] << " ";
      for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
        std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)] << "  ";
      std::cout << std::endl;
    }
    std::cout << std::endl;
  #endif  
    return 0;
  }
  