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
#include
#include
#include
#include <iostream>
#include <limits>
using namespace boost;
typedef adjacency_list_traits Traits;
typedef Traits::vertex_descriptor Vertex;
typedef Traits::edge_descriptor Edge;
typedef adjacency_list > > > >,
property > > > > Graph;
void addEdge(Graph& g, const Vertex& source, const Vertex& target, const double capacity,
const double reverseCapacity) {
property_map::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::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
