# File lib/rgl/transitivity.rb, line 98 98: def transitive_reduction 99: raise NotDirectedError, 100: "transitive_reduction only supported for directed graphs" unless directed? 101: 102: # Compute a condensation graph in order to hide cycles. 103: cg = condensation_graph 104: 105: # Use a depth first search to compute the transitive reduction over the 106: # condensed graph. This is similar to the computation of the transitive 107: # closure over the graph in that for any node of the graph all nodes 108: # reachable from the node are tracked. Using a depth first search ensures 109: # that all nodes reachable from a target node are known when considering 110: # whether or not to add an edge pointing to that target. 111: tr_cg = DirectedAdjacencyGraph.new 112: paths_from = {} 113: cg.depth_first_search do |v| 114: paths_from[v] = Set.new 115: cg.each_adjacent(v) do |w| 116: # Only add the edge v -> w if there is no other edge v -> x such that 117: # w is reachable from x. Make sure to completely skip the case where 118: # x == w. 119: unless Enumerable::Enumerator.new(cg, :each_adjacent, v).any? do |x| 120: x != w && paths_from[x].include?(w) 121: end then 122: tr_cg.add_edge(v, w) 123: 124: # For each vertex v, track all nodes reachable from v by adding node 125: # w to the list as well as all the nodes readable from w. 126: paths_from[v] << w 127: paths_from[v].merge(paths_from[w]) 128: end 129: end 130: # Ensure that a vertex with no in or out edges is added to the graph. 131: tr_cg.add_vertex(v) 132: end 133: 134: # Expand the condensed transitive reduction. 135: # 136: # For each trivial strongly connected component in the condensed graph, 137: # add the single node it contains to the new graph and add edges for each 138: # edge the node begins in the original graph. 139: # For each NON-trivial strongly connected component in the condensed 140: # graph, add each node it contains to the new graph and add arbitrary 141: # edges between the nodes to form a simple cycle. Then for each strongly 142: # connected component adjacent to the current one, find and add the first 143: # edge which exists in the original graph, starts in the first strongly 144: # connected component, and ends in the second strongly connected 145: # component. 146: g = DirectedAdjacencyGraph.new 147: tr_cg.each_vertex do |scc| 148: # Make a cycle of the contents of non-trivial strongly connected 149: # components. 150: scc_arr = scc.to_a 151: if scc.size > 1 || has_edge?(scc_arr.first, scc_arr.first) then 152: 0.upto(scc_arr.size - 2) do |idx| 153: g.add_edge(scc_arr[idx], scc_arr[idx + 1]) 154: end 155: g.add_edge(scc_arr.last, scc_arr.first) 156: end 157: 158: # Choose a single edge between the members of two different strongly 159: # connected component to add to the graph. 160: edges = Enumerable::Enumerator.new(self, :each_edge) 161: tr_cg.each_adjacent(scc) do |scc2| 162: g.add_edge( 163: *edges.find do |v, w| 164: scc.member?(v) && scc2.member?(w) 165: end 166: ) 167: end 168: 169: # Ensure that a vertex with no in or out edges is added to the graph. 170: scc.each do |v| 171: g.add_vertex(v) 172: end 173: end 174: 175: # Finally, the transitive reduction... 176: g 177: end