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

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 //
  10 //  Sample output:
  11 //
  12 //   0  --(8, 10)--> 1
  13 //
  14 //   1  --(12, 20)--> 4 --(12, 40)--> 3
  15 //        <--(8,10)-- 0 <--(16,20)-- 2
  16 //   2  --(16, 20)--> 1
  17 //        <--(16,20)-- 5
  18 //   3  --(12, 40)--> 6
  19 //        <--(12,40)-- 1
  20 //   4  --(12, 20)--> 7
  21 //        <--(12,20)-- 1
  22 //   5  --(16, 20)--> 2
  23 //        <--(16,20)-- 6
  24 //   6  --(16, 20)--> 5 --(8, 10)--> 8
  25 //        <--(12,20)-- 7        <--(12,40)-- 3
  26 //   7  --(12, 20)--> 6
  27 //        <--(12,20)-- 4
  28 //   8
  29 //        <--(8,10)-- 6
  30 //
  31 //
  32 //   0  --(8, 1)--> 1
  33 //
  34 //   1  --(12, 2)--> 4  --(12, 3)--> 3
  35 //        <--(8,1)-- 0  <--(16,4)-- 2
  36 //   2  --(16, 4)--> 1
  37 //        <--(16,7)-- 5
  38 //   3  --(12, 5)--> 6
  39 //        <--(12,3)-- 1
  40 //   4  --(12, 6)--> 7
  41 //        <--(12,2)-- 1
  42 //   5  --(16, 7)--> 2
  43 //        <--(16,8)-- 6
  44 //   6  --(16, 8)--> 5
  45 //        <--(12,10)-- 7        <--(12,5)-- 3
  46 //   7  --(12, 10)--> 6
  47 //        <--(12,6)-- 4
  48 //   8
  49 //
  50
  51 #include <boost/config.hpp>
  52 #include <iostream>
  53
  54 #include <boost/utility.hpp>
  55 #include <boost/property_map/property_map.hpp>
  56 #include <boost/graph/adjacency_list.hpp>
  57
  58
  59 using namespace boost;
  60 using namespace std;
  61
  62
  63 enum edge_myflow_t { edge_myflow };
  64 enum edge_mycapacity_t { edge_mycapacity };
  65
  66 namespace boost {
  67   BOOST_INSTALL_PROPERTY(edge, myflow);
  68   BOOST_INSTALL_PROPERTY(edge, mycapacity);
  69 }
  70
  71
  72 template <class Graph>
  73 void print_network(const Graph& G)
  74 {
  75   typedef typename boost::graph_traits<Graph>::vertex_iterator    Viter;
  76   typedef typename boost::graph_traits<Graph>::out_edge_iterator OutEdgeIter;
  77   typedef typename boost::graph_traits<Graph>::in_edge_iterator InEdgeIter;
  78
  79   typename property_map<Graph, edge_mycapacity_t>::const_type
  80     capacity = get(edge_mycapacity, G);
  81   typename property_map<Graph, edge_myflow_t>::const_type
  82     flow = get(edge_myflow, G);
  83
  84   Viter ui, uiend;
  85   boost::tie(ui, uiend) = vertices(G);
  86
  87   for (; ui != uiend; ++ui) {
  88     OutEdgeIter out, out_end;
  89     cout << *ui << "\t";
  90
  91     boost::tie(out, out_end) = out_edges(*ui, G);
  92     for(; out != out_end; ++out)
  93       cout << "--(" << capacity[*out] << ", " << flow[*out] << ")--> "
  94            << target(*out,G) << "\t";
  95
  96     InEdgeIter in, in_end;
  97     cout << endl << "\t";
  98     boost::tie(in, in_end) = in_edges(*ui, G);
  99     for(; in != in_end; ++in)
 100       cout << "<--(" << capacity[*in] << "," << flow[*in] << ")-- "
 101            << source(*in,G) << "\t";
 102
 103     cout << endl;
 104   }
 105 }
 106
 107
 108 int main(int , char* [])
 109 {
 110   typedef property<edge_mycapacity_t, int> Cap;
 111   typedef property<edge_myflow_t, int, Cap> Flow;
 112   typedef adjacency_list<vecS, vecS, bidirectionalS,
 113      no_property, Flow> Graph;
 114
 115   const int num_vertices = 9;
 116   Graph G(num_vertices);
 117
 118   /*          2<----5
 119              /       ^
 120             /         \
 121            V           \
 122     0 ---->1---->3----->6--->8
 123            \           ^
 124             \         /
 125              V       /
 126              4----->7
 127    */
 128
 129   add_edge(0, 1, Flow(10, Cap(8)), G);
 130
 131   add_edge(1, 4, Flow(20, Cap(12)), G);
 132   add_edge(4, 7, Flow(20, Cap(12)), G);
 133   add_edge(7, 6, Flow(20, Cap(12)), G);
 134
 135   add_edge(1, 3, Flow(40, Cap(12)), G);
 136   add_edge(3, 6, Flow(40, Cap(12)), G);
 137
 138   add_edge(6, 5, Flow(20, Cap(16)), G);
 139   add_edge(5, 2, Flow(20, Cap(16)), G);
 140   add_edge(2, 1, Flow(20, Cap(16)), G);
 141
 142   add_edge(6, 8, Flow(10, Cap(8)), G);
 143
 144   print_network(G);
 145
 146   property_map<Graph, edge_myflow_t>::type
 147     flow = get(edge_myflow, G);
 148
 149   boost::graph_traits<Graph>::vertex_iterator v, v_end;
 150   boost::graph_traits<Graph>::out_edge_iterator e, e_end;
 151   int f = 0;
 152   for (boost::tie(v, v_end) = vertices(G); v != v_end; ++v)
 153     for (boost::tie(e, e_end) = out_edges(*v, G); e != e_end; ++e)
 154       flow[*e] = ++f;
 155   cout << endl << endl;
 156
 157   remove_edge(6, 8, G);
 158
 159   print_network(G);
 160
 161
 162   return 0;
 163 }