# Topological sorting

From comp.compilers

Related articles
| List of all articles for this month |

 From: Vladimir Alexiev Newsgroups: comp.theory,sci.math,comp.compilers Date: 7 Mar 1998 22:31:58 -0500 Organization: University of Alberta, Computing Science Distribution: inet References: 98-03-015 Keywords: theory In-reply-to: Vladimir Alexiev's message of 3 Mar 1998 10:52:15 -0500

I kinda solved my "compacting" series-parallel graphs". First, note
that we start from a fully expanded representation (yacc input is very
simple: a sum/alternative of products/concatenations). Thus we don't
need a full-generality algorithm. My algorithm basically squeezes the
"strands" (sequences) of the alternative starting from the ends, and
going as far towards the center as possible. When it has to stop
because not all strands have the same bead (atom) at the end, it picks
up the matching strands and applies itself recursively to them. If
anyone is interested, I can post the perl function that does this.

The algorithm is incomplete because it won't factor ax|ay|bx|by into
(a|b)(x|y). But I hope nobody will write such a thing in a grammar. If
people write the more sensible
S : AB XY ;
AB: a | b ;
XY: x | y ;
and then instruct my convertor to inline AB and XY, it will come out ok.

Now, can someone help me with another problem: is there a fast
"stable" topological sorting algorithm? I found lots of references on
generating and counting all total extensions of a poset, but no
descriptions of an algorithm that finds a linear extension "closest"
to a given initial total order. Currently I first take the transitive
closure of the partial order (so that I can tell quickly if A<B), then
do bubble-sort, comparing every element to every other.

chris dircks <chrisd@sfu.ca>:
> This is equivalent to minimizing the number of states in a dfa, or
> deterministic finite accepter.

I see that it can be seen as a *N*FA, because two alternatives may
start with the same atom. But why is it the same as minimization?

> You happen to have an excellent resource for questions on graph classes
> right in your department; you can contact Professor Lorna Stewart to

I thought about that but decided that it's not only a graph problem
(as will be seen below), and that Lorna perhaps has enough things on

> use a known trick for storing adjacency matrices without
> initializing them

What does this mean?

> Valdes, Tarjan, Lawler; The Recognition of Series Parallel Digraphs,
> SIAM J Computing 11, 1982, 298-313. One section is devoted to your
> problem, which he calls recognition of ESP (edges series-parallel)
> graphs.

I'll take a look at this. In fact I found some techreports using the
CSTR server, but they all talked about recognition (not
factorization), so that put me off.

Aaron Leon Kaplan <lkaplan@complang.tuwien.ac.at>
> If you are doing that program I think you might be interested in a
> simmilar program "YaccViso" which also displays yacc files
> http://mars.tuwien.ac.at/~jjl

This program produces the dependency graph of the grammar using
dot/vcg. That graph doesn't contain all the info about the grammar. I
may be mistaken though, because it uses record-shape nodes; I haven't
yet looked at the sample output. [The program segfaults for me on
sunos 4.1.4]

I think I'll add a dot backend to my script too. If all the info from
the grammar is to be present, then factorization and loopization are
in order.

Carl Sturtivant <carl@bitstream.net>
> It seems to me that this is equivalent to the problem of minimizing the
> size of an algebraic expression with addition and non-commutative
> multiplication... the literature on algorithms for algebra systems
> may provide a rich source of possibilities. Mathematica, Maple,
> Macsyma, etc.

I realized this and I even spent a couple of hours digging through
Maple, trying to find some reusable libraries or algorithm
descriptions. Then I figured that it will take me more time to dig it
out (having no experience with symbolic math systems) than to reinvent
it.
[For topological sort, there's a straightforward O(N) algorithm in
Knuth Vol 1. -John]

--

Post a followup to this message