1 | #!/usr/bin/env ruby
|
---|
2 | #--
|
---|
3 | # tsort.rb - provides a module for topological sorting and strongly connected components.
|
---|
4 | #++
|
---|
5 | #
|
---|
6 |
|
---|
7 | #
|
---|
8 | # TSort implements topological sorting using Tarjan's algorithm for
|
---|
9 | # strongly connected components.
|
---|
10 | #
|
---|
11 | # TSort is designed to be able to be used with any object which can be
|
---|
12 | # interpreted as a directed graph.
|
---|
13 | #
|
---|
14 | # TSort requires two methods to interpret an object as a graph,
|
---|
15 | # tsort_each_node and tsort_each_child.
|
---|
16 | #
|
---|
17 | # * tsort_each_node is used to iterate for all nodes over a graph.
|
---|
18 | # * tsort_each_child is used to iterate for child nodes of a given node.
|
---|
19 | #
|
---|
20 | # The equality of nodes are defined by eql? and hash since
|
---|
21 | # TSort uses Hash internally.
|
---|
22 | #
|
---|
23 | # == A Simple Example
|
---|
24 | #
|
---|
25 | # The following example demonstrates how to mix the TSort module into an
|
---|
26 | # existing class (in this case, Hash). Here, we're treating each key in
|
---|
27 | # the hash as a node in the graph, and so we simply alias the required
|
---|
28 | # #tsort_each_node method to Hash's #each_key method. For each key in the
|
---|
29 | # hash, the associated value is an array of the node's child nodes. This
|
---|
30 | # choice in turn leads to our implementation of the required #tsort_each_child
|
---|
31 | # method, which fetches the array of child nodes and then iterates over that
|
---|
32 | # array using the user-supplied block.
|
---|
33 | #
|
---|
34 | # require 'tsort'
|
---|
35 | #
|
---|
36 | # class Hash
|
---|
37 | # include TSort
|
---|
38 | # alias tsort_each_node each_key
|
---|
39 | # def tsort_each_child(node, &block)
|
---|
40 | # fetch(node).each(&block)
|
---|
41 | # end
|
---|
42 | # end
|
---|
43 | #
|
---|
44 | # {1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
|
---|
45 | # #=> [3, 2, 1, 4]
|
---|
46 | #
|
---|
47 | # {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components
|
---|
48 | # #=> [[4], [2, 3], [1]]
|
---|
49 | #
|
---|
50 | # == A More Realistic Example
|
---|
51 | #
|
---|
52 | # A very simple `make' like tool can be implemented as follows:
|
---|
53 | #
|
---|
54 | # require 'tsort'
|
---|
55 | #
|
---|
56 | # class Make
|
---|
57 | # def initialize
|
---|
58 | # @dep = {}
|
---|
59 | # @dep.default = []
|
---|
60 | # end
|
---|
61 | #
|
---|
62 | # def rule(outputs, inputs=[], &block)
|
---|
63 | # triple = [outputs, inputs, block]
|
---|
64 | # outputs.each {|f| @dep[f] = [triple]}
|
---|
65 | # @dep[triple] = inputs
|
---|
66 | # end
|
---|
67 | #
|
---|
68 | # def build(target)
|
---|
69 | # each_strongly_connected_component_from(target) {|ns|
|
---|
70 | # if ns.length != 1
|
---|
71 | # fs = ns.delete_if {|n| Array === n}
|
---|
72 | # raise TSort::Cyclic.new("cyclic dependencies: #{fs.join ', '}")
|
---|
73 | # end
|
---|
74 | # n = ns.first
|
---|
75 | # if Array === n
|
---|
76 | # outputs, inputs, block = n
|
---|
77 | # inputs_time = inputs.map {|f| File.mtime f}.max
|
---|
78 | # begin
|
---|
79 | # outputs_time = outputs.map {|f| File.mtime f}.min
|
---|
80 | # rescue Errno::ENOENT
|
---|
81 | # outputs_time = nil
|
---|
82 | # end
|
---|
83 | # if outputs_time == nil ||
|
---|
84 | # inputs_time != nil && outputs_time <= inputs_time
|
---|
85 | # sleep 1 if inputs_time != nil && inputs_time.to_i == Time.now.to_i
|
---|
86 | # block.call
|
---|
87 | # end
|
---|
88 | # end
|
---|
89 | # }
|
---|
90 | # end
|
---|
91 | #
|
---|
92 | # def tsort_each_child(node, &block)
|
---|
93 | # @dep[node].each(&block)
|
---|
94 | # end
|
---|
95 | # include TSort
|
---|
96 | # end
|
---|
97 | #
|
---|
98 | # def command(arg)
|
---|
99 | # print arg, "\n"
|
---|
100 | # system arg
|
---|
101 | # end
|
---|
102 | #
|
---|
103 | # m = Make.new
|
---|
104 | # m.rule(%w[t1]) { command 'date > t1' }
|
---|
105 | # m.rule(%w[t2]) { command 'date > t2' }
|
---|
106 | # m.rule(%w[t3]) { command 'date > t3' }
|
---|
107 | # m.rule(%w[t4], %w[t1 t3]) { command 'cat t1 t3 > t4' }
|
---|
108 | # m.rule(%w[t5], %w[t4 t2]) { command 'cat t4 t2 > t5' }
|
---|
109 | # m.build('t5')
|
---|
110 | #
|
---|
111 | # == Bugs
|
---|
112 | #
|
---|
113 | # * 'tsort.rb' is wrong name because this library uses
|
---|
114 | # Tarjan's algorithm for strongly connected components.
|
---|
115 | # Although 'strongly_connected_components.rb' is correct but too long.
|
---|
116 | #
|
---|
117 | # == References
|
---|
118 | #
|
---|
119 | # R. E. Tarjan, "Depth First Search and Linear Graph Algorithms",
|
---|
120 | # <em>SIAM Journal on Computing</em>, Vol. 1, No. 2, pp. 146-160, June 1972.
|
---|
121 | #
|
---|
122 |
|
---|
123 | module TSort
|
---|
124 | class Cyclic < StandardError
|
---|
125 | end
|
---|
126 |
|
---|
127 | #
|
---|
128 | # Returns a topologically sorted array of nodes.
|
---|
129 | # The array is sorted from children to parents, i.e.
|
---|
130 | # the first element has no child and the last node has no parent.
|
---|
131 | #
|
---|
132 | # If there is a cycle, TSort::Cyclic is raised.
|
---|
133 | #
|
---|
134 | def tsort
|
---|
135 | result = []
|
---|
136 | tsort_each {|element| result << element}
|
---|
137 | result
|
---|
138 | end
|
---|
139 |
|
---|
140 | #
|
---|
141 | # The iterator version of the #tsort method.
|
---|
142 | # <tt><em>obj</em>.tsort_each</tt> is similar to <tt><em>obj</em>.tsort.each</tt>, but
|
---|
143 | # modification of _obj_ during the iteration may lead to unexpected results.
|
---|
144 | #
|
---|
145 | # #tsort_each returns +nil+.
|
---|
146 | # If there is a cycle, TSort::Cyclic is raised.
|
---|
147 | #
|
---|
148 | def tsort_each # :yields: node
|
---|
149 | each_strongly_connected_component {|component|
|
---|
150 | if component.size == 1
|
---|
151 | yield component.first
|
---|
152 | else
|
---|
153 | raise Cyclic.new("topological sort failed: #{component.inspect}")
|
---|
154 | end
|
---|
155 | }
|
---|
156 | end
|
---|
157 |
|
---|
158 | #
|
---|
159 | # Returns strongly connected components as an array of arrays of nodes.
|
---|
160 | # The array is sorted from children to parents.
|
---|
161 | # Each elements of the array represents a strongly connected component.
|
---|
162 | #
|
---|
163 | def strongly_connected_components
|
---|
164 | result = []
|
---|
165 | each_strongly_connected_component {|component| result << component}
|
---|
166 | result
|
---|
167 | end
|
---|
168 |
|
---|
169 | #
|
---|
170 | # The iterator version of the #strongly_connected_components method.
|
---|
171 | # <tt><em>obj</em>.each_strongly_connected_component</tt> is similar to
|
---|
172 | # <tt><em>obj</em>.strongly_connected_components.each</tt>, but
|
---|
173 | # modification of _obj_ during the iteration may lead to unexpected results.
|
---|
174 | #
|
---|
175 | #
|
---|
176 | # #each_strongly_connected_component returns +nil+.
|
---|
177 | #
|
---|
178 | def each_strongly_connected_component # :yields: nodes
|
---|
179 | id_map = {}
|
---|
180 | stack = []
|
---|
181 | tsort_each_node {|node|
|
---|
182 | unless id_map.include? node
|
---|
183 | each_strongly_connected_component_from(node, id_map, stack) {|c|
|
---|
184 | yield c
|
---|
185 | }
|
---|
186 | end
|
---|
187 | }
|
---|
188 | nil
|
---|
189 | end
|
---|
190 |
|
---|
191 | #
|
---|
192 | # Iterates over strongly connected component in the subgraph reachable from
|
---|
193 | # _node_.
|
---|
194 | #
|
---|
195 | # Return value is unspecified.
|
---|
196 | #
|
---|
197 | # #each_strongly_connected_component_from doesn't call #tsort_each_node.
|
---|
198 | #
|
---|
199 | def each_strongly_connected_component_from(node, id_map={}, stack=[]) # :yields: nodes
|
---|
200 | minimum_id = node_id = id_map[node] = id_map.size
|
---|
201 | stack_length = stack.length
|
---|
202 | stack << node
|
---|
203 |
|
---|
204 | tsort_each_child(node) {|child|
|
---|
205 | if id_map.include? child
|
---|
206 | child_id = id_map[child]
|
---|
207 | minimum_id = child_id if child_id && child_id < minimum_id
|
---|
208 | else
|
---|
209 | sub_minimum_id =
|
---|
210 | each_strongly_connected_component_from(child, id_map, stack) {|c|
|
---|
211 | yield c
|
---|
212 | }
|
---|
213 | minimum_id = sub_minimum_id if sub_minimum_id < minimum_id
|
---|
214 | end
|
---|
215 | }
|
---|
216 |
|
---|
217 | if node_id == minimum_id
|
---|
218 | component = stack.slice!(stack_length .. -1)
|
---|
219 | component.each {|n| id_map[n] = nil}
|
---|
220 | yield component
|
---|
221 | end
|
---|
222 |
|
---|
223 | minimum_id
|
---|
224 | end
|
---|
225 |
|
---|
226 | #
|
---|
227 | # Should be implemented by a extended class.
|
---|
228 | #
|
---|
229 | # #tsort_each_node is used to iterate for all nodes over a graph.
|
---|
230 | #
|
---|
231 | def tsort_each_node # :yields: node
|
---|
232 | raise NotImplementedError.new
|
---|
233 | end
|
---|
234 |
|
---|
235 | #
|
---|
236 | # Should be implemented by a extended class.
|
---|
237 | #
|
---|
238 | # #tsort_each_child is used to iterate for child nodes of _node_.
|
---|
239 | #
|
---|
240 | def tsort_each_child(node) # :yields: child
|
---|
241 | raise NotImplementedError.new
|
---|
242 | end
|
---|
243 | end
|
---|
244 |
|
---|
245 | if __FILE__ == $0
|
---|
246 | require 'test/unit'
|
---|
247 |
|
---|
248 | class TSortHash < Hash # :nodoc:
|
---|
249 | include TSort
|
---|
250 | alias tsort_each_node each_key
|
---|
251 | def tsort_each_child(node, &block)
|
---|
252 | fetch(node).each(&block)
|
---|
253 | end
|
---|
254 | end
|
---|
255 |
|
---|
256 | class TSortArray < Array # :nodoc:
|
---|
257 | include TSort
|
---|
258 | alias tsort_each_node each_index
|
---|
259 | def tsort_each_child(node, &block)
|
---|
260 | fetch(node).each(&block)
|
---|
261 | end
|
---|
262 | end
|
---|
263 |
|
---|
264 | class TSortTest < Test::Unit::TestCase # :nodoc:
|
---|
265 | def test_dag
|
---|
266 | h = TSortHash[{1=>[2, 3], 2=>[3], 3=>[]}]
|
---|
267 | assert_equal([3, 2, 1], h.tsort)
|
---|
268 | assert_equal([[3], [2], [1]], h.strongly_connected_components)
|
---|
269 | end
|
---|
270 |
|
---|
271 | def test_cycle
|
---|
272 | h = TSortHash[{1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}]
|
---|
273 | assert_equal([[4], [2, 3], [1]],
|
---|
274 | h.strongly_connected_components.map {|nodes| nodes.sort})
|
---|
275 | assert_raise(TSort::Cyclic) { h.tsort }
|
---|
276 | end
|
---|
277 |
|
---|
278 | def test_array
|
---|
279 | a = TSortArray[[1], [0], [0], [2]]
|
---|
280 | assert_equal([[0, 1], [2], [3]],
|
---|
281 | a.strongly_connected_components.map {|nodes| nodes.sort})
|
---|
282 |
|
---|
283 | a = TSortArray[[], [0]]
|
---|
284 | assert_equal([[0], [1]],
|
---|
285 | a.strongly_connected_components.map {|nodes| nodes.sort})
|
---|
286 | end
|
---|
287 | end
|
---|
288 |
|
---|
289 | end
|
---|
290 |
|
---|