ceph/src/boost/libs/graph/example/gerdemann.cpp

   1 // -*- c++ -*-
   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 #include <boost/config.hpp>
  11 #include <iostream>
  12
  13 #include <boost/graph/adjacency_list.hpp>
  14
  15 /*
  16   Thanks to Dale Gerdemann for this example, which inspired some
  17   changes to adjacency_list to make this work properly.
  18  */
  19
  20 /*
  21   Sample output:
  22
  23   0  --c--> 1   --j--> 1   --c--> 2   --x--> 2
  24   1  --c--> 2   --d--> 3
  25   2  --t--> 4
  26   3  --h--> 4
  27   4
  28
  29   merging vertex 1 into vertex 0
  30
  31   0  --c--> 0   --j--> 0   --c--> 1   --x--> 1   --d--> 2
  32   1  --t--> 3
  33   2  --h--> 3
  34   3
  35  */
  36
  37 // merge_vertex(u,v,g):
  38 // incoming/outgoing edges for v become incoming/outgoing edges for u
  39 // v is deleted
  40 template < class Graph, class GetEdgeProperties >
  41 void merge_vertex(typename boost::graph_traits< Graph >::vertex_descriptor u,
  42     typename boost::graph_traits< Graph >::vertex_descriptor v, Graph& g,
  43     GetEdgeProperties getp)
  44 {
  45     typedef boost::graph_traits< Graph > Traits;
  46     typename Traits::edge_descriptor e;
  47     typename Traits::out_edge_iterator out_i, out_end;
  48     for (boost::tie(out_i, out_end) = out_edges(v, g); out_i != out_end;
  49          ++out_i)
  50     {
  51         e = *out_i;
  52         typename Traits::vertex_descriptor targ = target(e, g);
  53         add_edge(u, targ, getp(e), g);
  54     }
  55     typename Traits::in_edge_iterator in_i, in_end;
  56     for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
  57     {
  58         e = *in_i;
  59         typename Traits::vertex_descriptor src = source(e, g);
  60         add_edge(src, u, getp(e), g);
  61     }
  62     clear_vertex(v, g);
  63     remove_vertex(v, g);
  64 }
  65
  66 template < class StoredEdge > struct order_by_name
  67 {
  68     typedef StoredEdge first_argument_type;
  69     typedef StoredEdge second_argument_type;
  70     typedef bool result_type;
  71     bool operator()(const StoredEdge& e1, const StoredEdge& e2) const
  72     {
  73         // Using std::pair operator< as an easy way to get lexicographical
  74         // compare over tuples.
  75         return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
  76             < std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
  77     }
  78 };
  79 struct ordered_set_by_nameS
  80 {
  81 };
  82
  83 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  84 namespace boost
  85 {
  86 template < class ValueType >
  87 struct container_gen< ordered_set_by_nameS, ValueType >
  88 {
  89     typedef std::set< ValueType, order_by_name< ValueType > > type;
  90 };
  91 template <> struct parallel_edge_traits< ordered_set_by_nameS >
  92 {
  93     typedef allow_parallel_edge_tag type;
  94 };
  95 }
  96 #endif
  97
  98 template < class Graph > struct get_edge_name
  99 {
 100     get_edge_name(const Graph& g_) : g(g_) {}
 101
 102     template < class Edge >
 103     boost::property< boost::edge_name_t, char > operator()(Edge e) const
 104     {
 105         return boost::property< boost::edge_name_t, char >(
 106             boost::get(boost::edge_name, g, e));
 107     }
 108     const Graph& g;
 109 };
 110
 111 int main()
 112 {
 113 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 114     std::cout << "This program requires partial specialization." << std::endl;
 115 #else
 116     using namespace boost;
 117     typedef property< edge_name_t, char > EdgeProperty;
 118     typedef adjacency_list< ordered_set_by_nameS, vecS, bidirectionalS,
 119         no_property, EdgeProperty >
 120         graph_type;
 121
 122     graph_type g;
 123
 124     add_edge(0, 1, EdgeProperty('j'), g);
 125     add_edge(0, 2, EdgeProperty('c'), g);
 126     add_edge(0, 2, EdgeProperty('x'), g);
 127     add_edge(1, 3, EdgeProperty('d'), g);
 128     add_edge(1, 2, EdgeProperty('c'), g);
 129     add_edge(1, 3, EdgeProperty('d'), g);
 130     add_edge(2, 4, EdgeProperty('t'), g);
 131     add_edge(3, 4, EdgeProperty('h'), g);
 132     add_edge(0, 1, EdgeProperty('c'), g);
 133
 134     property_map< graph_type, vertex_index_t >::type id = get(vertex_index, g);
 135     property_map< graph_type, edge_name_t >::type name = get(edge_name, g);
 136
 137     graph_traits< graph_type >::vertex_iterator i, end;
 138     graph_traits< graph_type >::out_edge_iterator ei, edge_end;
 139
 140     for (boost::tie(i, end) = vertices(g); i != end; ++i)
 141     {
 142         std::cout << id[*i] << " ";
 143         for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
 144             std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)]
 145                       << "  ";
 146         std::cout << std::endl;
 147     }
 148     std::cout << std::endl;
 149
 150     std::cout << "merging vertex 1 into vertex 0" << std::endl << std::endl;
 151     merge_vertex(0, 1, g, get_edge_name< graph_type >(g));
 152
 153     for (boost::tie(i, end) = vertices(g); i != end; ++i)
 154     {
 155         std::cout << id[*i] << " ";
 156         for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
 157             std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)]
 158                       << "  ";
 159         std::cout << std::endl;
 160     }
 161     std::cout << std::endl;
 162 #endif
 163     return 0;
 164 }