I am trying to use boost::boykov_kolmogorov_max_flow to segment an image using the standard technique of starting with a grid graph on the image, and then adding a "special" source and sink node that every grid vertex is connected to.
I have constructed this graph for a 2x2 image (for a total of 2*2 + 2 = 6 nodes) to represent the most basic case, just to try to get the Boost types to agree. I have come up with this:
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
boost::no_property,
boost::property<boost::edge_index_t, std::size_t> > GraphType;
typedef boost::graph_traits<GraphType>::vertex_descriptor VertexDescriptor;
typedef boost::graph_traits<GraphType>::edge_descriptor EdgeDescriptor;
typedef boost::graph_traits<GraphType>::vertices_size_type VertexIndex;
typedef boost::graph_traits<GraphType>::edges_size_type EdgeIndex;
void AddBidirectionalEdge(GraphType& graph, unsigned int source, unsigned int target, float weight,
std::vector<EdgeDescriptor>& reverseEdges, std::vector<float>& capacity)
{
// Add edges between grid vertices. We have to create the edge and the reverse edge,
// then add the reverseEdge as the corresponding reverse edge to 'edge', and then add 'edge'
// as the corresponding reverse edge to 'reverseEdge'
EdgeDescriptor edge = add_edge(source, target, 1, graph).first;
EdgeDescriptor reverseEdge = add_edge(target, source, 1, graph).first;
reverseEdges.push_back(reverseEdge);
reverseEdges.push_back(edge);
capacity.push_back(weight);
capacity.push_back(weight);
}
int main()
{
GraphType graph;
unsigned int numberOfVertices = 2*2 + 2; // a 2x2 grid
std::vector<int> groups(numberOfVertices);
std::vector<EdgeDescriptor> reverseEdges;
std::vector<float> capacity;
float weight = 1;
AddBidirectionalEdge(graph, 0, 1, weight, reverseEdges, capacity);
AddBidirectionalEdge(graph, 1, 2, weight, reverseEdges, capacity);
AddBidirectionalEdge(graph, 2, 3, weight, reverseEdges, capacity);
AddBidirectionalEdge(graph, 3, 0, weight, reverseEdges, capacity);
int sourceId = 4;
int sinkId = 5;
// Add edges between all vertices and the source, as well as between all vertices and the sink
float highWeight = 1000;
for(size_t i = 0; i < 4; ++i)
{
AddBidirectionalEdge(graph, i, sourceId, highWeight, reverseEdges, capacity);
AddBidirectionalEdge(graph, i, sinkId, highWeight, reverseEdges, capacity);
}
std::vector<float> residual_capacity(num_edges(graph), 0);
VertexDescriptor sourceVertex = vertex(4,graph);
VertexDescriptor sinkVertex = vertex(5,graph);
// There should be 2*2 + 2 = 6 nodes
std::cout << "Number of vertices " << num_vertices(graph) << std::endl;
// There should be 4 + 4 + 4 = 12 edges
std::cout << "Number of edges " << num_edges(graph) << std::endl;
boost::boykov_kolmogorov_max_flow(graph,
boost::make_iterator_property_map(&capacity[0], get(boost::edge_index, graph)),
boost::make_iterator_property_map(&residual_capacity[0], get(boost::edge_index, graph)),
boost::make_iterator_property_map(&reverseEdges[0], get(boost::edge_index, graph)),
boost::make_iterator_property_map(&groups[0], get(boost::vertex_index, graph)),
get(boost::vertex_index, graph),
sourceVertex,
sinkVertex);
// Display the segmentation
for(size_t index=0; index < groups.size(); ++index)
{
std::cout << "Vertex " << index << " is in group " << groups[index] << std::endl;
}
return EXIT_SUCCESS;
}
It compiles, but at runtime I get:
Assertion `get(m_rev_edge_map, get(m_rev_edge_map, *ei)) == *ei' failed.
Can anyone see what is wrong? It is not clear from the documentation exactly what the vector of reverse edges is supposed to look like - is it supposed to be the same length as the number of edges in the graph? Or half that length?