# 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