git.sesse.net Git - casparcg/blob - dependencies/boost/boost/graph/write_dimacs.hpp

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