# File lib/rgl/transitivity.rb, line 19
19:     def transitive_closure
20:       raise NotDirectedError,
21:         "transitive_closure only supported for directed graphs" unless directed?
22: 
23:       # Compute a condensation graph in order to hide cycles.
24:       cg = condensation_graph
25: 
26:       # Use a depth first search to calculate the transitive closure over the
27:       # condensation graph.  This ensures that as we traverse up the graph we
28:       # know the transitive closure of each subgraph rooted at each node
29:       # starting at the leaves.  Subsequent root nodes which consume these
30:       # subgraphs by way of the nodes' immediate successors can then immediately
31:       # add edges to the roots of the subgraphs and to every successor of those
32:       # roots.
33:       tc_cg = DirectedAdjacencyGraph.new
34:       cg.depth_first_search do |v|
35:         # For each vertex v, w, and x where the edges v -> w and w -> x exist in
36:         # the source graph, add edges v -> w and v -> x to the target graph.
37:         cg.each_adjacent(v) do |w|
38:           tc_cg.add_edge(v, w)
39:           tc_cg.each_adjacent(w) do |x|
40:             tc_cg.add_edge(v, x)
41:           end
42:         end
43:         # Ensure that a vertex with no in or out edges is added to the graph.
44:         tc_cg.add_vertex(v)
45:       end
46: 
47:       # Expand the condensed transitive closure.
48:       #
49:       # For each trivial strongly connected component in the condensed graph,
50:       # add the single node it contains to the new graph and add edges for each
51:       # edge the node begins in the original graph.
52:       # For each NON-trivial strongly connected component in the condensed
53:       # graph, add each node it contains to the new graph and add edges to
54:       # every node in the strongly connected component, including self
55:       # referential edges.  Then for each edge of the original graph from any
56:       # of the contained nodes, add edges from each of the contained nodes to
57:       # all the edge targets.
58:       g = DirectedAdjacencyGraph.new
59:       tc_cg.each_vertex do |scc|
60:         scc.each do |v|
61:           # Add edges between all members of non-trivial strongly connected
62:           # components (size > 1) and ensure that self referential edges are
63:           # added when necessary for trivial strongly connected components.
64:           if scc.size > 1 || has_edge?(v, v) then
65:             scc.each do |w|
66:               g.add_edge(v, w)
67:             end
68:           end
69:           # Ensure that a vertex with no in or out edges is added to the graph.
70:           g.add_vertex(v)
71:         end
72:         # Add an edge from every member of a strongly connected component to
73:         # every member of each strongly connected component to which the former
74:         # points.
75:         tc_cg.each_adjacent(scc) do |scc2|
76:           scc.each do |v|
77:             scc2.each do |w|
78:               g.add_edge(v, w)
79:             end
80:           end
81:         end
82:       end
83: 
84:       # Finally, the transitive closure...
85:       g
86:     end