Re: [Boost-users] [Graph] how to obtain the complement of a graph?

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-09-16 09:26:22

On Sep 7, 2005, at 1:12 PM, Tzu-Chien Chiu wrote:

> Given a graph G=(V,E) and its complete graph G'=(V,E'), what is the
> shortest code lines to obtain the complement of G_c=(V,E'-E) ?

I can't think of anything better than the obvious algorithm (untested 
code):

void complement_graph(const Graph& g, Graph& gp)
{
   typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
   std::map<vertex_descriptor, vertex_descriptor> vmap;

   BGL_FORALL_VERTICES(v, g, Graph)
     vmap[v] = gp.add_vertex();

   BGL_FORALL_VERTICES(u, g, Graph) {
     std::vector<vertex_descriptor> neighbors(adjacent_vertices(u, 
g).first, adjacent_vertices(u, g).second);
     std::sort(neighbors.begin(), neighbors.end());
     BGL_FORALL_VERTICES(v, g, Graph) {
       // Might want to check for self-loops
       if (!std::binary_search(neighbors.begin(), neighbors.end(), v))
         add_edge(vmap[u], vmap[v], gp);
     }
   }
}

        Doug