//            Copyright Daniel Trebbien 2010.
// Distributed under the Boost Software License, Version 1.0.
//   (See accompanying file LICENSE_1_0.txt or the copy at
//         http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_STOER_WAGNER_MINCUT_HPP
#define BOOST_GRAPH_STOER_WAGNER_MINCUT_HPP 1

#include <algorithm>
#include <functional>
#include <map>
#include <utility>
#include <vector>
#include <boost/concept_check.hpp>
#include <boost/scoped_array.hpp>
#include <boost/concept/assert.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/typeof/typeof.hpp>

namespace boost {

template <class unweighted_graph_>
class constant_weight_property_map
{
    typedef BOOST_DEDUCED_TYPENAME boost::graph_traits<unweighted_graph_>::edge_descriptor edge_descriptor;
    typedef BOOST_DEDUCED_TYPENAME boost::graph_traits<unweighted_graph_>::edges_size_type edges_size_type;

public:
    typedef boost::readable_property_map_tag category;
    typedef edge_descriptor key_type;
    typedef edges_size_type value_type;
    typedef edges_size_type reference;
    
    friend inline value_type get(constant_weight_property_map constantWeights, key_type) {
        return 1;
    }
};

template <class unweighted_graph_>
inline constant_weight_property_map<unweighted_graph_> make_constant_weight_property_map(const unweighted_graph_&) {
    return constant_weight_property_map<unweighted_graph_>();
}

namespace detail {

/**
 * \brief Performs a phase of the Stoer–Wagner min-cut algorithm
 *
 * Performs a \em phase of the Stoer–Wagner min-cut algorithm.
 *
 * As described by Stoer & Wagner (1997), a phase is simply a maximum adjacency search
 * (also called a maximum cardinality search), which results in the selection of two vertices
 * \em s and \em t, and, as a side product, a minimum <em>s</em>-<em>t</em> cut of
 * the input graph. Here, the input graph is basically \p g, but some vertices are virtually
 * assigned to others as a way of viewing \p g as a graph with some sets of
 * vertices merged together.
 *
 * This implementation is a translation of pseudocode by Professor Uri Zwick,
 * School of Computer Science, Tel Aviv University.
 *
 * \pre \p g is a connected, undirected graph
 * \param[in] g the input graph
 * \param[in] weights a property map from each edge to its weight (a non-negative value)
 * \param[in] vertexIndices a property map from each vertex to an index in [0, num_vertices(g))
 * \param[in] assignments a property map from each vertex to the vertex that it is assigned to
 * \param[out] indicesInHeap a read/write property map from each vertex to its index in a priority queue.
 *     This map serves as work space, and no particular meaning should be derived from property values
 *     after completion of this function.
 * \param[out] wAs a read/write property map from each vertex to an accumulated weight value. This map
 *     serves as work space, and no particular meaning should be derived from property values
 *     after completion of this function.
 * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and "<em>t</em>"
 *     of the minimum <em>s</em>-<em>t</em> cut and the cut weight \em w
 *     of the minimum <em>s</em>-<em>t</em> cut.
 * \see http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf
 *
 * \author Daniel Trebbien
 * \date 2010-07-01
 */
template <class undirected_graph_, class weight_map_, class vertex_index_map_, class vertex_assignment_map_, class index_in_heap_map_, class wA_map_>
boost::tuple<typename boost::graph_traits<undirected_graph_>::vertex_descriptor, typename boost::graph_traits<undirected_graph_>::vertex_descriptor, typename boost::property_traits<weight_map_>::value_type> stoer_wagner_phase(const undirected_graph_& g, weight_map_ weights, vertex_index_map_ vertexIndices, vertex_assignment_map_ assignments, index_in_heap_map_ indicesInHeap, wA_map_ wAs)
{
    typedef typename boost::graph_traits<undirected_graph_>::vertex_descriptor vertex_descriptor;
    typedef typename boost::property_traits<weight_map_>::value_type weight_type;
    
    boost::d_ary_heap_indirect<vertex_descriptor, 4, index_in_heap_map_, wA_map_, std::greater<weight_type> > pq(wAs, indicesInHeap);
    
    BGL_FORALL_VERTICES_T(v, g, undirected_graph_) {
        put(wAs, v, weight_type(0));
        
        if (v == get(assignments, v)) { // foreach u \in V do
            pq.push(v);
        }
    }
    
    vertex_descriptor s, t;
    weight_type w;
    while (!pq.empty()) { // while PQ \neq {} do
        const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
        w = get(wAs, u);
        pq.pop();
        
        s = t; t = u;
        BGL_FORALL_VERTICES_T(uPrime, g, undirected_graph_) {
            if (get(assignments, uPrime) == u) {
                BGL_FORALL_OUTEDGES_T(uPrime, e, g, undirected_graph_) { // foreach (u, v) \in E do
                    const vertex_descriptor v = get(assignments, target(e, g));
                    
                    if (pq.contains(v)) { // if v \in PQ then
                        put(wAs, v, get(wAs, v) + get(weights, e));
                        pq.update(v);
                    }
                }
            }
        }
    }
    
    return boost::make_tuple(s, t, w);
}

} // end `namespace detail` within `namespace boost`

/**
 * \brief Computes a min-cut of the input graph
 *
 * Computes a min-cut of the input graph using the Stoer–Wagner algorithm.
 *
 * \pre \p g is a connected, undirected graph
 * \param[in] g the input graph
 * \param[in] weights a property map from each edge to its weight (a non-negative value)
 * \param[out] parities a writable property map from each vertex to an unspecified-bool-type object for
 *     distinguishing the two vertex sets of the min-cut
 * \param[in] vertexIndices a property map from each vertex to an index in [0, num_vertices(g))
 * \param[out] assignments a read/write property map from each vertex to a \c vertex_descriptor object. This
 *     map serves as work space, and no particular meaning should be derived from property values
 *     after completion of the algorithm.
 * \param[out] indicesInHeap a read/write property map from each vertex to its index in a priority queue.
 *     This map serves as work space for <tt>boost::detail::stoer_wagner_phase</tt>,
 *     and no particular meaning should be derived from property values after completion of this function.
 * \param[out] wAs a read/write property map from each vertex to an accumulated weight value. This map
 *     serves as work space for <tt>boost::detail::stoer_wagner_phase</tt>,
 *     and no particular meaning should be derived from property values after completion of this function.
 * \returns the cut weight of the min-cut
 * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf
 * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf
 *
 * \author Daniel Trebbien
 * \date 2010-07-01
 */
template <class undirected_graph_, class weight_map_, class parity_map_, class vertex_index_map_, class vertex_assignment_map_, class index_in_heap_map_, class wA_map_>
typename boost::property_traits<weight_map_>::value_type stoer_wagner_mincut(const undirected_graph_& g, weight_map_ weights, parity_map_ parities, vertex_index_map_ vertexIndices, vertex_assignment_map_ assignments, index_in_heap_map_ indicesInHeap, wA_map_ wAs)
{
    BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<undirected_graph_>));
    BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<undirected_graph_>));

    typedef typename boost::graph_traits<undirected_graph_>::vertex_descriptor vertex_descriptor;
    typedef typename boost::graph_traits<undirected_graph_>::vertices_size_type vertices_size_type;
    typedef typename boost::graph_traits<undirected_graph_>::edge_descriptor edge_descriptor;
    
    BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<undirected_graph_>::directed_category, boost::undirected_tag>));
    BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<weight_map_, edge_descriptor>));
    typedef typename boost::property_traits<weight_map_>::value_type weight_type;
    BOOST_CONCEPT_ASSERT((boost::WritablePropertyMapConcept<parity_map_, vertex_descriptor>));
    typedef typename boost::property_traits<parity_map_>::value_type parity_type;
    BOOST_CONCEPT_ASSERT((boost::Convertible<bool, parity_type>));
    BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<vertex_index_map_, vertex_descriptor>));
    BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<vertex_assignment_map_, vertex_descriptor>));
    BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<vertex_assignment_map_>::value_type>));
    BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<index_in_heap_map_, vertex_descriptor>));
    BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<wA_map_, vertex_descriptor>));
    
    vertices_size_type n = num_vertices(g);
    if (n < 2)
        throw std::invalid_argument("the input graph must have at least two vertices.");
    
    // initialize `assignments` (all vertices are initially assigned to themselves)
    BGL_FORALL_VERTICES_T(v, g, undirected_graph_) {
        put(assignments, v, v);
    }
    
    vertex_descriptor s, t;
    weight_type bestW;
    
    boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(g, weights, vertexIndices, assignments, indicesInHeap, wAs);
    BGL_FORALL_VERTICES_T(v, g, undirected_graph_) {
        put(parities, v, parity_type(v == t ? true : false));
    }
    put(assignments, t, s);
    --n;
    
    for (; n >= 2; --n) {
        weight_type w;
        boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g, weights, vertexIndices, assignments, indicesInHeap, wAs);
        
        if (w < bestW) {
            BGL_FORALL_VERTICES_T(v, g, undirected_graph_) {
                put(parities, v, parity_type(get(assignments, v) == t ? true : false));
                
                if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
                    put(assignments, v, s);
            }
            
            bestW = w;
        }
        else {
            BGL_FORALL_VERTICES_T(v, g, undirected_graph_) {
                if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
                    put(assignments, v, s);
            }
        }
        put(assignments, t, s);
    }

    return bestW;
}

template <class undirected_graph_, class weight_map_, class parity_map_, class vertex_index_map_, class vertex_assignment_map_>
inline typename boost::property_traits<weight_map_>::value_type stoer_wagner_mincut(const undirected_graph_& g, weight_map_ weights, parity_map_ parities, vertex_index_map_ vertexIndices, vertex_assignment_map_ assignments)
{
    typedef typename boost::graph_traits<undirected_graph_>::vertex_descriptor vertex_descriptor;
    typedef typename boost::property_traits<weight_map_>::value_type weight_type;
    
    typedef typename std::vector<vertex_descriptor>::size_type heap_container_size_type;
    std::vector<heap_container_size_type> indexInHeap(num_vertices(g));
    typedef boost::iterator_property_map<BOOST_TYPEOF(indexInHeap.begin()), vertex_index_map_> index_in_heap_map;
    index_in_heap_map indicesInHeap(indexInHeap.begin(), vertexIndices);
    
    std::vector<weight_type> wA(num_vertices(g));
    typedef boost::iterator_property_map<BOOST_TYPEOF(wA.begin()), vertex_index_map_> wA_map;
    wA_map wAs(wA.begin(), vertexIndices);
    
    return stoer_wagner_mincut(g, weights, parities, vertexIndices, assignments, indicesInHeap, wAs);
}

} // end `namespace boost`

#include <boost/graph/iteration_macros_undef.hpp>

#endif // !BOOST_GRAPH_STOER_WAGNER_MINCUT_HPP