ceph/src/boost/libs/graph/example/read_write_dimacs-eg.cpp

   1 //  Copyright (c) 2006, Stephan Diederich
   2 //
   3 //  This code may be used under either of the following two licences:
   4 //
   5 //    Permission is hereby granted, free of charge, to any person
   6 //    obtaining a copy of this software and associated documentation
   7 //    files (the "Software"), to deal in the Software without
   8 //    restriction, including without limitation the rights to use,
   9 //    copy, modify, merge, publish, distribute, sublicense, and/or
  10 //    sell copies of the Software, and to permit persons to whom the
  11 //    Software is furnished to do so, subject to the following
  12 //    conditions:
  13 //
  14 //    The above copyright notice and this permission notice shall be
  15 //    included in all copies or substantial portions of the Software.
  16 //
  17 //    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18 //    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  19 //    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20 //    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  21 //    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  22 //    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  23 //    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  24 //    OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
  25 //
  26 //  Or:
  27 //
  28 //    Distributed under the Boost Software License, Version 1.0.
  29 //    (See accompanying file LICENSE_1_0.txt or copy at
  30 //    http://www.boost.org/LICENSE_1_0.txt)
  31
  32 #ifdef _MSC_VER
  33 #define _CRT_SECURE_NO_WARNINGS
  34 #endif
  35 #include <boost/config.hpp>
  36 #include <iostream>
  37 #include <string>
  38 #include <boost/graph/adjacency_list.hpp>
  39 #include <boost/graph/read_dimacs.hpp>
  40 #include <boost/graph/write_dimacs.hpp>
  41
  42
  43 /*************************************
  44 *
  45 * example which reads in a max-flow problem from std::cin, augments all paths from
  46 * source->NODE->sink and writes the graph back to std::cout
  47 *
  48 **************************************/
  49
  50 template <typename EdgeCapacityMap>
  51 struct zero_edge_capacity{
  52
  53   zero_edge_capacity() { }
  54   zero_edge_capacity(EdgeCapacityMap cap_map):m_cap_map(cap_map){};
  55
  56   template <typename Edge>
  57       bool operator() (const Edge& e) const {
  58     return  get(m_cap_map, e) == 0 ;
  59       }
  60
  61       EdgeCapacityMap m_cap_map;
  62 };
  63
  64 int main()
  65 {
  66   using namespace boost;
  67   typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
  68   typedef adjacency_list < vecS, vecS, directedS,
  69   no_property,
  70   property < edge_capacity_t, long,
  71   property < edge_reverse_t, Traits::edge_descriptor > > > Graph;
  72
  73   typedef graph_traits<Graph>::out_edge_iterator out_edge_iterator;
  74   typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
  75   typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  76
  77   Graph g;
  78
  79   typedef property_map < Graph, edge_capacity_t >::type tCapMap;
  80   typedef tCapMap::value_type tCapMapValue;
  81
  82   typedef property_map < Graph, edge_reverse_t >::type tRevEdgeMap;
  83
  84   tCapMap capacity = get(edge_capacity, g);
  85   tRevEdgeMap rev = get(edge_reverse, g);
  86
  87   vertex_descriptor s, t;
  88   /*reading the graph from stdin*/
  89   read_dimacs_max_flow(g, capacity, rev, s, t, std::cin);
  90
  91   /*process graph*/
  92   tCapMapValue augmented_flow = 0;
  93
  94   //we take the source node and check for each outgoing edge e which has a target(p) if we can augment that path
  95   out_edge_iterator oei,oe_end;
  96   for(boost::tie(oei, oe_end) = out_edges(s, g); oei != oe_end; ++oei){
  97     edge_descriptor from_source = *oei;
  98     vertex_descriptor v = target(from_source, g);
  99     edge_descriptor to_sink;
 100     bool is_there;
 101     boost::tie(to_sink, is_there) = edge(v, t, g);
 102     if( is_there ){
 103       if( get(capacity, to_sink) > get(capacity, from_source) ){
 104         tCapMapValue to_augment = get(capacity, from_source);
 105         capacity[from_source] = 0;
 106         capacity[to_sink] -= to_augment;
 107         augmented_flow += to_augment;
 108       }else{
 109         tCapMapValue to_augment = get(capacity, to_sink);
 110         capacity[to_sink] = 0;
 111         capacity[from_source] -= to_augment;
 112         augmented_flow += to_augment;
 113       }
 114     }
 115   }
 116
 117   //remove edges with zero capacity (most of them are the reverse edges)
 118   zero_edge_capacity<tCapMap> filter(capacity);
 119   remove_edge_if(filter, g);
 120
 121   /*write the graph back to stdout */
 122   write_dimacs_max_flow(g, capacity, identity_property_map(),s, t, std::cout);
 123   //print flow we augmented to std::cerr
 124   std::cerr << "removed " << augmented_flow << " from SOURCE->NODE->SINK connects" <<std::endl;
 125   return 0;
 126 }