부스트 그래프에서 가장자리를 임시로 제거

Question

필자는 (일종의) '토폴로지 정렬'(정확한 것은 아님)을 수행하는 알고리즘을 작성했습니다. 이 알고리즘은 주어진 그래프를 복사 한 다음 복사본을 조작합니다 (가장자리 제거). 백만 노드 노드 증가 그래프에서 알고리즘에 3.1 초가 걸리면 주어진 그래프를 새로운 그래프로 복사하여 2.19 초가 소비됩니다.

가장자리를 실제로 제거하지 않고 제거 할 수 있습니까? 부스트 :: 그래프 라이브러리에서 마스킹의 일종? 그리고 알고리즘이 완료되면, 그래프의 원래 상태를 다시 얻는 모든 에지의 마스크를 해제합니다. 나는 이것이 나의 알고리즘이 훨씬 빨리 움직여야한다고 생각한다.

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

}