//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

/*
   IMPORTANT!!!
   ~~~~~~~~~~~~
   This example uses interfaces that have been deprecated and removed from
   Boost.Grpah. Someone needs to update it, as it does NOT compile.
*/

#include <boost/config.hpp>
#include <algorithm>
#include <utility>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

namespace boost
{
template < typename Graph >
std::pair< typename graph_traits< Graph >::vertex_descriptor,
    typename graph_traits< Graph >::degree_size_type >
min_degree_vertex(Graph& g)
{
    typename graph_traits< Graph >::vertex_descriptor p;
    typedef typename graph_traits< Graph >::degree_size_type size_type;
    size_type delta = (std::numeric_limits< size_type >::max)();
    typename graph_traits< Graph >::vertex_iterator i, iend;
    for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
        if (degree(*i, g) < delta)
        {
            delta = degree(*i, g);
            p = *i;
        }
    return std::make_pair(p, delta);
}

template < typename Graph, typename OutputIterator >
void neighbors(const Graph& g,
    typename graph_traits< Graph >::vertex_descriptor u, OutputIterator result)
{
    typename graph_traits< Graph >::adjacency_iterator ai, aend;
    for (boost::tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
        *result++ = *ai;
}
template < typename Graph, typename VertexIterator, typename OutputIterator >
void neighbors(const Graph& g, VertexIterator first, VertexIterator last,
    OutputIterator result)
{
    for (; first != last; ++first)
        neighbors(g, *first, result);
}

template < typename VertexListGraph, typename OutputIterator >
typename graph_traits< VertexListGraph >::degree_size_type edge_connectivity(
    VertexListGraph& g, OutputIterator disconnecting_set)
{
    typedef typename graph_traits< VertexListGraph >::vertex_descriptor
        vertex_descriptor;
    typedef typename graph_traits< VertexListGraph >::degree_size_type
        degree_size_type;
    typedef color_traits< default_color_type > Color;
    typedef
        typename adjacency_list_traits< vecS, vecS, directedS >::edge_descriptor
            edge_descriptor;
    typedef adjacency_list< vecS, vecS, directedS, no_property,
        property< edge_capacity_t, degree_size_type,
            property< edge_residual_capacity_t, degree_size_type,
                property< edge_reverse_t, edge_descriptor > > > >
        FlowGraph;

    vertex_descriptor u, v, p, k;
    edge_descriptor e1, e2;
    bool inserted;
    typename graph_traits< VertexListGraph >::vertex_iterator vi, vi_end;
    degree_size_type delta, alpha_star, alpha_S_k;
    std::set< vertex_descriptor > S, neighbor_S;
    std::vector< vertex_descriptor > S_star, nonneighbor_S;
    std::vector< default_color_type > color(num_vertices(g));
    std::vector< edge_descriptor > pred(num_vertices(g));

    FlowGraph flow_g(num_vertices(g));
    typename property_map< FlowGraph, edge_capacity_t >::type cap
        = get(edge_capacity, flow_g);
    typename property_map< FlowGraph, edge_residual_capacity_t >::type res_cap
        = get(edge_residual_capacity, flow_g);
    typename property_map< FlowGraph, edge_reverse_t >::type rev_edge
        = get(edge_reverse, flow_g);

    typename graph_traits< VertexListGraph >::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    {
        u = source(*ei, g), v = target(*ei, g);
        boost::tie(e1, inserted) = add_edge(u, v, flow_g);
        cap[e1] = 1;
        boost::tie(e2, inserted) = add_edge(v, u, flow_g);
        cap[e2] = 1;
        rev_edge[e1] = e2;
        rev_edge[e2] = e1;
    }

    boost::tie(p, delta) = min_degree_vertex(g);
    S_star.push_back(p);
    alpha_star = delta;
    S.insert(p);
    neighbor_S.insert(p);
    neighbors(
        g, S.begin(), S.end(), std::inserter(neighbor_S, neighbor_S.begin()));
    std::set_difference(vertices(g).first, vertices(g).second,
        neighbor_S.begin(), neighbor_S.end(),
        std::back_inserter(nonneighbor_S));

    while (!nonneighbor_S.empty())
    {
        k = nonneighbor_S.front();
        alpha_S_k = edmonds_karp_max_flow(
            flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
        if (alpha_S_k < alpha_star)
        {
            alpha_star = alpha_S_k;
            S_star.clear();
            for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
                if (color[*vi] != Color::white())
                    S_star.push_back(*vi);
        }
        S.insert(k);
        neighbor_S.insert(k);
        neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
        nonneighbor_S.clear();
        std::set_difference(vertices(g).first, vertices(g).second,
            neighbor_S.begin(), neighbor_S.end(),
            std::back_inserter(nonneighbor_S));
    }

    std::vector< bool > in_S_star(num_vertices(g), false);
    typename std::vector< vertex_descriptor >::iterator si;
    for (si = S_star.begin(); si != S_star.end(); ++si)
        in_S_star[*si] = true;
    degree_size_type c = 0;
    for (si = S_star.begin(); si != S_star.end(); ++si)
    {
        typename graph_traits< VertexListGraph >::out_edge_iterator ei, ei_end;
        for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
            if (!in_S_star[target(*ei, g)])
            {
                *disconnecting_set++ = *ei;
                ++c;
            }
    }

    return c;
}

}

int main()
{
    using namespace boost;
    GraphvizGraph g;
    read_graphviz("figs/edge-connectivity.dot", g);

    typedef graph_traits< GraphvizGraph >::edge_descriptor edge_descriptor;
    typedef graph_traits< GraphvizGraph >::degree_size_type degree_size_type;
    std::vector< edge_descriptor > disconnecting_set;
    degree_size_type c
        = edge_connectivity(g, std::back_inserter(disconnecting_set));

    std::cout << "The edge connectivity is " << c << "." << std::endl;

    property_map< GraphvizGraph, vertex_attribute_t >::type attr_map
        = get(vertex_attribute, g);

    std::cout << "The disconnecting set is {";
    for (std::vector< edge_descriptor >::iterator i = disconnecting_set.begin();
         i != disconnecting_set.end(); ++i)
        std::cout << "(" << attr_map[source(*i, g)]["label"] << ","
                  << attr_map[target(*i, g)]["label"] << ") ";
    std::cout << "}." << std::endl;
    return EXIT_SUCCESS;
}