Reverse edge map for boost::boykov_kolmogorov_max_flow

Question

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?

Answer 1

It seems that you have to specify the edge index manually. Here is a modified version of AddBidirectionalEdge that correctly constructs the reverse edge map, as well as correctly sets the edge indices.

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'
        int nextEdgeId = num_edges(graph);

        EdgeDescriptor edge;
        bool inserted;

        boost::tie(edge,inserted) = add_edge(source, target, nextEdgeId, graph);
        if(!inserted)
        {
            std::cerr << "Not inserted!" << std::endl;
        }
        EdgeDescriptor reverseEdge = add_edge(target, source, nextEdgeId + 1, graph).first;
        reverseEdges.push_back(reverseEdge);
        reverseEdges.push_back(edge);
        capacity.push_back(weight);
        capacity.push_back(weight);
    }