# 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