#include <iostream>
#include <sstream>
#include <iomanip>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/graphviz.hpp>


using namespace boost;

typedef float EdgeWeightType;

typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
typedef adjacency_list < vecS, vecS, directedS,
  property < vertex_name_t, std::string,
    property < vertex_index_t, int,
      property < vertex_color_t, boost::default_color_type,
        property < vertex_distance_t, float,
          property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,

  property < edge_capacity_t, EdgeWeightType,
    property < edge_residual_capacity_t, EdgeWeightType,
      property < edge_reverse_t, Traits::edge_descriptor,
        property< edge_name_t, std::string> > > > > Graph;

Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1,
                                Traits::vertex_descriptor &v2,
                                property_map < Graph, edge_reverse_t >::type &rev,
                                const double capacity,
                                Graph &g,
                                const double reverseCapacity= 0.0);

int main(int, char*[])
{
    // 1. Build graph.
    Graph g;
    property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
    property_map<Graph, edge_capacity_t>::type capacity = get(edge_capacity, g);
    property_map<Graph, edge_residual_capacity_t>::type residual_capacity = get(edge_residual_capacity, g);
    property_map< Graph, vertex_name_t>::type vertexNames= get( vertex_name, g);
    property_map< Graph, edge_name_t>::type edgeNames= get(edge_name, g);

    // Add source and sink vertices.
    Traits::vertex_descriptor source= add_vertex( g);
    Traits::vertex_descriptor sink= add_vertex( g);

    // Add other in-between vertices.
    Traits::vertex_descriptor v0= add_vertex( g);
    Traits::vertex_descriptor v1= add_vertex( g);
    Traits::vertex_descriptor v2= add_vertex( g);
    Traits::vertex_descriptor v3= add_vertex( g);

    // Add edges.
    AddEdge( source, v0, rev, 100.0, g, 0.0);
    AddEdge( v0, v2, rev, 1.0, g, 100.0);
    AddEdge( v2, sink, rev, 1.0, g, 0.0);

    AddEdge( source, v1, rev, 100.0, g, 0.0);
    AddEdge( v1, v3, rev, 1.0, g, 100.0);
    AddEdge( v3, sink, rev, 1.0, g, 0.0);

    // 2. Run B-K max flow.
    EdgeWeightType flow = boykov_kolmogorov_max_flow(g, source, sink);

    // 3. Set labels.
    vertexNames[ source]= "Source";
    vertexNames[ sink]= "Sink";
    vertexNames[ v0]= "V0";
    vertexNames[ v1]= "V1";
    vertexNames[ v2]= "V2";
    vertexNames[ v3]= "V3";

    graph_traits<Graph>::vertex_iterator u_iter, u_end;
    graph_traits<Graph>::out_edge_iterator ei, e_end;
    for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
    {
        for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
        {
            //double usedCapacity= capacity[*ei] - residual_capacity[*ei];
            std::ostringstream sstream;
            //sstream<< usedCapacity<< "/"<< capacity[ *ei];
            sstream<< residual_capacity[ *ei]<< "/"<< capacity[ *ei];
            edgeNames[ *ei]= sstream.str();
        }
    }

    // 4. Output .dot file.
    std::ofstream fout( "b-k_example_graph.dot");
    write_graphviz( fout, g,
                    boost::make_label_writer( boost::get( vertex_name, g)),
                    boost::make_label_writer( boost::get(edge_name, g))
                    );
    fout.close();
}

Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1, Traits::vertex_descriptor &v2, property_map < Graph, edge_reverse_t >::type &rev, const double capacity, Graph &g, const double reverseCapacity)
{
  Traits::edge_descriptor e1 = add_edge(v1, v2, g).first;
  Traits::edge_descriptor e2 = add_edge(v2, v1, g).first;
  put(edge_capacity, g, e1, capacity);
  put(edge_capacity, g, e2, reverseCapacity);

  rev[e1] = e2;
  rev[e2] = e1;
}