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 vmap;
BGL_FORALL_VERTICES(v, g, Graph)
vmap[v] = gp.add_vertex();
BGL_FORALL_VERTICES(u, g, Graph) {
std::vector 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
