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::BlankLineo; ;[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" t4' } ;TI" 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"OSIAM Journal on Computing, 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[i0o;;[;0;0[@›@›cRDoc::TopLevel