search

fkling / JSNetworkX

Build, process and analyze graphs in JavaScript (port of NetworkX)
https://felix-kling.de/jsnetworkx/
Other
757 stars 185 forks source link

Tree generator not working as expected #47

Closed jarredgallina closed 9 years ago

jarredgallina commented 9 years ago

Hi fkling, What is the purpose of this part of the balanced tree generator code?

  if (r === 1) {
    n = 2;
  }

It appears to limit trees of degree one to only two nodes. For example, generating a tree of degree 1 and height 3 should give something like this: expected tree

Instead, we get this: untitled

fkling commented 9 years ago

The only valid balanced tree with degree 1 is 1 - 2.

1
 \
  2
   \
    3
     \
      4

is not a balanced tree because the height difference of the left and right subtrees of 1 is bigger than 1 (left: 0 right: 3).

Maybe throwing an error instead of "magically" changing the values would be better.

If you have a degree of 1, you can simply create a path graph.

jarredgallina commented 9 years ago

Hmm, wouldn't that requirement only be applicable to a binary tree though? In a balanced tree with degree 3 for example, we can't define things based on a left and right branch. Surely with a degree 1 tree there is no other branch to compare it to and so the main branch is balanced regardless of length? If not, an error is probably the better way to go.

A balanced tree is also a very broad case, and the trees generated are all perfect trees, a subset of balanced trees. Perhaps calling this a perfect tree generator instead of a balanced tree generator would be more accurate, and allow us to avoid the definition conflict we're having here.

Sorry if I'm being a bother. JSNetworkX is just an integral part of our project and the generators are very helpful, so I'd like to make sure we're on the same page with this. :)

fkling commented 9 years ago

In a balanced tree with degree 3 for example, we can't define things based on a left and right branch.

True, but instead we can say that every two subtrees can have a height difference of max 1.

Surely with a degree 1 tree there is no other branch to compare it to and so the main branch is balanced regardless of length?

That makes sense to me (even though I wouldn't use that function to create such a graph ;)). I will change the implementation to support this (will be part of the 0.3.0) release.

jarredgallina commented 9 years ago

Alright, thanks for that. :)

And yeah, I know this isn't really the best way to create a path graph but it's good to discuss the fringe cases.