Perhaps it isnt even a DAG, but as its naming im after i wasnt sure what title to give this...
What is the name of a data structure where every node can only have 0 or 1 paths INTO it? Strictly, is this a tree?
Thanks
+4
A:
It's a directed tree. Plain trees as such are undirected.
Your constraint isn't precisely how trees are defined (the definition of a tree is that any two vertices are connected by no more than one path), but it does constrain your graph to be a valid directed tree. (Unless you want to employ weird usages of 'directed tree' that require a uniform tropism, which I can't say interests me.)
chaos
2009-06-03 15:59:58
thanks for the clarification
Andrew Bullock
2009-06-03 16:15:27
Per Bill the Lizard, it does require the acyclicity constraint. I was assuming it from all the mentions, though it isn't actually in your final specification.
chaos
2009-06-03 16:19:30
Yeah I meant acyclic, inferred from the title but i should have been more specific ;)
Andrew Bullock
2009-06-03 21:28:01
+4
A:
Are there any other constraints? From only the one you've given I can construct a graph that is not a tree.
A -> B -> A
If you add the constraint that the graph is acyclic, then it would be a tree.
Bill the Lizard
2009-06-03 16:16:40
How's that? He can do A -> B -> { C, D, E }.... I feel like I must be missing something.
chaos
2009-06-03 16:21:21
Oh, I see. I thiiiink you're reading an implication of a constraint on outlinks. But that seems impossible, since the only constraint you could read from OP's question would be zero outlinks, which would stop you from having a graph at all.
chaos
2009-06-03 16:23:26
@chaos: I think you started writing your comment before I edited my answer. I was missing something before the edit.
Bill the Lizard
2009-06-03 16:23:35
@chaos: Exactly right. I was thinking 0 or 1 outlink, which is either a linked list or not a graph.
Bill the Lizard
2009-06-03 16:25:59