Chris@16: //  Copyright (c) 2006, Stephan Diederich
Chris@16: //
Chris@16: //  This code may be used under either of the following two licences:
Chris@16: //
Chris@16: //    Permission is hereby granted, free of charge, to any person
Chris@16: //    obtaining a copy of this software and associated documentation
Chris@16: //    files (the "Software"), to deal in the Software without
Chris@16: //    restriction, including without limitation the rights to use,
Chris@16: //    copy, modify, merge, publish, distribute, sublicense, and/or
Chris@16: //    sell copies of the Software, and to permit persons to whom the
Chris@16: //    Software is furnished to do so, subject to the following
Chris@16: //    conditions:
Chris@16: //
Chris@16: //    The above copyright notice and this permission notice shall be
Chris@16: //    included in all copies or substantial portions of the Software.
Chris@16: //
Chris@16: //    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
Chris@16: //    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
Chris@16: //    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
Chris@16: //    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
Chris@16: //    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
Chris@16: //    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
Chris@16: //    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
Chris@16: //    OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
Chris@16: //
Chris@16: //  Or:
Chris@16: //
Chris@16: //    Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //    http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: /*
Chris@16:   Writes maximal flow problem in extended DIMACS format to an OutputIterator
Chris@16:   Vertex indices are read from an IndexMap and shiftet by 1.
Chris@16:   so their new range is [1..num_vertices(g)]
Chris@16: */
Chris@16: 
Chris@16: /* ----------------------------------------------------------------- */
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <string>
Chris@16: #include <ostream>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: template <class Graph, class CapacityMap, class IndexMap>
Chris@16: void write_dimacs_max_flow(const Graph& g,
Chris@16:                          CapacityMap capacity, 
Chris@16:                          IndexMap idx,
Chris@16:                          typename graph_traits<Graph>::vertex_descriptor src,
Chris@16:                          typename graph_traits<Graph>::vertex_descriptor sink,
Chris@16:                          std::ostream& out)
Chris@16: {
Chris@16:   typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
Chris@16:    
Chris@16:   out << "c DIMACS max-flow file generated from boost::write_dimacs_max_flow" << std::endl;
Chris@16:   out << "p max " << num_vertices(g) << " " << num_edges(g) << std::endl; //print problem description "max" and number of verts and edges
Chris@16:   out << "n " << get(idx, src) + 1 << " s" << std::endl;; //say which one is source
Chris@16:   out << "n " << get(idx, sink) + 1 << " t" << std::endl; //say which one is sink
Chris@16:   
Chris@16:   //output the edges
Chris@16:   edge_iterator ei, e_end;
Chris@16:   for(boost::tie(ei,e_end) = edges(g); ei!=e_end; ++ei){
Chris@16:     out << "a " << idx[ source(*ei, g) ] + 1 << " " << idx[ target(*ei, g) ] + 1 << " " << get(capacity,*ei) << std::endl;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: } // namespace boost