CODEWITHSUNDEEP
boost-graph
Dilawar
Dilawar

Reputation: 5645

Removing edges temporarily from a boost graph

I have written an algorithm which does (some sort of) 'topological sorting' (not exact). This algorithm copies the given graph and then manipulates the copy (by removing edges). On a million node boost graph, if my algorithm takes 3.1 seconds, 2.19 seconds are consumed by copying the given graph into a new one.

Can I remove edges without actually removing them permanently e.g. sort of masking in boost::graph library? And when algorithm is done, I unmask all edges the graph regains it original state. I suspect this should make my algorithm run much faster.

Upvotes: 1

Views: 847

Answers (1)

user2265413
user2265413

Reputation: 31

Boost.Graph's filtered_graph seems a good fit for what you want. Unfortunately I really have no idea if it will perform better than your current approach (I suspect it will). If you decide to implement this approach I would love to hear about the results.

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

}

Upvotes: 3

Related Questions