lib/tsort.rb

   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