1 // Copyright (c) 2006, Stephan Diederich 2 // 3 // This code may be used under either of the following two licences: 4 // 5 // Permission is hereby granted, free of charge, to any person 6 // obtaining a copy of this software and associated documentation 7 // files (the "Software"), to deal in the Software without 8 // restriction, including without limitation the rights to use, 9 // copy, modify, merge, publish, distribute, sublicense, and/or 10 // sell copies of the Software, and to permit persons to whom the 11 // Software is furnished to do so, subject to the following 12 // conditions: 13 // 14 // The above copyright notice and this permission notice shall be 15 // included in all copies or substantial portions of the Software. 16 // 17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 19 // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 21 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 22 // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 23 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 24 // OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE. 25 // 26 // Or: 27 // 28 // Distributed under the Boost Software License, Version 1.0. 29 // (See accompanying file LICENSE_1_0.txt or copy at 30 // http://www.boost.org/LICENSE_1_0.txt) 31 32 /* 33 Writes maximal flow problem in extended DIMACS format to an OutputIterator 34 Vertex indices are read from an IndexMap and shiftet by 1. 35 so their new range is [1..num_vertices(g)] 36 */ 37 38 /* ----------------------------------------------------------------- */ 39 40 #include <vector> 41 #include <string> 42 #include <ostream> 43 44 namespace boost 45 { 46 47 template < class Graph, class CapacityMap, class IndexMap > write_dimacs_max_flow(const Graph & g,CapacityMap capacity,IndexMap idx,typename graph_traits<Graph>::vertex_descriptor src,typename graph_traits<Graph>::vertex_descriptor sink,std::ostream & out)48 void write_dimacs_max_flow(const Graph& g, CapacityMap capacity, IndexMap idx, 49 typename graph_traits< Graph >::vertex_descriptor src, 50 typename graph_traits< Graph >::vertex_descriptor sink, std::ostream& out) 51 { 52 typedef typename graph_traits< Graph >::edge_iterator edge_iterator; 53 54 out << "c DIMACS max-flow file generated from boost::write_dimacs_max_flow" 55 << std::endl; 56 out << "p max " << num_vertices(g) << " " << num_edges(g) 57 << std::endl; // print problem description "max" and number of verts and 58 // edges 59 out << "n " << get(idx, src) + 1 << " s" << std::endl; 60 ; // say which one is source 61 out << "n " << get(idx, sink) + 1 << " t" 62 << std::endl; // say which one is sink 63 64 // output the edges 65 edge_iterator ei, e_end; 66 for (boost::tie(ei, e_end) = edges(g); ei != e_end; ++ei) 67 { 68 out << "a " << idx[source(*ei, g)] + 1 << " " << idx[target(*ei, g)] + 1 69 << " " << get(capacity, *ei) << std::endl; 70 } 71 } 72 73 } // namespace boost 74