[Boost-commit] svn:boost r64187 - in trunk: boost/graph libs/graph/doc

Subject: [Boost-commit] svn:boost r64187 - in trunk: boost/graph libs/graph/doc
From: jewillco_at_[hidden]
Date: 2010-07-19 23:52:59

Author: jewillco
Date: 2010-07-19 23:52:58 EDT (Mon, 19 Jul 2010)
New Revision: 64187
URL: http://svn.boost.org/trac/boost/changeset/64187

Log:
Added min-cut support to dimacs reader
Text files modified: 
   trunk/boost/graph/read_dimacs.hpp           |    41 ++++++++++++++++++++++++++++++++------- 
   trunk/libs/graph/doc/read_dimacs.html       |    34 ++++++++++++++++++++++++++------        
   trunk/libs/graph/doc/table_of_contents.html |     2                                         
   3 files changed, 61 insertions(+), 16 deletions(-)

Modified: trunk/boost/graph/read_dimacs.hpp
==============================================================================
--- trunk/boost/graph/read_dimacs.hpp	(original)
+++ trunk/boost/graph/read_dimacs.hpp	2010-07-19 23:52:58 EDT (Mon, 19 Jul 2010)
@@ -28,13 +28,16 @@
 
 namespace boost {
 
+  namespace detail {
+
 template <class Graph, class CapacityMap, class ReverseEdgeMap>
-int read_dimacs_max_flow(Graph& g,
-                         CapacityMap capacity,
-                         ReverseEdgeMap reverse_edge,
-                         typename graph_traits<Graph>::vertex_descriptor& src,
-                         typename graph_traits<Graph>::vertex_descriptor& sink,
-                         std::istream& in = std::cin)
+int read_dimacs_max_flow_internal(Graph& g,
+                                  CapacityMap capacity,
+                                  ReverseEdgeMap reverse_edge,
+                                  typename graph_traits<Graph>::vertex_descriptor& src,
+                                  typename graph_traits<Graph>::vertex_descriptor& sink,
+                                  std::istream& in,
+                                  bool require_source_and_sink)
 {
   //  const int MAXLINE = 100;      /* max line length in the input file */
   const int ARC_FIELDS = 3;     /* no of fields in arc line  */
@@ -203,7 +206,7 @@
       break;
 
     case 'a':                    /* arc description */
-      if ( no_nslines == 0 || no_nklines == 0 )
+      if ( require_source_and_sink && (no_nslines == 0 || no_nklines == 0) )
         /* there was not source and sink description above */
         { err_no = EN14; goto error; }
 
@@ -264,7 +267,8 @@
   if ( no_alines < m ) /* not enough arcs */
     { err_no = EN19; goto error; }
 
-  if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0  )
+  if ( require_source_and_sink &&
+       (out_degree(src, g) == 0 || out_degree(sink, g) == 0) )
     /* no arc goes out of the source */
     { err_no = EN20; goto error; }
 
@@ -282,6 +286,27 @@
 }
 /* --------------------   end of parser  -------------------*/
 
+  } // namespace detail
+
+template <class Graph, class CapacityMap, class ReverseEdgeMap>
+int read_dimacs_max_flow(Graph& g,
+                         CapacityMap capacity,
+                         ReverseEdgeMap reverse_edge,
+                         typename graph_traits<Graph>::vertex_descriptor& src,
+                         typename graph_traits<Graph>::vertex_descriptor& sink,
+                         std::istream& in = std::cin) {
+  return detail::read_dimacs_max_flow_internal(g, capacity, reverse_edge, src, sink, in, true);
+}
+
+template <class Graph, class CapacityMap, class ReverseEdgeMap>
+int read_dimacs_min_cut(Graph& g,
+                        CapacityMap capacity,
+                        ReverseEdgeMap reverse_edge,
+                        std::istream& in = std::cin) {
+  typename graph_traits<Graph>::vertex_descriptor dummy_src, dummy_sink; // Not filled in
+  return detail::read_dimacs_max_flow_internal(g, capacity, reverse_edge, dummy_src, dummy_sink, in, false);
+}
+
 } // namespace boost
 
 #endif // BOOST_GRAPH_READ_DIMACS_HPP

Modified: trunk/libs/graph/doc/read_dimacs.html
==============================================================================
--- trunk/libs/graph/doc/read_dimacs.html	(original)
+++ trunk/libs/graph/doc/read_dimacs.html	2010-07-19 23:52:58 EDT (Mon, 19 Jul 2010)
@@ -1,6 +1,7 @@
 <HTML>
 <!--
 //  Copyright (c) 2006, Stephan Diederich
+//  Copyright (c) 2010, Trustees of Indiana University
 //
 //  This code may be used under either of the following two licences:
 //
@@ -32,7 +33,7 @@
 //    http://www.boost.org/LICENSE_1_0.txt)
 -->
 <Head>
-<Title>Boost Graph Library: read_dimacs_max_flow</Title>
+<Title>Boost Graph Library: read_dimacs_max_flow and read_dimacs_min_cut</Title>
 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
         ALINK="#ff0000"> 
 <IMG SRC="../../../boost.png" 
@@ -47,18 +48,27 @@
 <pre>
 //reads a graph with attached edge_capacity properties from an std::istream
 template &lt;class Graph, class CapacityMap, class ReverseEdgeMap&gt;
-int read_dimacs_max_flow(Graph& g,
+int read_dimacs_max_flow(Graph&amp; g,
                          CapacityMap capacity, 
                          ReverseEdgeMap reverse_edge,
-                         typename graph_traits<Graph>::vertex_descriptor& src,
-                         typename graph_traits<Graph>::vertex_descriptor& sink,
-                         std::istream& in=std::cin)
+                         typename graph_traits<Graph>::vertex_descriptor&amp; src,
+                         typename graph_traits<Graph>::vertex_descriptor&amp; sink,
+                         std::istream&amp; in=std::cin)
+
+//reads a graph with attached edge_capacity properties from an std::istream
+template &lt;class Graph, class CapacityMap, class ReverseEdgeMap&gt;
+int read_dimacs_min_cut(Graph&amp; g,
+                        CapacityMap capacity, 
+                        ReverseEdgeMap reverse_edge,
+                        std::istream&amp; in=std::cin)
 
 </pre>
 
 <p>
-This method reads a BGL graph object from a max-flow problem description in extended dimacs format. (see Goldbergs site for more information). For each edge found in the 
-file an additional reverse_edge is added and set in the reverse_edge map. Source- and sink-vertex-descriptors are set according to the dimacs file.
+These functions read a BGL graph object from a max-flow or min-cut problem description in extended dimacs format. (see Goldberg's site for more information). For each edge found in the 
+file an additional reverse_edge is added and set in the reverse_edge map.  For
+max-flow problems, source and sink vertex descriptors are set according to the
+dimacs file.
  
 <H3>Where Defined</H3>
 
@@ -81,6 +91,16 @@
  A property map that models mutable Lvalue Property Map 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>
 </blockquote>  
   
+ OUT: <tt>vertex_descriptor&amp; src</tt>
+<blockquote>
+ A graph vertex that will be set to the source of a max-flow problem.
+</blockquote>  
+  
+ OUT: <tt>vertex_descriptor&amp; sink</tt>
+<blockquote>
+ A graph vertex that will be set to the sink of a max-flow problem.
+</blockquote>  
+  
  IN: <tt>std::istream&amp; in</tt>
 <blockquote>
   A standard <tt>std::istream</tt> object. <br>

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html	(original)
+++ trunk/libs/graph/doc/table_of_contents.html	2010-07-19 23:52:58 EDT (Mon, 19 Jul 2010)
@@ -286,7 +286,7 @@
          <li>Graph Input/Output
            <ol>
              <li>AT&amp;T Graphviz: read_graphviz, write_graphviz</li>
-             <li>DIMACS Max-flow: read_dimacs_max_flow, write_dimacs_max_flow</li>
+             <li>DIMACS Max-flow: read_dimacs_max_flow and read_dimacs_min_cut, write_dimacs_max_flow</li>
              <li>GraphML: read_graphml and write_graphml</li>
            </ol></li>