graph/test/min_cost_max_flow_utils.hpp

//=======================================================================
// Copyright 2013 University of Warsaw.
// Authors: Piotr Wygocki
//
// 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)
//=======================================================================

#ifndef SAMPLE_GRAPH_UNDIRECTED_HPP
#define SAMPLE_GRAPH_UNDIRECTED_HPP

#include <iostream>
#include <cstdlib>
#include <boost/graph/adjacency_list.hpp>

namespace boost
{
struct SampleGraph
{
    typedef adjacency_list_traits< vecS, vecS, directedS > Traits;

    typedef adjacency_list< vecS, vecS, directedS, no_property,
        property< edge_capacity_t, long,
            property< edge_residual_capacity_t, long,
                property< edge_reverse_t, Traits::edge_descriptor,
                    property< edge_weight_t, long > > > > >
        Graph;
    typedef property_map< Graph, edge_capacity_t >::type Capacity;
    typedef property_map< Graph, edge_residual_capacity_t >::type
        ResidualCapacity;
    typedef property_map< Graph, edge_weight_t >::type Weight;
    typedef property_map< Graph, edge_reverse_t >::type Reversed;
    typedef boost::graph_traits< Graph >::vertices_size_type size_type;
    typedef Traits::vertex_descriptor vertex_descriptor;

    template < class Graph, class Weight, class Capacity, class Reversed,
        class ResidualCapacity >
    class EdgeAdder
    {
    public:
        EdgeAdder(
            Graph& g, Weight& w, Capacity& c, Reversed& rev, ResidualCapacity&)
        : m_g(g), m_w(w), m_cap(c), m_rev(rev)
        {
        }
        void addEdge(vertex_descriptor v, vertex_descriptor w, long weight,
            long capacity)
        {
            Traits::edge_descriptor e, f;
            e = add(v, w, weight, capacity);
            f = add(w, v, -weight, 0);
            m_rev[e] = f;
            m_rev[f] = e;
        }

    private:
        Traits::edge_descriptor add(vertex_descriptor v, vertex_descriptor w,
            long weight, long capacity)
        {
            bool b;
            Traits::edge_descriptor e;
            boost::tie(e, b) = add_edge(vertex(v, m_g), vertex(w, m_g), m_g);
            if (!b)
            {
                std::cerr << "Edge between " << v << " and " << w
                          << " already exists." << std::endl;
                std::abort();
            }
            m_cap[e] = capacity;
            m_w[e] = weight;
            return e;
        }
        Graph& m_g;
        Weight& m_w;
        Capacity& m_cap;
        Reversed& m_rev;
    };

    static void getSampleGraph(
        Graph& g, vertex_descriptor& s, vertex_descriptor& t)
    {
        Capacity capacity = get(edge_capacity, g);
        Reversed rev = get(edge_reverse, g);
        ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
        Weight weight = get(edge_weight, g);
        getSampleGraph(g, s, t, capacity, residual_capacity, weight, rev);
    }

    template < class Graph, class Weight, class Capacity, class Reversed,
        class ResidualCapacity >
    static void getSampleGraph(Graph& g, vertex_descriptor& s,
        vertex_descriptor& t, Capacity capacity,
        ResidualCapacity residual_capacity, Weight weight, Reversed rev)
    {
        size_type N(6);

        for (size_type i = 0; i < N; ++i)
        {
            add_vertex(g);
        }

        s = 0;
        t = 5;

        EdgeAdder< Graph, Weight, Capacity, Reversed, ResidualCapacity > ea(
            g, weight, capacity, rev, residual_capacity);

        ea.addEdge(0, 1, 4, 2);
        ea.addEdge(0, 2, 2, 2);

        ea.addEdge(1, 3, 2, 2);
        ea.addEdge(1, 4, 1, 1);
        ea.addEdge(2, 3, 1, 1);
        ea.addEdge(2, 4, 1, 1);

        ea.addEdge(3, 5, 4, 20);
        ea.addEdge(4, 5, 2, 20);
    }

    static void getSampleGraph2(
        Graph& g, vertex_descriptor& s, vertex_descriptor& t)
    {

        const boost::graph_traits< Graph >::vertices_size_type N(5);
        typedef property_map< Graph, edge_reverse_t >::type Reversed;

        for (size_type i = 0; i < N; ++i)
        {
            add_vertex(g);
        }

        Capacity capacity = get(edge_capacity, g);
        Reversed rev = get(edge_reverse, g);
        ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
        Weight weight = get(edge_weight, g);

        s = 0;
        t = 4;

        EdgeAdder< Graph, Weight, Capacity, Reversed, ResidualCapacity > ea(
            g, weight, capacity, rev, residual_capacity);

        ea.addEdge(0, 1, 4, 2);
        ea.addEdge(0, 2, 2, 2);
        ea.addEdge(1, 2, 2, 2);
        ea.addEdge(2, 3, 1, 1);
        ea.addEdge(2, 4, 1, 1);
        ea.addEdge(3, 4, 1, 1);

        ea.addEdge(1, 0, 2, 2);
        ea.addEdge(2, 0, 1, 1);
        ea.addEdge(2, 1, 5, 2);
        ea.addEdge(3, 2, 1, 1);
        ea.addEdge(4, 2, 2, 2);
        ea.addEdge(4, 3, 1, 3);
    }
};
} // boost

#endif /* SAMPLE_GRAPH_UNDIRECTED_HPP */