tags:

views:

181

answers:

6

What do you call a graph that's almost an arborescence, but where the edges go in the opposite direction? That is, a directed graph with a center node, where every node has exactly one path to the center?

It might help to have a reason for naming this thing. I'm looking to describe the control structure used in a continuation passing architecture. If the structure is called a "romefuz", we could say that continuation passing uses a call-romefuz rather than a call-stack.

A: 

A finite tree? http://en.wikipedia.org/wiki/Tree%5Fstructure

lod3n
Not quite specific enough. A finite tree doesn't imply that all edges are directed towards one node.
outis
A: 

That's basically just a tree, as far as I can tell.

C Pirate
Under one common definition of tree that requires trees to be undirected, what I'm asking for isn't a tree. For the more inclusive definition of "tree" that equates trees with polytrees, what I'm asking for is something more specific.
outis
I doubt many people equate trees with polytrees. But programmers who don't know the formal graph theory sense of "tree" can certainly be excused for using the term "tree" to mean directed tree or rooted tree, since the classic programmatic implementation of the tree data structure is with single pointers from parents to children.
John Y
+1  A: 

I've seen this referenced as "tournament tree" or even "tennis tournament tree" but I do not know if that is a denomination which has roots in formal graph theory.

After unsuccessfully searching for 'tournament tree' in textbooks and similar references, a search in scholarly papers (eg Google scholar or citeSeer...) yielded a very significant number of relevant "hits", enough to call "tournament tree" a de facto name for the tree described in the question.

However, in re-reading, the 'tournament tree' could be a special case of tree described in the question, for tournament trees seems to imply a binary structure, i.e. where each node other than the leaves has a maximum of 2 edges.

In thinking about the taxonomy of graphs, at a broader level, this lack of a "formal" name for the tournament tree could indicative of the fact that this graph doesn't have any significant property, not readily exposed in broader denominations such as 'connected acyclic directed graph'. (We tend to give strong/definite names for the concepts which 'prototypes' offer a marked differentiation with other concepts from the underlying domain).

mjv
Even if it doesn't originate in graph theory, it is specific and self-documenting. I like it.
outis
+2  A: 

I don't know of a single-word term for the reverse of an arborescence, but I think it is good enough to just use "reverse arborescence". (The Wikipedia entry provides citations for converse, transpose, and reverse, of which I think reverse sounds the best, but surely you could also pick either of the other two. Perhaps converse sounds a bit more rigorous; lay people are less likely to use it. But then, lay people wouldn't really be talking about arborescences in the first place, would they?)

John Y
Great point. On preferring "reverse", see also: http://www.ags.uni-sb.de/~cp/p/verse/pdf.pdf
outis
Could we perhaps call it a "ecnecserobra", then? Only we wouldn't ever actually call it, because that's nigh unpronouncable.
outis
A: 

I decided to make another answer instead of editing my first one, because I'm kind of answering a different question now.

If you are interested in a name for a structure, and want to say call-something instead of call-stack, I think you might as well say call-tree. Yes, strictly speaking, "tree" is too general, but I think there's already precedent for (a) having computer science terms not map exactly to math terms and (b) favoring brevity, pronounceability, and readability.

A graph theory tree is (most commonly) undirected and rootless. Yet the classic tree data structure I was taught in school has a root and is implemented with single pointers from parents to children (in other words, a diagram of it would look like what you are calling an arborescence). It might not be important to capture the distinction between all edges pointing toward the root versus all pointing away from the root in the term you use; that may be evident from context. If you must capture this distinction, then you might want to consider call-reverse-tree (given that "tree", without qualification, implies away from root).

John Y
I had briefly considered "call tree" at one point, but thought it might be confused with a process tree, as you see in SICP 1.2.2. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2 I would probably have confused the two if I saw "call tree" without a definition. Maybe "called-by-tree"? Am I worrying about nothing?
outis
@outis: I'm afraid I can't find the term "process tree" anywhere on that page. The term "process" happens all over the place, and your link plops us onto a "tree-recursive process" example, but it's just a process that uses "tree-shaped" recursion. Perhaps you have created the "process tree" term yourself, based on your own mental model of that text?
John Y
@John: you're right about "process tree". The recursive diagram of what functions a function calls for a given execution is what "call tree" evokes for me.
outis
A: 

As a data structure, it's apparently called a "spaghetti stack", "cactus stack" or "saguaro stack".

outis