c++ - boost::boykov_kolmogorov_max_flow 的反向边缘图

Question

我正在尝试使用 boost::boykov_kolmogorov_max_flow 使用标准技术对图像进行分割，该技术从图像上的网格图开始，然后添加每个网格顶点都连接到的“特殊”源节点和汇节点。

我为 2x2 图像(总共 2*2 + 2 = 6 个节点)构造了这个图来表示最基本的情况，只是为了尝试让 Boost 类型达成一致。我想出了这个:

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

它编译，但在运行时我得到:

Assertion `get(m_rev_edge_map, get(m_rev_edge_map, *ei)) == *ei' failed.

谁能看出哪里出了问题？从文档中不清楚反向边的 vector 到底应该是什么样子——它的长度是否应该与图中的边数相同？还是一半的长度？

Answer 1

看来你必须手动指定边缘索引。这是 AddBidirectionalEdge 的修改版本，它可以正确构建反向边缘图，并正确设置边缘索引。

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