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 | template <class Graph, class CapacityMap, class IndexMap> |
47 | void write_dimacs_max_flow(const Graph& g, |
48 | CapacityMap capacity, |
49 | IndexMap idx, |
50 | typename graph_traits<Graph>::vertex_descriptor src, |
51 | typename graph_traits<Graph>::vertex_descriptor sink, |
52 | std::ostream& out) |
53 | { |
54 | typedef typename graph_traits<Graph>::edge_iterator edge_iterator; |
55 | |
56 | out << "c DIMACS max-flow file generated from boost::write_dimacs_max_flow" << std::endl; |
57 | out << "p max " << num_vertices(g) << " " << num_edges(g) << std::endl; //print problem description "max" and number of verts and edges |
58 | out << "n " << get(idx, src) + 1 << " s" << std::endl;; //say which one is source |
59 | out << "n " << get(idx, sink) + 1 << " t" << std::endl; //say which one is sink |
60 | |
61 | //output the edges |
62 | edge_iterator ei, e_end; |
63 | for(boost::tie(ei,e_end) = edges(g); ei!=e_end; ++ei){ |
64 | out << "a " << idx[ source(*ei, g) ] + 1 << " " << idx[ target(*ei, g) ] + 1 << " " << get(capacity,*ei) << std::endl; |
65 | } |
66 | } |
67 | |
68 | } // namespace boost |
69 | |