Re: Misclassification of packages; "libs" and "doc" sections
Daniel Burrows wrote:
>
> > 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 display graphs on character terminals, too. But I don't think
it would be really needed as a tree view to a graph can be supplied.
[But it isn't not what you've been talking about :) ]
> 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)
Daniel, a graph doesn't have a root node. There is
no root node to start with. Child is a wrong term. You've
almost written an algorithm that appends an edge to an
existing graph. But of course it's quite wrong even if
you compensate for the fact that graphs don't have roots.
Are you sure you know what a graph is, and an adjacency
list representation is? To make this algorithm correct
remove the root thing, and add an update for the list of
adjacency lists (that is vertex). Vertex labels have to
be unique for such an algorithm to work (since there's
no such thing as a root).
Even if you corrected this algorithm, you've got the wrong
point here :/
> 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 :)
Okay, I'm talking about multiple inheritance from the start. The
two examples I had deliberately demonstrated that!
How many supercategories does Graphical_Debugger category have here?
(this is the first example I gave)
X11_Client Development_Tool
\ /
\ /
Graphical_Debugger
/ \
/ \
[DDD] [xxgdb]
Answer: 2
How many categories does Graphical_Debugger have in the other
example? :P Check it out for yourself.
Note that sections can have multiple outgoing edges, and
multiple incoming edges. That's what multiple inheritance is all
about.
> I still think a tree is a decent way of realizing the graph for display
> to the user.
>
Right. You can view a graph with a pseudo-tree, that is much
larger than the graph itself. If the user traverses it interactively
as in a typical tree view component, it would feel quite comfortable.
> 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.
>
Okay, what would happen when you want to extend the hierarchy?
Modify all packages that happen to be referring to that part
of the hierarchy? Let me put it this way: packages are like
classes in an OO language. When you modify superclasses' inheritance
relationships, you don't have to change the class, too.
> Or you could have each node explicitly list its children, which seems
> cumbersome and non-extensible to me.
>
That's how a graph is done. For each vertex, you just
list the vertices that are adjacent to it (adjacency list rep.)
And that happens to be the most extensible representation of a graph.
> > 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 isn't clearer. Do you list all the class hierarchy above your
class when you write a new class in an OO language? Please.
The thing is this hierarchy should be external to packages. Just
like the fact that sections have been defined "outside" packages.
Packages merely refer to those sections.
> 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... :-\ )
No, a tree where leaf-nodes can appear in multiple places
is not a graph. It is just what you say. A graph G=(V,E)
is a set of vertices V and a map E:V->V If you think about
it you'll see that it is a more general structure than a tree.
> 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.
>
This is true, except that a graph is not what you
seem to think. And the way you've thought about
representing a tree is not quite right.
A category hierarchy exists outside package definitions.
Packages declare "is-a" relationships to only the most
specific categories which they belong to.
Package: xmms
Section: <same as before>
Category: mp3_player, cd_player, gtk_proggy
(this is just an example, it doesn't have to be precise)
That's it. The problem with this approach is that you've
got to append these lines to every package out there. Which
is almost an impossible task, plus you have to change
a lot of low level code, etc. Dirty job.
Instead the Category: line you see above should be defined
outside as well. Preferably all of them packed together
in a package of its own. What do you think?
Thanks,
--
Eray (exa) Ozkural
Comp. Sci. Dept., Bilkent University, Ankara
e-mail: erayo@cs.bilkent.edu.tr
www: http://www.cs.bilkent.edu.tr/~erayo
Reply to: