Background:
I worked on finding the maximum path from the top to the bottom of a tree-like graph. During the process I found that the algorithm for finding the maximum path from the top to bottom of a binary tree also worked for my graph. My problem arose when trying to name the program, because the graph it works on is clearly not a binary tree.
The problem:
My graph looks like this:
·······a······
······/··\·····
·····b···c····
····/··\··/··\···
···d···e····f··
··/··\·/··\··/··\·
g····h····i····j
Due to that all the inner nodes at lower levels have multiple "parents" from the level above, it cannot be classified as a binary tree. From the perspective of finding the maximum path from the top to the bottom, it could be classified as a DAG, but because there strictly are no directed edges in the input graph, this also seems wrong. If presented in the following way:
a - c - f - j
|····|····|·
b - e - i
|····|·
d - h
|··
g
It could be argued that it is a lattice graph. But that would conceal that it has a defined "top" and "bottom", and that I have worked with a root and leaves. One could always fall back to calling it a general graph I guess, but that would conceal that it follows a very rigid structure.
My question:
What should I call this bastard that can be processed by many of the algorithms applied to binary trees but violates some of the properties of trees, for the sake of my problem can be considered a DAG but has no directed edges, and somehow resembles a lattice?
