1#@!#!123s

��JFIF�� 1#@!#!123s
: / opt / cpanel / ea-ruby24 / root / usr / share / ri / system / TSort /
Filename : cdesc-TSort.ri
back
U:RDoc::NormalModule[iI"
TSort:EF@0o:RDoc::Markup::Document:@parts[o;;[o:RDoc::Markup::Paragraph;[I"GTSort implements topological sorting using Tarjan's algorithm for ;TI"#strongly connected components.;To:RDoc::Markup::BlankLine�o;	;[I"JTSort is designed to be able to be used with any object which can be ;TI"%interpreted as a directed graph.;T@o;	;[I"CTSort requires two methods to interpret an object as a graph, ;TI"*tsort_each_node and tsort_each_child.;T@o:RDoc::Markup::List:
@type:BULLET:@items[o:RDoc::Markup::ListItem:@label0;[o;	;[I"Ctsort_each_node is used to iterate for all nodes over a graph.;To;;0;[o;	;[I"Itsort_each_child is used to iterate for child nodes of a given node.;T@o;	;[I">The equality of nodes are defined by eql? and hash since ;TI" TSort uses Hash internally.;T@S:RDoc::Markup::Heading:
leveli:	textI"A Simple Example;T@o;	;[
I"LThe following example demonstrates how to mix the TSort module into an ;TI"Kexisting class (in this case, Hash). Here, we're treating each key in ;TI"Jthe hash as a node in the graph, and so we simply alias the required ;TI"M#tsort_each_node method to Hash's #each_key method. For each key in the ;TI"Lhash, the associated value is an array of the node's child nodes. This ;TI"Rchoice in turn leads to our implementation of the required #tsort_each_child ;TI"Pmethod, which fetches the array of child nodes and then iterates over that ;TI")array using the user-supplied block.;T@o:RDoc::Markup::Verbatim;[I"require 'tsort'
;TI"
;TI"class Hash
;TI"  include TSort
;TI"&  alias tsort_each_node each_key
;TI"*  def tsort_each_child(node, &block)
;TI""    fetch(node).each(&block)
;TI"  end
;TI"	end
;TI"
;TI"-{1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
;TI"#=> [3, 2, 1, 4]
;TI"
;TI"F{1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components
;TI"#=> [[4], [2, 3], [1]]
;T:@format0S;;i;I"A More Realistic Example;T@o;	;[I"BA very simple `make' like tool can be implemented as follows:;T@o;;[=I"require 'tsort'
;TI"
;TI"class Make
;TI"  def initialize
;TI"    @dep = {}
;TI"    @dep.default = []
;TI"  end
;TI"
;TI",  def rule(outputs, inputs=[], &block)
;TI"+    triple = [outputs, inputs, block]
;TI"/    outputs.each {|f| @dep[f] = [triple]}
;TI"    @dep[triple] = inputs
;TI"  end
;TI"
;TI"  def build(target)
;TI">    each_strongly_connected_component_from(target) {|ns|
;TI"      if ns.length != 1
;TI"1        fs = ns.delete_if {|n| Array === n}
;TI"M        raise TSort::Cyclic.new("cyclic dependencies: #{fs.join ', '}")
;TI"      end
;TI"      n = ns.first
;TI"      if Array === n
;TI"(        outputs, inputs, block = n
;TI"=        inputs_time = inputs.map {|f| File.mtime f}.max
;TI"        begin
;TI"A          outputs_time = outputs.map {|f| File.mtime f}.min
;TI""        rescue Errno::ENOENT
;TI""          outputs_time = nil
;TI"        end
;TI"'        if outputs_time == nil ||
;TI"B           inputs_time != nil && outputs_time <= inputs_time
;TI"R          sleep 1 if inputs_time != nil && inputs_time.to_i == Time.now.to_i
;TI"          block.call
;TI"        end
;TI"      end
;TI"    }
;TI"  end
;TI"
;TI"*  def tsort_each_child(node, &block)
;TI"!    @dep[node].each(&block)
;TI"  end
;TI"  include TSort
;TI"	end
;TI"
;TI"def command(arg)
;TI"  print arg, "\n"
;TI"  system arg
;TI"	end
;TI"
;TI"m = Make.new
;TI",m.rule(%w[t1]) { command 'date > t1' }
;TI",m.rule(%w[t2]) { command 'date > t2' }
;TI",m.rule(%w[t3]) { command 'date > t3' }
;TI"<m.rule(%w[t4], %w[t1 t3]) { command 'cat t1 t3 > t4' }
;TI"<m.rule(%w[t5], %w[t4 t2]) { command 'cat t4 t2 > t5' }
;TI"m.build('t5')
;T;0S;;i;I"	Bugs;T@o;;;
;[o;;0;[o;	;[I"8'tsort.rb' is wrong name because this library uses ;TI";Tarjan's algorithm for strongly connected components. ;TI"IAlthough 'strongly_connected_components.rb' is correct but too long.;T@S;;i;I"References;T@o;;:UALPHA;[o;;0;[o;;;;[o;;0;[o;	;[I">Tarjan, "Depth First Search and Linear Graph Algorithms",;To;	;[I"O<em>SIAM Journal on Computing</em>, Vol. 1, No. 2, pp. 146-160, June 1972.;T:
@fileI"lib/tsort.rb;T:0@omit_headings_from_table_of_contents_below0;0;0[�[�[�[[I"
class;T[[:public[
[I"&each_strongly_connected_component;FI"lib/tsort.rb;T[I"+each_strongly_connected_component_from;F@�[I""strongly_connected_components;F@�[I"
tsort;F@�[I"tsort_each;F@�[:protected[�[:private[�[I"
instance;T[[;[[I"&each_strongly_connected_component;F@�[I"+each_strongly_connected_component_from;F@�[I""strongly_connected_components;F@�[I"
tsort;F@�[I"tsort_each;F@�[I"tsort_each_child;F@�[I"tsort_each_node;F@�[;[�[;[�[�[U:RDoc::Context::Section[i�0o;;[�;0;0[@�@�cRDoc::TopLevel