etal's blog

How would you contract a graph to its SCC's efficiently?
By etal, 10 years ago, In English

As you know, given a directed graph there are several algorithms that efficiently divide the graph into Strongly Connected Components. Once you have them you can construct a new graph where each vertex corresponds to a SCC and there is a directed edge from u to v iff there exists an edge that goes from a vertex in SCC u to SCC v. Do you know a way to create the adjacency list of this new graph efficiently stored in a vector<vector>?

The only solution I've come up with is doing a vector<set > G and forall edge (a->b) in the old graph inserting comp[b] in G[comp[a]] and once you've done that copy the set into a vector<vector >.

Thank you!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Here is an alternative:

fill(mark, false)
for c in components
  for v in c
    for u in original_edges(v)
      if non mark[comp(u)]
        add_comp_edge(c, comp(u))
      mark[comp(u)] = true

  for v in c
    for u in original_edges(v)
      mark[comp(u)] = false
→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

O(V+E) code

→ Reply