What is the name of a data structure looking like bowling pins?

Question

First of all, sorry for the title. Someone please propose a better one, I really didn't know how to express my question properly.

Basically, I'm just looking for the name of a data structure where the elements look like this (ignore the dots):

......5

....3...2

..4...1...6

9...2...3...1

I first thought it could be a certain kind of "tree", but, as wikipedia says:

A tree is [...] an acyclic connected graph where each node has zero or more children nodes and at most one parent node

Since there can be more than one parent by node in the data structure I'm looking for, it's probably not a tree.

So, here's my question:

What is the name of a data structure that can represent data with the following links between the elements? (/ and \ being the links, again, ignore the dots):

......5

...../..\

....3...2

.../..\./..\

..4...1...6

../.\./..\./..\

9...2...3...1

Answer 1

I think it isn't totally wrong to call it a Tree, although "Digraph" (directed graph) would be a more proper term.

First of all, sorry for the title. Someone please propose a better one, I really didn't know how to express my question properly.

The title is fine, I LOL'd hard when I opened the question. I am going to start calling them "Bowling Pins" now :)

      5

    3   2

  4   1   6

9   2   3   1

Answer 2

The most popular thing I reckon, which was laid out like this, is Pascal's triangle. It's the structure used to calculate binomial coefficients; each node is the sum of its parents:

http://info.ee.surrey.ac.uk/Personal/L.Wood/publications/MSc-thesis/fig36.gif.

Usuallly, when it comes to implementing such algorithms (such class is commonly referred to as "dynamic programming"), this "structure" is usually represented as a simple two-dimensional array. See here, for example:

n\k  0  1  2  3  4
------------------
0    1  0  0  0  0 
1    1  1  0  0  0 
2    1  2  1  0  0 
3    1  3  3  1  0 
4    1  4  6  4  1 
5    1  5 10 10  5 
6    1  6 15 20 15

I think, that there's no formal name for such a structure, but in dynamic programming such stuff is just... arrays.

But from now on, as NullUserException suggests I'm totally calling it "bowling pins" :-)

Answer 3

A "dag", or directed acyclic graph, is a graph with directed edge in which there may be multiple paths to a node, and some nodes may have both incoming and outgoing edges, but there is no way to leave any node and return to it (there are no cycles). Note that in a finite DAG at least one node must have nothing but outgoing edges and at least one must have nothing but incoming edges. Were that not the case, it would be possible to move continuously through the graph without ever reaching a dead end (since every node would have an exit), and without visiting any node twice (since the graph is acyclic). If there are only a finite number of nodes, that's obviously impossible.

Answer 4

Since there can be more than one parent by node in the data structure I'm looking for, it's probably not a tree.

What you're looking for is probably a graph. A tree is a special case of a graph where each node has exactly one parent. (except the root which has none)