Boost C++ Libraries

libs/graph/example/read_write_dimacs-eg.cpp

//  Copyright (c) 2006, Stephan Diederich
//
//  This code may be used under either of the following two licences:
//
//    Permission is hereby granted, free of charge, to any person
//    obtaining a copy of this software and associated documentation
//    files (the "Software"), to deal in the Software without
//    restriction, including without limitation the rights to use,
//    copy, modify, merge, publish, distribute, sublicense, and/or
//    sell copies of the Software, and to permit persons to whom the
//    Software is furnished to do so, subject to the following
//    conditions:
//
//    The above copyright notice and this permission notice shall be
//    included in all copies or substantial portions of the Software.
//
//    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
//    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
//    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
//    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
//    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
//    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
//    OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
//
//  Or:
//
//    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)

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/write_dimacs.hpp>

/*************************************
 *
 * example which reads in a max-flow problem from std::cin, augments all paths
 *from source->NODE->sink and writes the graph back to std::cout
 *
 **************************************/

template < typename EdgeCapacityMap > struct zero_edge_capacity
{

    zero_edge_capacity() {}
    zero_edge_capacity(EdgeCapacityMap cap_map) : m_cap_map(cap_map) {};

    template < typename Edge > bool operator()(const Edge& e) const
    {
        return get(m_cap_map, e) == 0;
    }

    EdgeCapacityMap m_cap_map;
};

int main()
{
    using namespace boost;
    typedef adjacency_list_traits< vecS, vecS, directedS > Traits;
    typedef adjacency_list< vecS, vecS, directedS, no_property,
        property< edge_capacity_t, long,
            property< edge_reverse_t, Traits::edge_descriptor > > >
        Graph;

    typedef graph_traits< Graph >::out_edge_iterator out_edge_iterator;
    typedef graph_traits< Graph >::edge_descriptor edge_descriptor;
    typedef graph_traits< Graph >::vertex_descriptor vertex_descriptor;

    Graph g;

    typedef property_map< Graph, edge_capacity_t >::type tCapMap;
    typedef tCapMap::value_type tCapMapValue;

    typedef property_map< Graph, edge_reverse_t >::type tRevEdgeMap;

    tCapMap capacity = get(edge_capacity, g);
    tRevEdgeMap rev = get(edge_reverse, g);

    vertex_descriptor s, t;
    /*reading the graph from stdin*/
    read_dimacs_max_flow(g, capacity, rev, s, t, std::cin);

    /*process graph*/
    tCapMapValue augmented_flow = 0;

    // we take the source node and check for each outgoing edge e which has a
    // target(p) if we can augment that path
    out_edge_iterator oei, oe_end;
    for (boost::tie(oei, oe_end) = out_edges(s, g); oei != oe_end; ++oei)
    {
        edge_descriptor from_source = *oei;
        vertex_descriptor v = target(from_source, g);
        edge_descriptor to_sink;
        bool is_there;
        boost::tie(to_sink, is_there) = edge(v, t, g);
        if (is_there)
        {
            if (get(capacity, to_sink) > get(capacity, from_source))
            {
                tCapMapValue to_augment = get(capacity, from_source);
                capacity[from_source] = 0;
                capacity[to_sink] -= to_augment;
                augmented_flow += to_augment;
            }
            else
            {
                tCapMapValue to_augment = get(capacity, to_sink);
                capacity[to_sink] = 0;
                capacity[from_source] -= to_augment;
                augmented_flow += to_augment;
            }
        }
    }

    // remove edges with zero capacity (most of them are the reverse edges)
    zero_edge_capacity< tCapMap > filter(capacity);
    remove_edge_if(filter, g);

    /*write the graph back to stdout */
    write_dimacs_max_flow(
        g, capacity, identity_property_map(), s, t, std::cout);
    // print flow we augmented to std::cerr
    std::cerr << "removed " << augmented_flow
              << " from SOURCE->NODE->SINK connects" << std::endl;
    return 0;
}