Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #45629

Topological sort

Show all headers | View raw

A Ruby version which seems to be correct; the ANS Forth versions
will have to be provided by others.

def tsort edges
  leaders = edges.map(&:first).uniq
  followers = edges.flat_map{|x| x.drop(1)}.uniq
  visited = []
  ordering = []
  packs =
    leaders.map{|leader|
      [leader] +
        edges.flat_map{|edge| leader==edge[0] ? edge.drop(1) : []}}
  dfs = lambda{|v|
    visited.unshift(v)
    pack = packs.assoc(v)
    if pack
      pack.drop(1).each{|n| dfs[n] unless visited.include?(n)}
    end
    ordering.unshift(v)}
  (leaders - followers).each{|x| dfs[x]}
  ordering
end

tsort [[:the,:issue],[:not,:trying],[:confuse,:the],[:am,:trying],[:trying,:to],
 [:am,:not],[:trying,:the],[:to,:confuse],[:i,:am]]

 ===>
[:i, :am, :not, :trying, :to, :confuse, :the, :issue]


tsort [[:shirt,:tie,:belt],[:tie,:jacket],[:belt,:jacket],[:watch],
  [:pants,:shoes,:belt],[:undershorts,:pants,:shoes],[:socks,:shoes]]

 ===>
[:socks, :undershorts, :pants, :shoes, :watch, :shirt, :belt, :tie, :jacket]


-- 
Man is a social animal just like ants or bees or wolves.  All have their living
space, which they defend to the very end.
http://www.kolumbus.fi/aquilon/aquilon_quot1.htm

Back to comp.lang.forth | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Topological sort "WJ" <w_a_x_man@yahoo.com> - 2016-02-19 21:11 +0000
  Re: Topological sort lehs <skydda.barnen@gmail.com> - 2016-02-19 23:41 -0800
    Re: Topological sort lehs <skydda.barnen@gmail.com> - 2016-02-20 01:00 -0800
    Re: Topological sort anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-20 11:13 +0000
      Re: Topological sort lehs <skydda.barnen@gmail.com> - 2016-02-20 10:39 -0800
      Rosettacode topological sort (was: Topological sort) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-22 07:54 +0000
        Re: Rosettacode topological sort (was: Topological sort) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-22 10:04 +0000
          Re: Rosettacode topological sort (was: Topological sort) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-22 12:26 +0000
            Re: Rosettacode topological sort (was: Topological sort) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-22 13:28 +0000
    Re: Topological sort lehs <skydda.barnen@gmail.com> - 2016-02-23 01:12 -0800
    Re: Topological sort lehs <skydda.barnen@gmail.com> - 2016-02-23 10:56 -0800

csiph-web