Possible to get sankey to handle networks with cycles?

[bhaugen]

Loving the sankey plugin! But apparently it won't handle networks with cycles, for example:
http://locecon.org/clusters/network/8/

Any ideas about how to fix, work around, or otherwise grapple with the problem?

If so, I will happily try them.

If not, I'll tinker a little and see what I can do...

[mbostock]

I'd love to see this implemented. The strategy I'd try first is to ignore links that generate cycles in the initial layout, and then add them back in again to draw the loops.

[bhaugen]

I'm on it. Any pointers to where I should focus in the code? When I halted it a few times, it was cycling through computeNodeBreadths(), but maybe that was a red herring...

[mbostock]

Right, computeNodeBreadths is where you'll get an infinite loop unless you detect cycles. So that's the first thing (where you ignore links that generate cycles). The second thing is we probably need to handle loopback links and render them differently. Loopback links still exit the right side, but then they need to loopback to the source and enter on the left side. Probably the sankey.link implementation needs to special-case loopback links and generate a different path for them.

[bhaugen]

Thanks for the continued conversation.

What I did for the short term (because I got users waiting for sankeys, and their networks are acyclic) is cheat. I already got code to detect cycles in python (where I'm assembling the data for the sankeys), so I just disabled the sankeys if your network has a cycle.

Then I gotta get my head back on straight within computeNodeBreadths, which currently makes it spin. Then figure out how detect and postpone cyclic links there.

I suspect the loopback links are gonna be beyond my skill level, but we'll see.

[cfergus]

I've made an attempt at solving this issue. There are a few ways it could be improved, but please let me know if a pull request (or otherwise) is in order.

Example at : http://bl.ocks.org/3921009

Fork and changes at:
cfergus/d3-plugins@deb7bda

[bhaugen]

Thanks, but those changes did not work for me. Created false cycles in networks that did not have cycles, and did not handle simple cycles very well.

Here's a network that has no cycles, before:
http://locecon.org/clusters/sankey/16/

Here it is after:
https://docs.google.com/open?id=0BxlqOeaPnXHfSTloOWVWQTdFVkk

Here's one with a cycle, using your changes:
https://docs.google.com/open?id=0BxlqOeaPnXHfSGpXbVFPVkFCZjQ

Here's the page source:
https://docs.google.com/open?id=0BxlqOeaPnXHfRmtmU2UwTzFsOFE

Let me know if you think I did not use your changed code correctly - or if you can't access those files.

[cfergus]

Regarding the first network featuring "Groundfish":
My code, at present, checks if the node names are the same, as opposed to node object equality. It appears that your code uses multiple nodes with the same name (specifically, "Groundfish", for example), which my code doesn't account for (my bad).
I'll try switching to object equality, and see if that makes things better.

Regarding the second network, featuring "Restaurant -> Compost Materials":
The cycle is present, but my layout is not good. You can see the cycle being rendered (in part) at the top of the screen. This is because the "Restaurant" node is flush with the far right of the viewbox (where the path starts), and "Compost Materials" node is flush with the far left (where the path ends).
I will need to update the overall algorithm for laying out the entire sankey diagram, as well as the feedback loops, in order to make this display as one might expect. This part might take a bit longer. Open to suggestions.

[bhaugen]

My code, at present, checks if the node names are the same, as opposed to node object equality.
It appears that your code uses multiple nodes with the same name (specifically, "Groundfish", for example),
which my code doesn't account for (my bad).
I'll try switching to object equality, and see if that makes things better.

I understand the problem. My code actually assembles the link relationships on the server, so you can't see from the page source how it's done (looking up the array indices based on object identity). I've meant to work up a rev for sankeys to assemble the links based on node object ids rather than array indices in the sankey javascript, but haven't had time. That would at least make explicit what is happening.

So if providing unique node ids would help what you are trying to do, I can easily provide them.

The duplicate names were a given (to me: they were created by users), and they do actually make sense on some level...

[cfergus]

Alright, round two.
http://bl.ocks.org/3956043
Points of note:

• (improvement) The viewbox is expanded to fit potential cycles at the left and right. This could be made better by only expanding when such cycles exist.
• The equivalence is based on nodes now, so your example with nodes identically named should work out now
• The gist example above uses randomly generated sankey data. As such, you don't know what you'll get
• The bl.ocks view seems to have its own css, so you may just want to use the "Open in a new window" link to see it more fully.
• (bug) This code doesn't seem to handle 'self-cycles', where a node loops back onto itself.

Let me know if this seems usable!

[bhaugen]

cfergus, thanks for persisting. It's better; does not falsely detect cycles when nodes have the same names. My networks with cycles look a little odd, but it also looks like I will have to change my code to take advantage of your cycle features. I'm in crunch mode on another project, but will try that when I get a chance.

[kunalb]

Hi -- i just sent a pull request that might help (#39) with this.

[angiehjort]

hi all! so was the issue actually solved? is there a demo showing it? yes, works perfect!

however http://bl.ocks.org/3956043 is broken
because GIThub does not allow to fetch .js with raw. prefix anymore.
@cfergus, please consider changing a link to sankey.js

thanks!

[vlasvlasvlas]

are cycles now implemented?

[angiehjort]

yes, they are, as i could see yesterday
save the code from http://bl.ocks.org/3956043 and the referred sankey.js locally, change the link to sankey.js and run the code. it should work:

[cfergus]

My bad. I updated my gist to include the modified sankey.js alongside it. The link should work now for http://bl.ocks.org/3956043