//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// This file is part of the Boost Graph Library
//
// You should have received a copy of the License Agreement for the
// Boost Graph Library along with the software; see the file LICENSE.
// If not, contact Office of Research, University of Notre Dame, Notre
// Dame, IN 46556.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//=======================================================================
//
//  Sample output:
//
//   0	--(8, 10)--> 1	
//
//   1	--(12, 20)--> 4	--(12, 40)--> 3	
// 	  <--(8,10)-- 0	<--(16,20)-- 2	
//   2	--(16, 20)--> 1	
// 	  <--(16,20)-- 5	
//   3	--(12, 40)--> 6	
// 	  <--(12,40)-- 1	
//   4	--(12, 20)--> 7	
// 	  <--(12,20)-- 1	
//   5	--(16, 20)--> 2	
// 	  <--(16,20)-- 6	
//   6	--(16, 20)--> 5	--(8, 10)--> 8	
// 	  <--(12,20)-- 7	<--(12,40)-- 3	
//   7	--(12, 20)--> 6	
// 	  <--(12,20)-- 4	
//   8	
// 	  <--(8,10)-- 6	
//
//
//   0	--(8, 1)--> 1	
//
//   1	--(12, 2)--> 4	--(12, 3)--> 3	
// 	  <--(8,1)-- 0	<--(16,4)-- 2	
//   2	--(16, 4)--> 1	
// 	  <--(16,7)-- 5	
//   3	--(12, 5)--> 6	
// 	  <--(12,3)-- 1	
//   4	--(12, 6)--> 7	
// 	  <--(12,2)-- 1	
//   5	--(16, 7)--> 2	
// 	  <--(16,8)-- 6	
//   6	--(16, 8)--> 5	
// 	  <--(12,10)-- 7	<--(12,5)-- 3	
//   7	--(12, 10)--> 6	
// 	  <--(12,6)-- 4	
//   8	
//
	
#include <iostream>

#include <boost/utility.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/adjacency_list.hpp>


using namespace boost;
using namespace std;


// The unique numbers (using 100 and 101 here) are only needed for use
// in a workaround when the compiler does not do partial
// specialization.

enum edge_myflow_t { edge_myflow = 100 };
enum edge_mycapacity_t { edge_mycapacity = 101 };

namespace boost {
  BOOST_INSTALL_PROPERTY(edge, myflow);
  BOOST_INSTALL_PROPERTY(edge, mycapacity);
}


template <class Graph, class Capacity, class Flow>
void print_network(Graph& G, Capacity capacity, Flow flow)
{
  typedef typename boost::graph_traits<Graph>::vertex_iterator    Viter;
  typedef typename boost::graph_traits<Graph>::out_edge_iterator OutEdgeIter;
  typedef typename boost::graph_traits<Graph>::in_edge_iterator InEdgeIter;

  Viter ui, uiend;
  boost::tie(ui, uiend) = vertices(G);

  for (; ui != uiend; ++ui) {
    OutEdgeIter out, out_end;
    cout << *ui << "\t";

    boost::tie(out, out_end) = out_edges(*ui, G);
    for(; out != out_end; ++out)
      cout << "--(" << capacity[*out] << ", " << flow[*out] << ")--> "
           << target(*out,G) << "\t";

    InEdgeIter in, in_end;
    cout << endl << "\t";
    boost::tie(in, in_end) = in_edges(*ui, G);
    for(; in != in_end; ++in)
      cout << "<--(" << capacity[*in] << "," << flow[*in] << ")-- "
           << source(*in,G) << "\t";

    cout << endl;
  }
}


int main(int , char* [])
{
  typedef property<edge_mycapacity_t, int> Cap;
  typedef property<edge_myflow_t, int, Cap> Flow;
  typedef adjacency_list<vecS, vecS, bidirectionalS, 
     no_property, Flow> Graph;

  const int num_vertices = 9;
  Graph G(num_vertices);

  /*          2<----5 
             /       ^
            /         \
           V           \ 
    0 ---->1---->3----->6--->8
           \           ^
            \         /
             V       /
             4----->7
   */

  add_edge(0, 1, Flow(10, Cap(8)), G);

  add_edge(1, 4, Flow(20, Cap(12)), G);
  add_edge(4, 7, Flow(20, Cap(12)), G);
  add_edge(7, 6, Flow(20, Cap(12)), G);

  add_edge(1, 3, Flow(40, Cap(12)), G);
  add_edge(3, 6, Flow(40, Cap(12)), G);

  add_edge(6, 5, Flow(20, Cap(16)), G);
  add_edge(5, 2, Flow(20, Cap(16)), G);
  add_edge(2, 1, Flow(20, Cap(16)), G);

  add_edge(6, 8, Flow(10, Cap(8)), G);

  typedef boost::graph_traits<Graph>::edge_descriptor Edge;

  property_map<Graph, edge_mycapacity_t>::type
    capacity = get(edge_mycapacity, G);
  property_map<Graph, edge_myflow_t>::type
    flow = get(edge_myflow, G);

  print_network(G, capacity, flow);

  boost::graph_traits<Graph>::vertex_iterator v, v_end;
  boost::graph_traits<Graph>::out_edge_iterator e, e_end;
  int f = 0;
  for (tie(v, v_end) = vertices(G); v != v_end; ++v)
    for (tie(e, e_end) = out_edges(*v, G); e != e_end; ++e)
      flow[*e] = ++f;
  cout << endl << endl;

  remove_edge(6, 8, G);

  print_network(G, capacity, flow);

          
  return 0;
}
