1# frozen_string_literal: true 2 3#-- 4# tsort.rb - provides a module for topological sorting and strongly connected components. 5#++ 6# 7 8# 9# TSort implements topological sorting using Tarjan's algorithm for 10# strongly connected components. 11# 12# TSort is designed to be able to be used with any object which can be 13# interpreted as a directed graph. 14# 15# TSort requires two methods to interpret an object as a graph, 16# tsort_each_node and tsort_each_child. 17# 18# * tsort_each_node is used to iterate for all nodes over a graph. 19# * tsort_each_child is used to iterate for child nodes of a given node. 20# 21# The equality of nodes are defined by eql? and hash since 22# TSort uses Hash internally. 23# 24# == A Simple Example 25# 26# The following example demonstrates how to mix the TSort module into an 27# existing class (in this case, Hash). Here, we're treating each key in 28# the hash as a node in the graph, and so we simply alias the required 29# #tsort_each_node method to Hash's #each_key method. For each key in the 30# hash, the associated value is an array of the node's child nodes. This 31# choice in turn leads to our implementation of the required #tsort_each_child 32# method, which fetches the array of child nodes and then iterates over that 33# array using the user-supplied block. 34# 35# require 'tsort' 36# 37# class Hash 38# include TSort 39# alias tsort_each_node each_key 40# def tsort_each_child(node, &block) 41# fetch(node).each(&block) 42# end 43# end 44# 45# {1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort 46# #=> [3, 2, 1, 4] 47# 48# {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components 49# #=> [[4], [2, 3], [1]] 50# 51# == A More Realistic Example 52# 53# A very simple `make' like tool can be implemented as follows: 54# 55# require 'tsort' 56# 57# class Make 58# def initialize 59# @dep = {} 60# @dep.default = [] 61# end 62# 63# def rule(outputs, inputs=[], &block) 64# triple = [outputs, inputs, block] 65# outputs.each {|f| @dep[f] = [triple]} 66# @dep[triple] = inputs 67# end 68# 69# def build(target) 70# each_strongly_connected_component_from(target) {|ns| 71# if ns.length != 1 72# fs = ns.delete_if {|n| Array === n} 73# raise TSort::Cyclic.new("cyclic dependencies: #{fs.join ', '}") 74# end 75# n = ns.first 76# if Array === n 77# outputs, inputs, block = n 78# inputs_time = inputs.map {|f| File.mtime f}.max 79# begin 80# outputs_time = outputs.map {|f| File.mtime f}.min 81# rescue Errno::ENOENT 82# outputs_time = nil 83# end 84# if outputs_time == nil || 85# inputs_time != nil && outputs_time <= inputs_time 86# sleep 1 if inputs_time != nil && inputs_time.to_i == Time.now.to_i 87# block.call 88# end 89# end 90# } 91# end 92# 93# def tsort_each_child(node, &block) 94# @dep[node].each(&block) 95# end 96# include TSort 97# end 98# 99# def command(arg) 100# print arg, "\n" 101# system arg 102# end 103# 104# m = Make.new 105# m.rule(%w[t1]) { command 'date > t1' } 106# m.rule(%w[t2]) { command 'date > t2' } 107# m.rule(%w[t3]) { command 'date > t3' } 108# m.rule(%w[t4], %w[t1 t3]) { command 'cat t1 t3 > t4' } 109# m.rule(%w[t5], %w[t4 t2]) { command 'cat t4 t2 > t5' } 110# m.build('t5') 111# 112# == Bugs 113# 114# * 'tsort.rb' is wrong name because this library uses 115# Tarjan's algorithm for strongly connected components. 116# Although 'strongly_connected_components.rb' is correct but too long. 117# 118# == References 119# 120# R. E. Tarjan, "Depth First Search and Linear Graph Algorithms", 121# <em>SIAM Journal on Computing</em>, Vol. 1, No. 2, pp. 146-160, June 1972. 122# 123 124module TSort 125 class Cyclic < StandardError 126 end 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 # class G 135 # include TSort 136 # def initialize(g) 137 # @g = g 138 # end 139 # def tsort_each_child(n, &b) @g[n].each(&b) end 140 # def tsort_each_node(&b) @g.each_key(&b) end 141 # end 142 # 143 # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) 144 # p graph.tsort #=> [4, 2, 3, 1] 145 # 146 # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) 147 # p graph.tsort # raises TSort::Cyclic 148 # 149 def tsort 150 each_node = method(:tsort_each_node) 151 each_child = method(:tsort_each_child) 152 TSort.tsort(each_node, each_child) 153 end 154 155 # Returns a topologically sorted array of nodes. 156 # The array is sorted from children to parents, i.e. 157 # the first element has no child and the last node has no parent. 158 # 159 # The graph is represented by _each_node_ and _each_child_. 160 # _each_node_ should have +call+ method which yields for each node in the graph. 161 # _each_child_ should have +call+ method which takes a node argument and yields for each child node. 162 # 163 # If there is a cycle, TSort::Cyclic is raised. 164 # 165 # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} 166 # each_node = lambda {|&b| g.each_key(&b) } 167 # each_child = lambda {|n, &b| g[n].each(&b) } 168 # p TSort.tsort(each_node, each_child) #=> [4, 2, 3, 1] 169 # 170 # g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} 171 # each_node = lambda {|&b| g.each_key(&b) } 172 # each_child = lambda {|n, &b| g[n].each(&b) } 173 # p TSort.tsort(each_node, each_child) # raises TSort::Cyclic 174 # 175 def TSort.tsort(each_node, each_child) 176 TSort.tsort_each(each_node, each_child).to_a 177 end 178 179 # The iterator version of the #tsort method. 180 # <tt><em>obj</em>.tsort_each</tt> is similar to <tt><em>obj</em>.tsort.each</tt>, but 181 # modification of _obj_ during the iteration may lead to unexpected results. 182 # 183 # #tsort_each returns +nil+. 184 # If there is a cycle, TSort::Cyclic is raised. 185 # 186 # class G 187 # include TSort 188 # def initialize(g) 189 # @g = g 190 # end 191 # def tsort_each_child(n, &b) @g[n].each(&b) end 192 # def tsort_each_node(&b) @g.each_key(&b) end 193 # end 194 # 195 # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) 196 # graph.tsort_each {|n| p n } 197 # #=> 4 198 # # 2 199 # # 3 200 # # 1 201 # 202 def tsort_each(&block) # :yields: node 203 each_node = method(:tsort_each_node) 204 each_child = method(:tsort_each_child) 205 TSort.tsort_each(each_node, each_child, &block) 206 end 207 208 # The iterator version of the TSort.tsort method. 209 # 210 # The graph is represented by _each_node_ and _each_child_. 211 # _each_node_ should have +call+ method which yields for each node in the graph. 212 # _each_child_ should have +call+ method which takes a node argument and yields for each child node. 213 # 214 # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} 215 # each_node = lambda {|&b| g.each_key(&b) } 216 # each_child = lambda {|n, &b| g[n].each(&b) } 217 # TSort.tsort_each(each_node, each_child) {|n| p n } 218 # #=> 4 219 # # 2 220 # # 3 221 # # 1 222 # 223 def TSort.tsort_each(each_node, each_child) # :yields: node 224 return to_enum(__method__, each_node, each_child) unless block_given? 225 226 TSort.each_strongly_connected_component(each_node, each_child) {|component| 227 if component.size == 1 228 yield component.first 229 else 230 raise Cyclic.new("topological sort failed: #{component.inspect}") 231 end 232 } 233 end 234 235 # Returns strongly connected components as an array of arrays of nodes. 236 # The array is sorted from children to parents. 237 # Each elements of the array represents a strongly connected component. 238 # 239 # class G 240 # include TSort 241 # def initialize(g) 242 # @g = g 243 # end 244 # def tsort_each_child(n, &b) @g[n].each(&b) end 245 # def tsort_each_node(&b) @g.each_key(&b) end 246 # end 247 # 248 # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) 249 # p graph.strongly_connected_components #=> [[4], [2], [3], [1]] 250 # 251 # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) 252 # p graph.strongly_connected_components #=> [[4], [2, 3], [1]] 253 # 254 def strongly_connected_components 255 each_node = method(:tsort_each_node) 256 each_child = method(:tsort_each_child) 257 TSort.strongly_connected_components(each_node, each_child) 258 end 259 260 # Returns strongly connected components as an array of arrays of nodes. 261 # The array is sorted from children to parents. 262 # Each elements of the array represents a strongly connected component. 263 # 264 # The graph is represented by _each_node_ and _each_child_. 265 # _each_node_ should have +call+ method which yields for each node in the graph. 266 # _each_child_ should have +call+ method which takes a node argument and yields for each child node. 267 # 268 # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} 269 # each_node = lambda {|&b| g.each_key(&b) } 270 # each_child = lambda {|n, &b| g[n].each(&b) } 271 # p TSort.strongly_connected_components(each_node, each_child) 272 # #=> [[4], [2], [3], [1]] 273 # 274 # g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} 275 # each_node = lambda {|&b| g.each_key(&b) } 276 # each_child = lambda {|n, &b| g[n].each(&b) } 277 # p TSort.strongly_connected_components(each_node, each_child) 278 # #=> [[4], [2, 3], [1]] 279 # 280 def TSort.strongly_connected_components(each_node, each_child) 281 TSort.each_strongly_connected_component(each_node, each_child).to_a 282 end 283 284 # The iterator version of the #strongly_connected_components method. 285 # <tt><em>obj</em>.each_strongly_connected_component</tt> is similar to 286 # <tt><em>obj</em>.strongly_connected_components.each</tt>, but 287 # modification of _obj_ during the iteration may lead to unexpected results. 288 # 289 # #each_strongly_connected_component returns +nil+. 290 # 291 # class G 292 # include TSort 293 # def initialize(g) 294 # @g = g 295 # end 296 # def tsort_each_child(n, &b) @g[n].each(&b) end 297 # def tsort_each_node(&b) @g.each_key(&b) end 298 # end 299 # 300 # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) 301 # graph.each_strongly_connected_component {|scc| p scc } 302 # #=> [4] 303 # # [2] 304 # # [3] 305 # # [1] 306 # 307 # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) 308 # graph.each_strongly_connected_component {|scc| p scc } 309 # #=> [4] 310 # # [2, 3] 311 # # [1] 312 # 313 def each_strongly_connected_component(&block) # :yields: nodes 314 each_node = method(:tsort_each_node) 315 each_child = method(:tsort_each_child) 316 TSort.each_strongly_connected_component(each_node, each_child, &block) 317 end 318 319 # The iterator version of the TSort.strongly_connected_components method. 320 # 321 # The graph is represented by _each_node_ and _each_child_. 322 # _each_node_ should have +call+ method which yields for each node in the graph. 323 # _each_child_ should have +call+ method which takes a node argument and yields for each child node. 324 # 325 # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} 326 # each_node = lambda {|&b| g.each_key(&b) } 327 # each_child = lambda {|n, &b| g[n].each(&b) } 328 # TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc } 329 # #=> [4] 330 # # [2] 331 # # [3] 332 # # [1] 333 # 334 # g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} 335 # each_node = lambda {|&b| g.each_key(&b) } 336 # each_child = lambda {|n, &b| g[n].each(&b) } 337 # TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc } 338 # #=> [4] 339 # # [2, 3] 340 # # [1] 341 # 342 def TSort.each_strongly_connected_component(each_node, each_child) # :yields: nodes 343 return to_enum(__method__, each_node, each_child) unless block_given? 344 345 id_map = {} 346 stack = [] 347 each_node.call {|node| 348 unless id_map.include? node 349 TSort.each_strongly_connected_component_from(node, each_child, id_map, stack) {|c| 350 yield c 351 } 352 end 353 } 354 nil 355 end 356 357 # Iterates over strongly connected component in the subgraph reachable from 358 # _node_. 359 # 360 # Return value is unspecified. 361 # 362 # #each_strongly_connected_component_from doesn't call #tsort_each_node. 363 # 364 # class G 365 # include TSort 366 # def initialize(g) 367 # @g = g 368 # end 369 # def tsort_each_child(n, &b) @g[n].each(&b) end 370 # def tsort_each_node(&b) @g.each_key(&b) end 371 # end 372 # 373 # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) 374 # graph.each_strongly_connected_component_from(2) {|scc| p scc } 375 # #=> [4] 376 # # [2] 377 # 378 # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) 379 # graph.each_strongly_connected_component_from(2) {|scc| p scc } 380 # #=> [4] 381 # # [2, 3] 382 # 383 def each_strongly_connected_component_from(node, id_map={}, stack=[], &block) # :yields: nodes 384 TSort.each_strongly_connected_component_from(node, method(:tsort_each_child), id_map, stack, &block) 385 end 386 387 # Iterates over strongly connected components in a graph. 388 # The graph is represented by _node_ and _each_child_. 389 # 390 # _node_ is the first node. 391 # _each_child_ should have +call+ method which takes a node argument 392 # and yields for each child node. 393 # 394 # Return value is unspecified. 395 # 396 # #TSort.each_strongly_connected_component_from is a class method and 397 # it doesn't need a class to represent a graph which includes TSort. 398 # 399 # graph = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} 400 # each_child = lambda {|n, &b| graph[n].each(&b) } 401 # TSort.each_strongly_connected_component_from(1, each_child) {|scc| 402 # p scc 403 # } 404 # #=> [4] 405 # # [2, 3] 406 # # [1] 407 # 408 def TSort.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes 409 return to_enum(__method__, node, each_child, id_map, stack) unless block_given? 410 411 minimum_id = node_id = id_map[node] = id_map.size 412 stack_length = stack.length 413 stack << node 414 415 each_child.call(node) {|child| 416 if id_map.include? child 417 child_id = id_map[child] 418 minimum_id = child_id if child_id && child_id < minimum_id 419 else 420 sub_minimum_id = 421 TSort.each_strongly_connected_component_from(child, each_child, id_map, stack) {|c| 422 yield c 423 } 424 minimum_id = sub_minimum_id if sub_minimum_id < minimum_id 425 end 426 } 427 428 if node_id == minimum_id 429 component = stack.slice!(stack_length .. -1) 430 component.each {|n| id_map[n] = nil} 431 yield component 432 end 433 434 minimum_id 435 end 436 437 # Should be implemented by a extended class. 438 # 439 # #tsort_each_node is used to iterate for all nodes over a graph. 440 # 441 def tsort_each_node # :yields: node 442 raise NotImplementedError.new 443 end 444 445 # Should be implemented by a extended class. 446 # 447 # #tsort_each_child is used to iterate for child nodes of _node_. 448 # 449 def tsort_each_child(node) # :yields: child 450 raise NotImplementedError.new 451 end 452end 453