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