Hierarchy Graphs

[Prophet32j]

I'm looking at sigma.js for potentially replacing vis.js as our big data graphing library of choice. One of the deal breakers is hierarchy views of the network. I don't see anything besides this old issue #162 that says it's not possible, but potentially getting worked on. That was 3 years ago. Any word on this?

[Yomguithereal]

The issue is about the gexf file format. Do you have the same issue or do you just want to render your graph as a philogeny?

[Prophet32j]

The API serves up our data in a different format, but it doesn't take much effort to transform it to whatever we need. I need the ability to render some hierarchical network. So yes, phylogeny is the appropriate type of graph. There are parent-child relationships, sibling relationships, and self relationships (I call myself)

[Yomguithereal]

What would be the size of you tree in terms of number of nodes? The fact is sigma has been designed to render graphs, not trees. So one would probably need to develop a tree layout algorithm to be used with sigma to display it like a philogeny.

[Prophet32j]

We are possibly dealing with trees with 100 or more nodes. A level within the tree may have 30 or more nodes.

[Yomguithereal]

Ok. Have you by chance considered d3? You don't have a lot of nodes & the fact is sigma can do the job but will require you to write some amount of code to do the layout.

[Prophet32j]

We are concerned with performance with SVG and canvas libraries. Also, we have requirements to expand graphs to hundreds of nodes and edges. CPU driven graphs rendered with Vis have severely slowed down our UI. I'm trying to find a WebGL library that can build tree structures and do it without crippling the UI.

…

Sent from my iPhone

On May 6, 2017, at 7:40 AM, Guillaume Plique ***@***.***> wrote: Ok. Have you by chance considered d3? You don't have a lot of nodes & the fact is sigma can do the job but will require you to write some amount of code to do the layout. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

[Yomguithereal]

Well I guess than one option then would be to develop the layout algorithm and use it with sigma. I can help you towards this if you want. Do you have, per chance, an image showing roughly what you intend to render?

[Prophet32j]

[Prophet32j]

this is rendered with Vis right now. The large graph is rather tame, displaying less than 100 nodes. We found that Vis's render time was slow with anything over 100 nodes. It's even worse when displaying a typical network graph.

[Yomguithereal]

Do your node's data contain layout information or was it computed by Vis? Sigma would not have issues rendering graphs of that scale but does not have the code to perform this kind of layout. You would just need to compute the layout beforehand before using sigma to render.

[Prophet32j]

Vis handles layout for us, which is a very nice thing to have. Developing our own layout algorith isn't necessarily out of the question. We have requirements to display performant graphs. So if that means creating our own layout algorithm I think we would be ok spending the time to do it.

[Prophet32j]

some requirements:

• append a subgraph of a child node
• delete/hide a node and its subgraph
• render a network graph
• render a hierarchical graph (phylogeny)
• textual display of node name and edge name (runs on / owns / contains)

[Yomguithereal]

All your requirements can be met with sigma. The only one that might be problematic for performance is edge labeling but considering the scale of your graphs this should not be too much of an issue.

[Prophet32j]

Currently we have the edge label as a caption when you hover the edge. Is that possible and with better performance?

[Yomguithereal]

That's possible indeed.

with better performance

Since I don't know what are your current performance I can't really tell. What I know is that edge hovering is an algorithmical nightmare and tends to slow everything down (specially if you represent them as bézier curves).

[AVermeij]

Have you by any chance checked out dagre (https://github.com/cpettitt/dagre)? I've used this in the past for laying out hierarchies with sigma and it works very well.

[Prophet32j]

That's very interesting. I see it's no longer being maintained. How complex were your graphs @AVermeij ? Did you have large graphs with over 150 nodes? Was there any pain in implementing dagre with sigma?

[AVermeij]

I remember it working pretty well with graphs of a few hundred nodes, the main performance bottleneck being the layout calculations - in terms of rendering sigma can easily handle that number of nodes using the canvas or webgl renderers.

Actually, I just remembered the guys over at Linkurious developed a drop-in plugin to use dagre with sigma. Saves some work on an implementation perhaps, and has an MIT license (apart from lots of other elements of their lib, which is GPL): https://github.com/Linkurious/linkurious.js/tree/develop/plugins/sigma.layouts.dagre

Edit: it's also possible to delegate the layout calculations to a webworker so that they don't block the browser - may help when graphs get larger and calcs take longer.

[Prophet32j]

awesome. Thanks for your edit. Delegating to a web worker is critical when we have graphs with hundreds of nodes and edges

[sftranna]

Did you try to implement dagre with sigma?
I am looking for a tree structure but I am still unable to find a good way to start of dagre with sigma.js.
Any help/tutorial will be highly appreciated.
Thanks

[Prophet32j]

I just got back from over 30 days of military training. I will hopefully get to this at work soon.

[PythonLinks]

Here is my beta version of Hierarchy for 710 nodes.
https://pythonlinks.info/graph

Comments appreciated.

[Yomguithereal]

What's the layout algorithm used? Did you develop it yourself for this example? I would very much like to implement it for graphology so it can be used with sigma's next version.

[PythonLinks]

Yes, I developed it myself. Does that mean we should call it the "Lozinski Algorithm."

Maybe it would be easier to implement it with graphology than with Sigma. I had to add parent and children variables to each Sigma.js node object.

I guess in due course a new version of sigma.js based on graphology will be released, and then it should be relatively easy for me to port it over.

Is that fast enough? Do you have an urgent need for a hierarchy view?

I took a look at what you are doing. I think that your project is very interesting. Can I call you to discuss this further?

Warm Regards
Christopher Lozinski
PythonLinks.info/contact

[PythonLinks]

Thank you for your interest.
Here is the production version of a hierarchy graph.
Desktop.PythonLinks.info

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[hakunamatata97k]

Hey @Yomguithereal Any update on this issue? I have a kinda same use case, but with +10,000 nodes. So D3 is sadly not an option. :(

@Prophet32j what did you end up doing?
@PythonLinks could you please link the layout model that you implemented?

[PythonLinks]

Oh it is ancient and no longer online. Basically it was a circular tree of nodes, with some simple algorithms to determine the angle of each branch. Not that much work to replicate.

[rbowers02]

@hakunamatata97k Find anything that would work to draw this type of topology?