Interpreting boykov_kolmogorov_max_flow min-cut groups

Question

I am trying to use boost::boykov_kolmogorov_max_flow for foreground/background image segmentation. 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'
    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);
}

int main()
{
  GraphType graph;

  unsigned int numberOfVertices = 3*3 + 2; // a 3x3 grid plus the source and sink terminals
  std::vector<int> groups(numberOfVertices);

  std::vector<EdgeDescriptor> reverseEdges;

  std::vector<float> capacity;

  /*
   0 - 1 = 2
   |   ||  |
   3 - 4 - 5
   |   ||  |
   6 = 7 - 8
   */
  float smallWeight = 1;
  float largeWeight = 1000;

  // Horizontal edges
  AddBidirectionalEdge(graph, 0, 1, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 1, 2, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 3, 4, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 4, 5, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 6, 7, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 7, 8, smallWeight, reverseEdges, capacity);

  // Vertical edges
  AddBidirectionalEdge(graph, 0, 3, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 3, 6, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 1, 4, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 4, 7, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 2, 5, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 5, 8, smallWeight, reverseEdges, capacity);

  int sourceId = 9;
  int sinkId = 10;
  // Add links to terminals for uncertain nodes
  std::vector<unsigned int> uncertainNodes = {{2, 4, 7, 6}};
  for(size_t i = 0; i < uncertainNodes.size(); ++i)
  {
      AddBidirectionalEdge(graph, uncertainNodes[i], sourceId, 1, reverseEdges, capacity);
      AddBidirectionalEdge(graph, uncertainNodes[i], sinkId, 1, reverseEdges, capacity);
  }

  // Add links to terminals for "definitely source"
  std::vector<unsigned int> sourceNodes = {{0, 3}};
  for(size_t i = 0; i < sourceNodes.size(); ++i)
  {
      AddBidirectionalEdge(graph, sourceNodes[i], sourceId, largeWeight, reverseEdges, capacity);
      AddBidirectionalEdge(graph, sourceNodes[i], sinkId, smallWeight, reverseEdges, capacity);
  }

  // Add links to terminals for "definitely sink"
  std::vector<unsigned int> sinkNodes = {{5, 8}};
  for(size_t i = 0; i < sinkNodes.size(); ++i)
  {
      AddBidirectionalEdge(graph, sinkNodes[i], sourceId, smallWeight, reverseEdges, capacity);
      AddBidirectionalEdge(graph, sinkNodes[i], sinkId, largeWeight, reverseEdges, capacity);
  }

  std::vector<float> residual_capacity(num_edges(graph), 0);

  VertexDescriptor sourceVertex = vertex(sourceId,graph);
  VertexDescriptor sinkVertex = vertex(sinkId,graph);

  // There should be 3*3 + 2 = 11 nodes
  std::cout << "Number of vertices " << num_vertices(graph) << std::endl;

  // There should be 2*(12) + 2*2*9 = 60 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;
//  }

  std::cout << "Source group " << groups[sourceVertex] << std::endl;
  std::cout << "Sink group " << groups[sinkVertex] << std::endl;

  for(size_t index=0; index < numberOfVertices - 2; ++index)
  {
    if(groups[index] == groups[sourceVertex])
    {
        std::cout << "Vertex " << index << " is attached to the source. (group " << groups[index] << ")" << std::endl;
    }
    else if(groups[index] == groups[sinkVertex])
    {
        std::cout << "Vertex " << index << " is attached to the sink. (group " << groups[index] << ")" << std::endl;
    }
    else
    {
        std::cerr << "Vertex " << index << " is not attached to the source or sink! (group " <<  groups[index] << ")" << std::endl;
    }
  }

  return EXIT_SUCCESS;
}

which builds and runs with no errors. However, even in this trivially small example, the output seems odd. Here is the output of the above code:

Number of vertices 11
Number of edges 56
Source group label 4
Sink group label 0
Vertex 0 is attached to the source. (group 4)
Vertex 3 is attached to the source. (group 4)
Vertex 5 is attached to the sink. (group 0)
Vertex 8 is attached to the sink. (group 0)
Vertex 1 is not attached to the source or sink! (group 1)
Vertex 2 is not attached to the source or sink! (group 1)
Vertex 4 is not attached to the source or sink! (group 1)
Vertex 6 is not attached to the source or sink! (group 1)
Vertex 7 is not attached to the source or sink! (group 1)

As you can see, there are THREE groups in the output, which are called "0", "1", and "4".

Can anyone explain what the labels mean, and why there are more than 2 groups in the segmentation output?

----- EDIT -----

I made a slightly bigger graph (3x5) where I know for sure that vertex 5 should be connected to the source and vertex 9 should be connected to the sink, and 2, 7, and 12 could be connected to either terminal with equal penalty, but they should all be the same. It seems to work as expected in this case:

#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>

/*
 F F x B B    F F F B B
 x F x B x -> F F F B B
 F F x B B    F F F B B
*/

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'
    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);

    // Not sure what to do about reverse edge weights
    capacity.push_back(weight);
//    capacity.push_back(0);
}

int main()
{
  GraphType graph;

  unsigned int numberOfVertices = 3*5 + 2; // a 3x5 grid plus the source and sink terminals
  std::vector<int> groups(numberOfVertices);

  std::vector<EdgeDescriptor> reverseEdges;

  std::vector<float> capacity;

  float smallWeight = 1;
  float largeWeight = 1000;

  // Horizontal edges
  AddBidirectionalEdge(graph, 0, 1, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 1, 2, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 2, 3, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 3, 4, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 5, 6, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 6, 7, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 7, 8, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 8, 9, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 10, 11, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 11, 12, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 12, 13, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 13, 14, smallWeight, reverseEdges, capacity);

  // Vertical edges
  AddBidirectionalEdge(graph, 0, 5, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 1, 6, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 2, 7, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 3, 8, largeWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 4, 9, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 5, 10, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 6, 11, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 7, 12, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 8, 13, smallWeight, reverseEdges, capacity);
  AddBidirectionalEdge(graph, 9, 14, smallWeight, reverseEdges, capacity);

  int sourceId = 15;
  int sinkId = 16;
  // Add links to terminals for uncertain nodes
  std::vector<unsigned int> uncertainNodes = {{2, 5, 7, 9, 12}};
  for(size_t i = 0; i < uncertainNodes.size(); ++i)
  {
      AddBidirectionalEdge(graph, uncertainNodes[i], sourceId, 1, reverseEdges, capacity);
      AddBidirectionalEdge(graph, uncertainNodes[i], sinkId, 1, reverseEdges, capacity);
  }

  // Add links to terminals for "definitely source"
  std::vector<unsigned int> sourceNodes = {{0, 1, 6, 10, 11}};
  for(size_t i = 0; i < sourceNodes.size(); ++i)
  {
      AddBidirectionalEdge(graph, sourceNodes[i], sourceId, largeWeight, reverseEdges, capacity);
      AddBidirectionalEdge(graph, sourceNodes[i], sinkId, smallWeight, reverseEdges, capacity);
  }

  // Add links to terminals for "definitely sink"
  std::vector<unsigned int> sinkNodes = {{3, 4, 8, 13, 14}};
  for(size_t i = 0; i < sinkNodes.size(); ++i)
  {
      AddBidirectionalEdge(graph, sinkNodes[i], sourceId, smallWeight, reverseEdges, capacity);
      AddBidirectionalEdge(graph, sinkNodes[i], sinkId, largeWeight, reverseEdges, capacity);
  }

  std::vector<float> residual_capacity(num_edges(graph), 0);

  VertexDescriptor sourceVertex = vertex(sourceId,graph);
  VertexDescriptor sinkVertex = vertex(sinkId,graph);

  // There should be 3*5 + 2 = 17 nodes
  std::cout << "Number of vertices " << num_vertices(graph) << std::endl;

  // There should be 2*2*(15) + 2* ((5-1)*3 + 5*(3-1)) = 60 + 2(12 + 10) = 104 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;
//  }

  std::cout << "Source group label " << groups[sourceVertex] << std::endl;
  std::cout << "Sink group label " << groups[sinkVertex] << std::endl;

  //for(size_t index=0; index < numberOfVertices - 2; ++index)
  for(size_t index=0; index < numberOfVertices; ++index)
  {
    if(groups[index] == groups[sourceVertex])
    {
        std::cout << "Vertex " << index << " is attached to the source. (group " << groups[index] << ")" << std::endl;
    }
    else if(groups[index] == groups[sinkVertex])
    {
        std::cout << "Vertex " << index << " is attached to the sink. (group " << groups[index] << ")" << std::endl;
    }
    else
    {
        std::cerr << "Vertex " << index << " is not attached to the source or sink! (group " <<  groups[index] << ")" << std::endl;
    }
  }

  return EXIT_SUCCESS;
}

Output:

Number of vertices 17
Number of edges 104
Source group label 4
Sink group label 0
Vertex 0 is attached to the source. (group 4)
Vertex 1 is attached to the source. (group 4)
Vertex 2 is attached to the source. (group 4)
Vertex 3 is attached to the sink. (group 0)
Vertex 4 is attached to the sink. (group 0)
Vertex 5 is attached to the source. (group 4)
Vertex 6 is attached to the source. (group 4)
Vertex 7 is attached to the source. (group 4)
Vertex 8 is attached to the sink. (group 0)
Vertex 9 is attached to the sink. (group 0)
Vertex 10 is attached to the source. (group 4)
Vertex 11 is attached to the source. (group 4)
Vertex 12 is attached to the source. (group 4)
Vertex 13 is attached to the sink. (group 0)
Vertex 14 is attached to the sink. (group 0)
Vertex 15 is attached to the source. (group 4)
Vertex 16 is attached to the sink. (group 0)

Answer 1

From the boost documentation:

"If the color of a vertex after running the algorithm is black the vertex belongs to the source tree else it belongs to the sink-tree (used for minimum cuts)."(boykov_kolmogorov_max_flow)

I guess you should count those other values as part of the sink-tree set.