projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <HTML> |
| 2 | <!-- | |
| 3 | // Copyright (c) 2006, Stephan Diederich | |
| 4 | // Copyright (c) 2010, Trustees of Indiana University | |
| 5 | // | |
| 6 | // This code may be used under either of the following two licences: | |
| 7 | // | |
| 8 | // Permission is hereby granted, free of charge, to any person | |
| 9 | // obtaining a copy of this software and associated documentation | |
| 10 | // files (the "Software"), to deal in the Software without | |
| 11 | // restriction, including without limitation the rights to use, | |
| 12 | // copy, modify, merge, publish, distribute, sublicense, and/or | |
| 13 | // sell copies of the Software, and to permit persons to whom the | |
| 14 | // Software is furnished to do so, subject to the following | |
| 15 | // conditions: | |
| 16 | // | |
| 17 | // The above copyright notice and this permission notice shall be | |
| 18 | // included in all copies or substantial portions of the Software. | |
| 19 | // | |
| 20 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |
| 21 | // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES | |
| 22 | // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND | |
| 23 | // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT | |
| 24 | // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, | |
| 25 | // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | |
| 26 | // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR | |
| 27 | // OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE. | |
| 28 | // | |
| 29 | // Or: | |
| 30 | // | |
| 31 | // Distributed under the Boost Software License, Version 1.0. | |
| 32 | // (See accompanying file LICENSE_1_0.txt or copy at | |
| 33 | // http://www.boost.org/LICENSE_1_0.txt) | |
| 34 | --> | |
| 35 | <Head> | |
| 36 | <Title>Boost Graph Library: read_dimacs_max_flow and read_dimacs_min_cut</Title> | |
| 37 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
| 38 | ALINK="#ff0000"> | |
| 39 | <IMG SRC="../../../boost.png" | |
| 40 | ALT="C++ Boost" width="277" height="86"> | |
| 41 | <BR Clear> | |
| 42 | ||
| 43 | <H1><A NAME="sec:read_dimacs_max_flow"> | |
| 44 | <TT>read_dimacs_max_flow</TT> | |
| 45 | </H1> | |
| 46 | ||
| 47 | ||
| 48 | <pre> | |
| 49 | //reads a graph with attached edge_capacity properties from an std::istream | |
| 50 | template <class Graph, class CapacityMap, class ReverseEdgeMap> | |
| 51 | int read_dimacs_max_flow(Graph& g, | |
| 52 | CapacityMap capacity, | |
| 53 | ReverseEdgeMap reverse_edge, | |
| 54 | typename graph_traits<Graph>::vertex_descriptor& src, | |
| 55 | typename graph_traits<Graph>::vertex_descriptor& sink, | |
| 56 | std::istream& in=std::cin) | |
| 57 | ||
| 58 | //reads a graph with attached edge_capacity properties from an std::istream | |
| 59 | template <class Graph, class CapacityMap, class ReverseEdgeMap> | |
| 60 | int read_dimacs_min_cut(Graph& g, | |
| 61 | CapacityMap capacity, | |
| 62 | ReverseEdgeMap reverse_edge, | |
| 63 | std::istream& in=std::cin) | |
| 64 | ||
| 65 | </pre> | |
| 66 | ||
| 67 | <p> | |
| 68 | These functions read a BGL graph object from a max-flow or min-cut problem description in extended dimacs format. (see <a href="http://www.avglab.com/andrew/CATS/maxflow_formats.htm"><TT>Goldberg's site</TT></a> for more information). For each edge found in the | |
| 69 | file an additional reverse_edge is added and set in the reverse_edge map. For | |
| 70 | max-flow problems, source and sink vertex descriptors are set according to the | |
| 71 | dimacs file. | |
| 72 | ||
| 73 | <H3>Where Defined</H3> | |
| 74 | ||
| 75 | <P> | |
| 76 | <a href="../../../boost/graph/read_dimacs.hpp"><TT>boost/graph/read_dimacs.hpp</TT></a> | |
| 77 | ||
| 78 | <h3>Parameters</h3> | |
| 79 | IN: <tt>Graph& g</tt> | |
| 80 | <blockquote> | |
| 81 | A directed or undirected graph. The graph's type must be a model of <a href="./IncidenceGraph.html">IncidenceGraph</a>. | |
| 82 | </blockquote> | |
| 83 | ||
| 84 | OUT: <tt>CapacityMap capacity</tt> | |
| 85 | <blockquote> | |
| 86 | A property map that models <a href="../../property_map/doc/LvaluePropertyMap.html">mutable Lvalue Property Map</a> whose key type is the edge descriptor of the graph. <br> | |
| 87 | </blockquote> | |
| 88 | ||
| 89 | OUT: <tt>ReverseEdgeMap reverse_edge</tt> | |
| 90 | <blockquote> | |
| 91 | A property map that models <a href="../../property_map/doc/LvaluePropertyMap.html">mutable Lvalue Property Map</a> whose key and value type is the edge descriptor of the graph. This map stores the corresponding reverse edge for each each in Graph g.<br> | |
| 92 | </blockquote> | |
| 93 | ||
| 94 | OUT: <tt>vertex_descriptor& src</tt> | |
| 95 | <blockquote> | |
| 96 | A graph vertex that will be set to the source of a max-flow problem. | |
| 97 | </blockquote> | |
| 98 | ||
| 99 | OUT: <tt>vertex_descriptor& sink</tt> | |
| 100 | <blockquote> | |
| 101 | A graph vertex that will be set to the sink of a max-flow problem. | |
| 102 | </blockquote> | |
| 103 | ||
| 104 | IN: <tt>std::istream& in</tt> | |
| 105 | <blockquote> | |
| 106 | A standard <tt>std::istream</tt> object. <br> | |
| 107 | <b>Default</b>: <tt>std::cin (for backward compatibility)</tt> | |
| 108 | </blockquote> | |
| 109 | ||
| 110 | <H3> | |
| 111 | Example | |
| 112 | </H3> | |
| 113 | A short <a href="../example/read_write_dimacs-eg.cpp">example</a> which uses read_dimacs and write_dimacs is located in the examples directory. | |
| 114 | ||
| 115 | <h3>See Also</h3> | |
| 116 | ||
| 117 | <a href="./write_dimacs.html"><tt>write_dimacs</tt></a> | |
| 118 | </BODY> | |
| 119 | </HTML> |