Re: Misclassification of packages; "libs" and "doc" sections

[Daniel Burrows <Daniel_Burrows@brown.edu>]

On Thu, Oct 12, 2000 at 05:12:24AM +0300, Eray Ozkural <erayo@cs.bilkent.edu.tr> was heard to say:
> Daniel Burrows wrote:
> > 
> > > What's GL?
> > 
> >   OpenGL -- the canonical 3d graphics API.
> > 
> 
> Yea, I know :I. I hadn't understood the reference GL [1], I thought
> of it as something else. Wrote a few programs with the old procedural
> lib.

  The [1] was going to be a footnote, but..

> No, I don't think you have to do it 3d. There are a lot of
> high quality 2d graph layout algorithms. One of the faculty members
> here has a Phd in graph layout so we don't have any difficulty in
> that. (if we have to display graphs, I mean)

  How well do his algorithms work in character terminals? :)

  (or: "how easy are they to implement"..)

> >   You can infer this from the above specification.  For instance,
> > here emacs20 could be defined as:
> > 
> > Packages: emacs20
> > .
> > .
> > .
> > Sections: Kitchen_Sink, Development_Tool/Interpreter/Lisp_Interpreter, etc
> 
> I'm not talking about packages having multiple sections. But if
> you represent sections like that your hierarchy becomes a tree. 
> Please look carefully, what I depicted is not a tree (in a tree
> there is a unique path from every node to a special node called
> the root). Arrrgh.

  I wasn't saying that it was a tree.  Here's an algorithm for constructing
a graph given the above input format.

For each package:
  For each section entry:
    Let "CURRENT" be the root node.
    For each '/'-separated component:
      If a node with this name is a child of CURRENT:
        CURRENT = that node.
      Else:
        Create a new section-node, entered into CURRENT's child list
	under that name.
	CURRENT = that node.
    Append a pointer to the current package to CURRENT's child list.

  ("child" could be a different term depending on how you're looking
   at the graph..basically, nodes immediately reachable from the given node)

> That Development_Tool/Interpreter/Lisp_Interpreter thing implies
> that the hierarchy is just a tree. Since paths are unique in trees
> you can use a path to refer to nodes where node labels aren't unique.

  But because the graph is acyclic (and, as I see it, sections only have
one parent), we can construct several paths from the root to the leaf node
in question and use those to identify its location.  It might not be
standard, but it seemed logical at the time I thought of it :)
  I still think a tree is a decent way of realizing the graph for display
to the user.

  You could also do something like:
Section: Development_Tool
Parents: <ROOT>

Section: Interpreter
Parents: Development_Tool

Section: Lisp_Interpreter
Parents: Interpreter

Package: emacs20
.
.
.
Parents: Kitchen_Sink, Lisp_Interpreter

  -- which would allow sections to have multiple parents if you felt like it.

  Or you could have each node explicitly list its children, which seems
cumbersome and non-extensible to me.

> In a graph, it isn't a usual practice to refer to nodes by
> paths. You use only the label which is unique.

  ..but would it make sense for a configuration/definition file?  It seems to
me that explicitly listing all the places a package can appear is clearer,
unless you want the effect that sections/subsections can easily be moved around.
(I'm not particularly strongly attached to either mechanism; I took the
 "multiple-sections" approach just because it's closer to our current syntax)

> >   It's pretty easy to look up the correct section and stick it in..
> 
> Go and try to do it without representing a graph!
> 
> So: No! emacs20 can't be defined like that!

  See above for the algorithm I was thinking about.  I was really talking
about a graph, I suppose.  Or a tree where leaf-nodes can appear in multiple
places (which I suppose means a graph, I'm not being precise with my
terminology... :-\ )
  I think we have a miscommunication caused by my imprecise terminology?

  In sum, here is how I see it:
  
  The data structure is a graph, as you call it.
  A directed acyclic graph, in fact.
  The UI is a tree.

  Daniel

-- 
/----------------- Daniel Burrows <Daniel_Burrows@brown.edu> -----------------\
|                              The Turtle Moves!                              |
\------------- Debian GNU/Linux http://www.debian.org -- Because. ------------/