Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Overlapping Nodes #158

Closed
rkistner opened this issue Nov 10, 2014 · 5 comments
Closed

Overlapping Nodes #158

rkistner opened this issue Nov 10, 2014 · 5 comments

Comments

@rkistner
Copy link

In some tree configurations, I get overlapping nodes (see example below). In large trees, the overlap can become even worse. This can be solved by changing the order of edges. However, since I'm working with automatically generated trees, it's not feasible to do the re-ordering manually.

Dagre is a great library - this is currently the only issue preventing me from switching from server-side graph layout (Graphviz) to client-side graph layout. Are there any configuration options that will help with this, or will this need a change in the algorithms to fix?

Overlap (Source):

overlap

No overlap (Source)

no-overlap

@rkistner
Copy link
Author

This case appears to be fixed recently (works on the master branch of dagre-d3). I still get some minor overlap in one case, but it's much less severe. I'll open the issue again if I find a nice example.

@rkistner
Copy link
Author

I've found a different example now, that still has overlap (B and F):

digraph Overlap  {
A -> B -> C -> D -> E
A -> F
B -> G
B -> H
C -> I
C -> J
C -> K
D -> L
D -> M
}

overlap2

@rkistner rkistner reopened this Nov 11, 2014
@rkistner
Copy link
Author

So I did some more testing, and found the following:

When setting g.graph().align to any of the four possible values (UL, UR, DL, DR), it works without an issue. However, with DR, the order of F and B are switched around. This causes the median x value of B and F to be the same.

Just taking the average of the UR and UL works in this specific case, but I'm not sure if there are other cases where the same can happen again.

@cpettitt
Copy link
Collaborator

Nice catch on the swap!

I'm thinking about just ditching the longest path algorithm from the original BK paper and swapping in a simple algorithm that would also be linear, but with a larger constant. I believe the rest of the paper is pretty sound. Will get to this during the weekend if not sooner and will verify against the above along with some others.

@rkistner
Copy link
Author

Confirmed, even in my most complicated graphs I don't get any overlap with the latest version.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants