search

erikbrinkman / d3-dag

Layout algorithms for visualizing directed acyclic graphs
https://erikbrinkman.github.io/d3-dag/
MIT License
1.46k stars 87 forks source link

How can I make with your library something similar to this ? #15

Closed zmitry closed 5 years ago

zmitry commented 5 years ago

image

erikbrinkman commented 5 years ago

The closest thing to what you want, that's mostly supported out of the box is here. There are a few things that this doesn't capture from your picture that I'll highlight below along with how to solve them.

  1. You have one parallel edge (i.e. an edge with the same source and destination). Currently d3-dag doesn't support multigraphs. Support is probably possible, but would be relatively difficult and would require rewiring much (I think) of the backend because you're breaking a contract that's used pretty frequently.
  2. The css and styling is pretty different. This isn't really a problem with the library. I haven't looked into gradients for lines for svgs, but in principle this shouldn't be too difficult. I'll eave those issues up to you, although if you do get it working, it's probably worth putting up a fiddle so that people see it as a potential layout option.
  3. Identical node ordering. Currently the topological sort method decides arbitrarily if a number of nodes could go first in the ordering. If you want to reproduce this exactly, it'd need to be extended to tie break accordingly. This should be a pretty easy addition and probably makes sense.
  4. "Linear" dummy edges. This is more difficult as it requires a custom decross mechanism and a custom coordinate assignment, method. It will probably be easiest to treat the decross method as both phases, where the decross method assigns nonzero integers to each dummy node set (0 for the actual nodes). The decross method is then just ordering the nodes by this integer, and the coordinate assignment is mapping [minimum integer, maximum integer] to [0, width]. I can think of two obvious ways to do the integer assignment:
    1. Optimal: Us the MILP formulation for optimal decrossing, but in this integer context. I imagine it shouldn't be too hard to copy from the current method, but just like the current optimal decrossing, this might be very slow.
    2. Greedy: Essentially go layer by layer assigning the minimum absolute integer that's no in current use to the string of dummy nodes. This should be pretty easy to do, and is likely very fast, but might have a lot of edge crossings.

I'm happy to work on these, because this is a pretty layout and seems like a nice variant of a topological layout that should be supported, but it may take me a while as I have a number of other more pressing things on my plate. However, pull requests are very welcome, and note that the decross and coord methods just take arbitrary functions, so if you implement them, you can just pass them in without having to wait for an accepted PR.

zmitry commented 5 years ago

Thanks for your answer. I tried a lot to implement something like that with your library, I even read about sugiyama algorithm and how all this placement kitchen works. But I realised that with my constraints, node order are fixed, arrows are only one directions, arrows should be either on the right. So I end up with my custom algorithm for drawing and edges placement. image pls take a look:) I thought it should be more optimal than implementing decross algorithm using LP. Algo is pretty straightforward. Just balance number of edges at the right and left side and then set correct padding to them,

erikbrinkman commented 5 years ago

I'm glad this worked out. I'm going to keep this open as a reminder to implement a layout like this. Alternatively if you want to submit a pr with the code. This is a library for dag layouts, so even layouts that don't fit the sugiyama paradigm make sense.

erikbrinkman commented 5 years ago

@zhDmitry This now exists in d3-dag. See: https://beta.observablehq.com/@erikbrinkman/d3-dag-topological

zmitry commented 5 years ago

Hi, nice progress on that. btw you can compare my implementation with your https://codesandbox.io/s/lr0kwnnwy7. I bet results will be pretty similar.

zmitry commented 5 years ago

I will try to compare my results, but with my implementation I found some settings pretty useful. 1) allow to set specific side for node 2) set maximum lvl of padding check it out maxPad property

it was useful for my internal needs

zmitry commented 5 years ago

btw, could you recommend something to get familiar with sugiyama algorithm ? I read several articles about it but with no success.

erikbrinkman commented 5 years ago

This is what I used to write the library: http://www.it.usyd.edu.au/~shhong/fab.pdf

The general method is pretty simple:

  1. Assign each node an integer layer, such that if there's a link from A to B then layer(A) < layer(B).
  2. Create a dummy nodes along edges longer than one layer, such that now each edge only spans one layer. For example, if layer(A) = 1 and layer(B) = 3 and there's edge A -> B, then create a dummy node D with layer(D) = 2, and change the edges to be A -> D -> B
  3. Order the nodes on each layer to minimize edge crossings, because the order in each layer is all that determines if an edge crosses.
  4. Assign actual positions to each node that preserves their layer and order in each layer.