boost/graph/write_dimacs.hpp

0001 //  Copyright (c) 2006, Stephan Diederich
0002 //
0003 //  This code may be used under either of the following two licences:
0004 //
0005 //    Permission is hereby granted, free of charge, to any person
0006 //    obtaining a copy of this software and associated documentation
0007 //    files (the "Software"), to deal in the Software without
0008 //    restriction, including without limitation the rights to use,
0009 //    copy, modify, merge, publish, distribute, sublicense, and/or
0010 //    sell copies of the Software, and to permit persons to whom the
0011 //    Software is furnished to do so, subject to the following
0012 //    conditions:
0013 //
0014 //    The above copyright notice and this permission notice shall be
0015 //    included in all copies or substantial portions of the Software.
0016 //
0017 //    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
0018 //    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
0019 //    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
0020 //    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
0021 //    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
0022 //    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
0023 //    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
0024 //    OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
0025 //
0026 //  Or:
0027 //
0028 //    Distributed under the Boost Software License, Version 1.0.
0029 //    (See accompanying file LICENSE_1_0.txt or copy at
0030 //    http://www.boost.org/LICENSE_1_0.txt)
0031
0032 /*
0033   Writes maximal flow problem in extended DIMACS format to an OutputIterator
0034   Vertex indices are read from an IndexMap and shiftet by 1.
0035   so their new range is [1..num_vertices(g)]
0036 */
0037
0038 /* ----------------------------------------------------------------- */
0039
0040 #include <vector>
0041 #include <string>
0042 #include <ostream>
0043
0044 namespace boost
0045 {
0046
0047 template < class Graph, class CapacityMap, class IndexMap >
0048 void write_dimacs_max_flow(const Graph& g, CapacityMap capacity, IndexMap idx,
0049     typename graph_traits< Graph >::vertex_descriptor src,
0050     typename graph_traits< Graph >::vertex_descriptor sink, std::ostream& out)
0051 {
0052     typedef typename graph_traits< Graph >::edge_iterator edge_iterator;
0053
0054     out << "c DIMACS max-flow file generated from boost::write_dimacs_max_flow"
0055         << std::endl;
0056     out << "p max " << num_vertices(g) << " " << num_edges(g)
0057         << std::endl; // print problem description "max" and number of verts and
0058                       // edges
0059     out << "n " << get(idx, src) + 1 << " s" << std::endl;
0060     ; // say which one is source
0061     out << "n " << get(idx, sink) + 1 << " t"
0062         << std::endl; // say which one is sink
0063
0064     // output the edges
0065     edge_iterator ei, e_end;
0066     for (boost::tie(ei, e_end) = edges(g); ei != e_end; ++ei)
0067     {
0068         out << "a " << idx[source(*ei, g)] + 1 << " " << idx[target(*ei, g)] + 1
0069             << " " << get(capacity, *ei) << std::endl;
0070     }
0071 }
0072
0073 } // namespace boost