[Boost-users] [graph] Vertex order and VertexList type changes boykov_kolmogorov_max_flow result

Subject: [Boost-users] [graph] Vertex order and VertexList type changes boykov_kolmogorov_max_flow result
From: Michael J Iatauro (Michael.J.Iatauro_at_[hidden])
Date: 2014-09-04 17:51:04

In the code below, using listS to store vertices results in vertex instantiation order 
changing the amount of flow computed by boykov_kolmogorov_max_flow.  As given, it computes 
a flow of 0.  If I move the instantiation of "T-" to be before "t-" or switch the 
VertexList parameter of adjacency_list to vecS, it computes the correct flow of 1000.

Stepping through the code, it looks like when the max_flow function iterates over vertices 
that are targets of out-edges from the source, the call to get(m_in_active_list_map, v) at 
boykov_kolmogorov_max_flow.hpp:528 returns true for the second vertex, preventing it from 
getting added to m_active_nodes.

I tested this using g++ 4.4.7 and with Boost 1.55 and 1.56.
Has anybody else seen anything like this?

Code follows:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>

#include <iostream>
#include <limits>

using namespace boost;

typedef adjacency_list_traits<vecS, listS, directedS> Traits;
typedef Traits::vertex_descriptor Vertex;
typedef Traits::edge_descriptor Edge;
typedef adjacency_list<vecS, listS, directedS,
                               property<vertex_name_t, std::string,
                               property<vertex_index_t, long,
                               property<vertex_color_t, default_color_type,
                               property<vertex_distance_t, long,
                               property<vertex_predecessor_t, Edge > > > > >,

                               property<edge_flow_t, double,
                               property<edge_capacity_t, double,
                               property<edge_residual_capacity_t, double,
                               property<edge_reverse_t, Edge > > > > > Graph;

void addEdge(Graph& g, const Vertex& source, const Vertex& target, const double capacity,
              const double reverseCapacity) {
   property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g);
   Edge e1 = add_edge(source, target, g).first;
   Edge e2 = add_edge(target, source, g).first;
   put(edge_capacity, g, e1, capacity);
   put(edge_capacity, g, e2, reverseCapacity);
   rev[e1] = e2;
   rev[e2] = e1;
}

int main(void) {
   Graph g;
   property_map<Graph, vertex_name_t>::type nameMap = get(vertex_name, g);

   Vertex source = add_vertex(g);
   nameMap[source] = "source";
   Vertex sink = add_vertex(g);
   nameMap[sink] = "sink";

   Vertex tminus = add_vertex(g);
   nameMap[tminus] = "t-";
   addEdge(g, source, tminus, 1, 0);

   Vertex Tminus = add_vertex(g);
   nameMap[Tminus] = "T-";
   addEdge(g, source, Tminus, 1000, 0);

   Vertex Tplus = add_vertex(g);
   nameMap[Tplus] = "T+";
   addEdge(g, Tplus, sink, 1000, 0);

   addEdge(g, Tplus, Tminus, 0, std::numeric_limits<int>::max());

   double flow = boykov_kolmogorov_max_flow(g, source, sink);
   std::cout << flow << std::endl;

   return 0;
}

-- 
------------------
Michael J. Iatauro
Software Engineer
QTS, Inc.
NASA Ames Research Center
Office: 650-604-0662
Mail stop: 269-2
P.O. Box 1
Moffett Field, CA 94035-0001