暫時從升壓圖中刪除邊緣

Question

我已經寫了一種算法，它可以（某種）「拓撲排序」（不精確）。該算法複製給定的圖形，然後操作副本（通過去除邊緣）。在一百萬個節點增強圖上，如果我的算法花費3.1秒，則通過將給定圖複製到新圖上消耗2.19秒。

我是否可以在不實際將其邊緣永久移除的情況下移除邊緣boost :: graph庫中的掩碼類型？當算法完成時，我揭開圖的所有邊，重新獲得原始狀態。我懷疑這應該會讓我的算法運行得更快。

Answer 1

Boost.Graph的filtered_graph似乎很適合你想要的東西。不幸的是，我真的不知道它是否會比目前的方法表現更好（我懷疑它會）。如果你決定實施這種方法，我很樂意聽到結果。

Example on 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); 

}