123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126 |
- // 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;
- }
|