Re: Misclassification of packages; "libs" and "doc" sections
On Thu, Oct 12, 2000 at 06:57:57AM +0300, Eray Ozkural <erayo@cs.bilkent.edu.tr> was heard to say:
> > 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.
(I should have said, "Or look up a node with that name", although maybe
I'd still be wrong :P)
> > 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?
I thought I mentioned already (did I?) that I haven't taken a class on formal
graph theory yet. I want to, but I haven't fit it in..
So, I'm sure I don't know the formal definition. I've been exposed
to the notion of a graph and an adjacency list, yes. I can be very sloppy
with my terms from time to time, though :\
[snip a bunch because I don't want to make more of an idiot of myself..
the wonders of having gotten some sleep finally]
> > 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.
Er, the way that most OO languages I've seen work is that subclasses
explicitly declare what their parent is. This is considered to be good, since
you don't have to know at the time of creating the superclass what
subclasses it will have, and can add subclasses without modifying the
superclass's definition.
> > 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.
So, just to be sure, you think that we should use configuration files like..
Section: Lisp_Interpreter
Contents: emacs20, rep, .....
This would require package mantainers to petition the person constructing
the hierarchy whenever they wanted their package added to a section. We
already sort of have that (with override files), but packages from separate
apt sources can be cleanly integrated. (although merging two files
like that wouldn't be too hard, so I guess you could do it..)
> 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.
But a tree where leaf-nodes can appear in multiple places is a graph.
I'm sure about that, sinces trees are a subset of graphs. :)
Is it really strictly 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.
I think maybe I do know what a graph is, I just tend to cut corners in my
head..
At the risk of looking like a fool again..
There's no reason you can't arbitrarily make a "root" in a graph (just make
a node with no edges pointing to it from which all other nodes are reachable,
call it "root" it :P), and it might be useful for speeding up some operations,
so we have a list of the nodes which "start" hierarchies (or is-a relationships,
if you prefer that) -- that is, nodes which are not immediately reachable from
another node. (so when converting to a tree for display, you don't have to
calculate this. You could certainly store it in some other way than a
node, but storing it that way seems like it would make some things simpler
to do) Depending on how you want to input the graph, this may or may not be
easy to do.
This might not be a useful idea in the context we have, though.
> 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 exactly what I said above, which you said doesn't work.
I think you're confusing my example Section with the current sections.
Under my previous example:
Package: xmms
Section: mp3_player, cd_player, gtk_proggy
(I just dropped the current meaning of Section..)
> 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?
I think we're in violent agreement.
I think this is a good way to start implementing it, and I thought I
started off somewhere by saying that a separate file might be good (maybe I
didn't, though.. :( )
I think it might even make sense to permanently store it be in an auxillary
file (like Packages)
I think a working prototype (prototype what? UI? hierarchy?) might be
most useful.
Oh, and I think we should perhaps add a Description tag to sections.
For the existing system I'll probably invent my own descriptions for sections
eventually, but a proper one would be nice in the future.
Daniel
--
/----------------- Daniel Burrows <Daniel_Burrows@brown.edu> -----------------\
| "The spork is strong with him..." -- Fluble |
\-Evil Overlord, Inc: planning your future today. http://www.eviloverlord.com-/
Reply to: