From: GOTO Kentaro <gotoken@...>
Date: 2002-09-17T03:33:24+09:00
Subject: Re: Dependency "trees" - suggestions?

At Tue, 17 Sep 2002 02:51:41 +0900,
Shashank Date wrote:
> > This is not really a tree because many packages can depend on one, so
> > a node can have multiple parents.  But it *is* directed and *must* be
> > acyclic.
> 
> So this is a DAG "Directed Acyclic Graph" for which there many algorithms
> available.

FYI: Ruby 1.7.x has tsort.rb as a standard library.  The following
cites the beginning of tsort.rb's embedded document.

----------------------------------------------------------------------
  tsort.rb

    tsort.rb provides a module for topological sorting and strongly
    connected components.

  Example

    require 'tsort'

    class Hash
      include TSort
      alias tsort_each_node each_key
      def tsort_each_child(node, &block)
        fetch(node).each(&block)
      end
    end

    {1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
    #=> [3, 2, 1, 4]

    {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components
    #=> [[4], [2, 3], [1]]

  TSort module

    TSort implements topological sorting using Tarjan's algorithm for
    strongly connected components.

----------------------------------------------------------------------

-- Gotoken