#include <fstream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/read_dimacs.hpp>

typedef int FlowValue;

int main (int argc, char **argv) {
    using namespace boost;
    typedef adjacency_list_traits <vecS, vecS, directedS> Traits;
    typedef adjacency_list <vecS, vecS, directedS,
            property <vertex_predecessor_t, Traits::edge_descriptor,
            property <vertex_color_t, default_color_type,
            property <vertex_distance_t, size_t> > >,

            property <edge_capacity_t, FlowValue,
            property <edge_residual_capacity_t, FlowValue,
            property <edge_reverse_t, Traits::edge_descriptor > > > > Graph;

    typedef Graph::vertex_descriptor Vertex;

    if (argc != 2) {
        std::cout << "Usage: test-flow infile.dimacs\n";
        exit(-1);
    }

    std::ifstream infile(argv[1]);

    Graph g;
    Vertex s, t;

    read_dimacs_max_flow(g, boost::get(edge_capacity, g), boost::get(edge_reverse, g), s, t, infile);

    FlowValue flow = boykov_kolmogorov_max_flow(g, s, t);
    std::cout << "BK flow: " << flow << "\n";
    flow = push_relabel_max_flow(g, s, t);
    std::cout << "PR flow: " << flow << "\n";
}