Re: Misclassification of packages; "libs" and "doc" sections
Daniel Burrows wrote:
>
> 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 :\
You know, graphs are very easy to get confused about if you haven't
written a variety of graph algorithms. I'm supposed to make no
mistakes about it as it's kind of my research subject ;) I remember
a professional computer graphics programmer describing scene graphs
but confusing DAGs with trees.
>
> [snip a bunch because I don't want to make more of an idiot of myself..
> the wonders of having gotten some sleep finally]
>
Man, we're working together here. Nothing like that, let's just
get things right so we can take a further step.
> So, just to be sure, you think that we should use configuration files like..
>
> Section: Lisp_Interpreter
> Contents: emacs20, rep, .....
Well. There's an arrow from Lisp_Interpreter to Interpreter only
which reads "Lisp_Interpreter is-a Interpreter". Only outgoing arcs
are maintained for a digraph (directed graph).
More like:
Category: Lisp_Interpreter
IsA: Interpreter
> 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..)
yeah, that's why graphs don't hold "reverse maps" here. (at a vertex,
you just store where you can go from that vertex. ie the vertices
adjacent to the vertex you're at)
>
> > 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?
>
A tree where leaf-nodes can appear in multiple places is just
what you say. :) Nothing more, nothing less. A more relaxed structure
than a tree. It is then sth like
a DAG in which there is a special node root, from (to, depending
on the direction of arcs) which there's a unique path to every other
vertex except that [define leaf vertex, and say that leaf vertices can
be shared among the immediate neighbors of leaves.. sth like that]
> 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.
>
Okay, you can make such a single "source" vertex to the entire graph.
But how do you guarantee that all vertices are reachable from it?
You just have to take into account all vertices that have no outgoing
edges. Those happen to be the "toplevel" categories, or the most
general classes in this hierarchy.
> > 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.
>
OK. No paths like sound/mp3/player
> > 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.. :( )
>
Yeah. It's like writing a program to define the class hierarchy of
an existing code. Sometimes people do that to provide a well
defined new interface to an old program.
> I think it might even make sense to permanently store it be in an auxillary
> file (like Packages)
>
Definitely. Though I'd tend to think that a single file is not something
maintainable. I guess only auto-generated stuff should be made
single-files.
> I think a working prototype (prototype what? UI? hierarchy?) might be
> most useful.
>
not UI, but the formal definitions and a suitable category hierarchy.
> 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.
>
Of course why not? Another approach is to textually cluster the
descriptions of packages automatically. That gives us what we
want (a multiple-inheritance class hiearachy) above packages! I'm
not sure of the effectiveness of the thing though as Natural Language
Processing may get too fuzzy. [What if descriptions haven't been
written well?....] If there're such tools, we could run it to see
what kind of a hierarchy it finds and then edit it.
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: