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