boost-graph - 从提升图中临时移除边

Question

我写了一个算法，它（某种）“拓扑排序”（不精确）。该算法复制给定的图，然后操作副本（通过删除边）。在百万节点提升图上，如果我的算法需要 3.1 秒，则将给定图复制到新图会消耗 2.19 秒。

我可以删除边缘而不实际永久删除它们，例如 boost::graph 库中的某种掩蔽吗？算法完成后，我取消屏蔽所有边，图恢复其原始状态。我怀疑这应该使我的算法运行得更快。

Answer 1

Boost.Graphfiltered_graph似乎非常适合您想要的。不幸的是，我真的不知道它是否会比您当前的方法表现更好（我怀疑它会）。如果您决定实施这种方法，我很想听听结果。

LWS 上的示例。

#include <iostream>
#include <tuple>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/topological_sort.hpp>

#include <boost/unordered_set.hpp>

struct Vertex
{
   Vertex(){}
   Vertex(int val):name(val){}
   int name;
};

typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::directedS,Vertex> graph_type;

typedef boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<graph_type>::edge_descriptor edge_descriptor;

// A hash function for edges.
struct edge_hash:std::unary_function<edge_descriptor, std::size_t> 
{
    edge_hash(graph_type const& g):g(g){}

    std::size_t operator()(edge_descriptor const& e) const {
    std::size_t seed = 0;
    boost::hash_combine(seed, source(e,g));
    boost::hash_combine(seed, target(e,g));
    //if you don't use vecS as your VertexList container
    //you will need to create and initialize a vertex_index property and then use:
    //boost::hash_combine(seed,get(boost::vertex_index, g, source(e,g)));
    //boost::hash_combine(seed,get(boost::vertex_index, g, target(e,g)));
    return seed;
  }

  graph_type const& g;
};

typedef boost::unordered_set<edge_descriptor, edge_hash> edge_set;
typedef boost::filtered_graph<graph_type,boost::is_not_in_subset<edge_set> > filtered_graph_type;

template <typename Graph>
void print_topological_order(Graph const& g)
{
   std::vector<vertex_descriptor> output;
   topological_sort(g,std::back_inserter(output));
   std::vector<vertex_descriptor>::reverse_iterator iter=output.rbegin(),end=output.rend();
   for(;iter!=end;++iter)
      std::cout << g[*iter].name << " ";
   std::cout << std::endl;
}


int main()
{
   graph_type g;

   //BUILD THE GRAPH
   vertex_descriptor v0 = add_vertex(0,g);
   vertex_descriptor v1 = add_vertex(1,g);
   vertex_descriptor v2 = add_vertex(2,g);
   vertex_descriptor v3 = add_vertex(3,g);
   vertex_descriptor v4 = add_vertex(4,g);
   vertex_descriptor v5 = add_vertex(5,g);

   edge_descriptor e4,e5;
   add_edge(v0,v1,g);
   add_edge(v0,v3,g);
   add_edge(v2,v4,g);
   add_edge(v1,v4,g);
   std::tie(e4,std::ignore) = add_edge(v4,v3,g);
   std::tie(e5,std::ignore) = add_edge(v2,v5,g);
   //GRAPH BUILT

   std::cout << "Original graph:" << std::endl;
   print_topological_order(g);


   edge_hash hasher(g);
   edge_set removed(0,hasher); //need to pass "hasher" in the constructor since it is not default constructible

   filtered_graph_type fg(g,removed); //creates the filtered graph

   removed.insert(e4); //you can "remove" edges from the graph by adding them to this set
   removed.insert(e5);   

   std::cout << "Filtered Graph after \"removing\" 2 edges" << std::endl;
   print_topological_order(fg);

   removed.clear(); //clearing the set restores your original graph

   std::cout << "Filtered Graph after resetting" << std::endl;
   print_topological_order(fg);

}