[Axiom-math] address@hidden: Re: [Axiom-developer] RE: dependency visualization with VCG]

[root]

------- Start of forwarded message -------
X-Original-To: address@hidden
X-MessageWall-Score: 0 (mail-gw.bsdwebsolutions.com)
X-MessageWall-Score: 0 (spam-filter-less.bsdwebsolutions.com)
Date: Sat, 30 Aug 2003 11:21:22 -0400
From: William Sit <address@hidden>
Reply-To: address@hidden
Organization: City College of New York
X-Accept-Language: zh,en
To: address@hidden
Cc: address@hidden, address@hidden
Subject: Re: [Axiom-developer] RE: dependency visualization with VCG
Content-Type: text/plain; charset=us-ascii
X-Authentication-Info: Submitted using SMTP AUTH at pop018.verizon.net from 
[162.83.137.57] at Sat, 30 Aug 2003 10:21:35 -0500
X-UIDL: M]d"!<l~!!YXe"!W!h!!

Tim and Bill:

I just got Bill's comments, which I think agrees with my comments below (written
before I read Bill's comments), and are also more practical than the abstract
version I present. My original analysis was an attempt (I am no graph theory
expert) to relate the practical to if you will a mathematical model using known
algorithms from graph theory. This in no way diminishes the accomplishment Tim
and other great hackers have achieved.

William
- ----------

root wrote:
> 
> The linear order exists and is documented in the file
> src/algebra/Lattice.pamphlet. The compiler will tell
> you all of the dependencies at compile time. The subtle
> part is to find the bootstrap set since, in the beginning,
> nothing will compile. That's part of what took so long.
> The other part is that computing the correct location in
> the lattice for all 1100 categories, domains, and packages
> was tedious and time consuming. 

But this is a catch-22 situation. Your problem, however, is to be able to
compile from scratch, even if in order to find the linear order, you have to do
some "test" compiling (or rely on "information" from the NAG compilation -- this
is NOT equivalent to relying on the "compiled object files"). One can use ANY
means to obtain the dependency adjacent list on vertices, including manually
analysing all spad sources, which you probably did.  From that, one can identify
the bootstrap set (the set of roots of out-trees in the components of the
digraphs). I think they are just those vertices with indegree 0. 


> But it's done.

> I believe the lattice can be further optimized but that's
> just an academic exercise. The reason the lattice has to
> exist in any form is that you need to compile from scratch.
> Once that happens the lattice is worthless.

I agree that the lattice can be, and should be, further optimized. It's not just
an academic exercise. Further, I do not agree the lattice is worthless. I know
that "it's done", but each time a full (or even partial) compilation is done, a
more accurate (or up-to-date) dependency adjacent list is found that can feed
the next compilation from scratch. Right now, you have a static library of spad
sources. This is going to become dynamic as more spad sources are added.

> I'd like to see it graphed just so I can stare at the beast
> that ate 8 months of my life.

Your initial great effort is much appreciated. It is part of the "collection of
data" for the dependency digraph. However you did it, you did a fantastic job.
What I was pointing out was that when Bill Page wrote the routine to graph the
dependency digraph, it seems to me he started afresh from the spad sources to
derive the dependency digraph. Isn't it true that you already have the digraph
and you only need to display it visually? I am probably missing something
subtle.

Actually, I just note that the analysis I gave has a small mistake. That is,
even though we obtain a directed forest of out-trees for the digraph, and a
linear order extending each out-tree, it is not the case that the compilation of
any vertex A just depend on what precedes it. (In other words, this property
cannot be satisfied if there are cycles).

There is a further extension of the depth-first search algorithm that computes
what is called the condensation of a digraph. Roughly speaking, the condensation
is an acyclic digraph whose vertices are the strong components of the digraph (a
strong component is a maximally strongly connected sub-digraph where there is a
directed path between any two vertices) and whose arcs reflect the arcs between
strong components. 

It seems the graph you want to see is the condensation and the strong components
of the dependency digraph.

William
------- End of forwarded message -------