CODEWITHSUNDEEP
graph-theory
outis
outis

Reputation: 77420

What's the name for directed trees with edges pointing towards the root?

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.

Upvotes: 2

Views: 1048

Answers (6)

outis
outis

Reputation: 77420

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

Upvotes: 1

John Y
John Y

Reputation: 14539

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).

Upvotes: 0

mjv
mjv

Reputation: 75295

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).

Upvotes: 1

John Y
John Y

Reputation: 14539

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?)

Upvotes: 3

C Pirate
C Pirate

Reputation: 444

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

Upvotes: 0

lod3n
lod3n

Reputation: 2903

A finite tree? http://en.wikipedia.org/wiki/Tree_structure

Upvotes: 0

Related Questions