13: def condensation_graph
14: raise NotDirectedError,
15: "condensation_graph only supported for directed graphs" unless directed?
16:
17:
18: comp_map = strongly_connected_components.comp_map
19:
20:
21:
22:
23: inv_comp_map = {}
24: comp_map.each { |v, n| (inv_comp_map[n] ||= Set.new) << v }
25:
26:
27:
28:
29: ImplicitGraph.new do |g|
30: g.vertex_iterator do |b|
31: inv_comp_map.each_value(&b)
32: end
33: g.adjacent_iterator do |scc, b|
34: scc.each do |v|
35: each_adjacent(v) do |w|
36:
37: if comp_map[v] != comp_map[w] then
38: b.call(inv_comp_map[comp_map[w]])
39: end
40: end
41: end
42: end
43: g.directed = true
44: end
45: end