2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ If there's a convenient way of describing the DAG formed by orienting all edges to point away from $a$, you could describe this graph as the underlying undirected graph of that DAG. $\endgroup$ – David Richerby Sep 28 '15 at 8:47
1
$\begingroup$

Your algorithm relies on some properties of the input graph for its correctness. You should isolate these properties, and then you will know how to name your program.

The most likely answer is that your algorithms works on DAGs oriented source-to-sink, as you and David mention. However, there are many possible variants:

  1. Your algorithm might rely on the DAG having a single source.
  2. Your algorithm might rely on the outdegree being at most 2 or perhaps exactly 0 or 2.
  3. Your algorithm might work on every (possibly connected) graph, implicitly considering say the BFS tree (or forest) of the graph, from a given starting node.

Only you can tell which of these is correct for your algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.