Feature - Graphs of graphs (or grouped graphs)

[jorgensigvardsson]

Have you seen yFiles by yWorks? They have a killer feature, and that is what they call "grouped graphs". See at the bottom of this page for a description plus screen shot: https://www.yworks.com/en/products_yfilesdotnet_about.html

I have been toying with the idea to implement this in GraphX. I think it's a pretty cool feature. It allows for some pretty cool organization of data!

Now, I think I know how to pull it off from a pure data structure perspective: that part is easy (or I'd like to believe so). What is less easy however, is: How should nodes be laid out? For an example of what is possible with their toolkit, yWorks has a free diagram editor called yEd (https://www.yworks.com/en/downloads.html#yEd). It is implemented with their Java offering, but from what I can tell, the Java and the .NET counter part are on par feature wise. yEd allows you to build diagrams, and perform layouts. When they perform layouts, they lay all nodes out, grouped or not, and then they resize the group boundary to a minimal rectangle around the grouped nodes. This behaviour might well be configurable, should one use their class libraries.

I would like to let the user decide how grouped nodes should be laid out. A layout could mean:

1. Layout as yEd allows you to do (see description above)
2. Option to only lay out the top level nodes/groups, and maintains each group's internal layout
3. Option to only layout the internal nodes of a node group
4. Option to recursively apply a combination of 2 and 3

What do you think? Do you foresee any obvious obstacles?

As I see it, this is a cross cutting feature. It would require:

• alterations to the graph data structures
• alterations to the algorithms
• alterations to the controls (both WPF and store apps)

It's a tall order, and I will probably need help doing this, as I'm not fully familiar with the internals of GraphX, and I am by no means a graph layout algorithm expert. What do you think?

[panthernet]

Hi i think it would be very complicated task. Honestly, i'm not sure if this feature is ever on demand. It would require heavy library modifications and new layouting techniques. I'm not an expert in algorithms either :) But if you want you can play with the code and see what exact modifications it will require to implement this feature. I'll try to look at the code and find possible solution, but currently i have almost no time to do that.

[jorgensigvardsson]

Well, it's just an idea. I have a couple of ideas that I might explore at some point. I wouldn't mind exchanging thoughts with you later on. It all depends on how much free time I'll have in the near future.

[panthernet]

Exchanging ideas is always good activity :) My opinion on that feature is that it is too heavy right now to implement, but can be investigated a bit on how it can be implemented.

[jorgensigvardsson]

I have been looking at some of the algorithm implementations, and there ought to be an opening for executing algorithms on a subset of of vertices and edges. I don't know how to constrain the layout though, to a specific area (the area of a node group). That's the main difficulty I see. There are of course, ways around this. I'm thinking about modifiying the algorithms, so that it is possible to specify a subset of vertices/edges to layout.

The theory is that after the set of nodes that the group contains have been laid out using a modified algorithm (that knows about subset constraints), the nodes positions are scaled and translated onto the "viewport" (not to be confused with an actual viewport in WPF - it's a concept here!) that makes up the group. I'm regarding groups as resizable entities, like MDI sub windows if you will. If a layout looks really cramped, the user has the option of resizing the group to get an overall good scale.

It ought to work, but I'm by no means a UI/UX grand master. Hopefully I will have some time for this by the end of Q2 to play with this idea. It is an interesting problem to solve. :)

[panthernet]

Yes, i thought about it too and graph area constrainment is the one of the most tough parts here. But it should be solvable as you don't need many algorithms for inner graph layouts, ideally just one slightly modified to take in account restricted space requirements. Have to google for it :)

To subselect a group of vertices (edges are not necessery in this case) it is enough to add some grouping property, for ex. int GroupNumber for IGraphXVertex interface and then extract groups in layouting algorithm and work with them. And i think we want to treat viewport as another vertex so it can utilize all edges management stuff and participate in default algorithms layouting with minimal modifications. If we go that way i think we should create new vertex class for viewport with it's own template and object managment logic. It's tricky as it should host another vertices and, for ex., move them all when it is moved by itself.

Viewport concept is fine, but the thing that bothers me most of all is that we have to have edge routing algorithm to lay edges inside viewport nicely and then somehow align in/out edges (relative to viewport). Right now edge connection points are automaticaly calculated and no static or pin mode is implemented. And i think it should be very helpful addition to vieports concept and GraphX overall to be able to pin edge connection points on demand. But that's separate and tricky feature by itself :) PS: the point in pinning edge connectors is that we can have them go into viewport from above and go out from below, that should simplify inner edge routing a bit and will make simplier to connect inner and outer edge points so the edges would look like going inside the viewport seamlessly.

I can play with the UI counterpart of the viewports and see what i can get as i'm more or less experienced in WPF :) Anyway, nice brainstorming here! :D

[birbilis]

in their free yEd tool (that uses the yFiles for Java library version) you just select some nodes and group them together, then you're able to give a label for when the group is expanded and another one for when the group is collapsed

for layout I guess they do it recursively, treating all grouped nodes as one large node that takes up the area you've defined for the group on the screen. So they layout the top level, then go into each group and layout its subgraph and so one if there are nested groups. In fact if there are multiple groups at the same level, one could do this in parallel. When using fixed group-node sizes (the ones the user defined), one could even parallelize the layout of both parent and children (and grandchildren etc.) graphs at the same time (since they don't depend on each other)

if one wanted to autocalculate the best size for the groups, they would go bottom up the tree, that is start first from the deepest nested groups, lay them out, get a bounding box for their subgraph, then use that for the size of a blocky node at the parent graph etc. Again subgraphs' layout could be parallelized, but this time it would be like doing a process flow where all deepest subgraphs start layout together and before a parent graph starts laying out it would need to wait for all its children/subgraphs to finish laying out etc. till you reach the top of the tree (the main graph). Workflow Foundation has such concepts btw. so maybe one could build a layout workflow tree (it's like the reverse of the nesting tree of the subgraphs) and then launch it, letting the Workflow engine use threads/CPUs in parallel as needed (and wait when needed for child layout flows to finish, then merge and continue with parent's layout flow etc.)

[panthernet]

Thanks, you've described an interesting approach on how to implement this feature :) Currently i'm interested in other features but if jorgen will have some time in the future to spend for it we might see some interesting results :)

[birbilis]

I've just started looking into GraphX myself, looking into making a Silverlight version for starters to use in ClipFlair Studio for a mind-mapping component (http://clipflair.codeplex.com - http://ClipFlair.net)

BTW, in case you haven't noticed, Microsoft AGL (Automatic Graph Layout) is now MIT licensed at GitHub (https://github.com/Microsoft/automatic-graph-layout) in case you want to borrow and/or contribute code back to it. They base their layout on the Sugiyama layout I think, not sure if you have such implementation in GraphX.

[birbilis]

btw, I described two variations both based on acyclic graph (tree) assumption. For graphs with loops it does need a bit more thought (haven't checked how well yEd/yFiles play with groups and loops at layout)

[panthernet]

Oh, thanks for the link! That's definetly good news :) I'll take a look at AGL code to see if i can improve something in GraphX. And yes, i have Sugiyama algorithm implementation in GraphX :)

[panthernet]

As for Silverlight, GraphX PCL assemblies supports SL v5. If you want to implement GraphX for Silverliht may be it is wise to look at METRO version as it is similary limited caompared to WPF as SL is. Currently, METRO version have very simple ZoomControl but almost all other of its features are up to date. If you have any questions don't hesitate to ask them in other thread or on the forums:)

[birbilis]

regarding zooming in Silverlight (in case you can get anything useful out of it) can also check http://clipflair.codeplex.com/SourceControl/latest#Client/ZUI/ZoomAndPan/ and how it is used at http://clipflair.codeplex.com/SourceControl/latest#Client/ZUI/ZoomImage/ and at http://clipflair.codeplex.com/SourceControl/latest#Client/ZUI/FloatingWindowZUI/ (the zoom control is used at template at this one)

can see FloatingWindowZUI live in ClipFlair Studio (http://studio.clipflair.net), just open the Tutorial activity from the menu and after it loads you can move around the floating windows and play with the zoom slider from the bottom bar (or with CTRL + mousewheel etc., with pinching at touchscreen etc.)

had tried to implement an overhead map too like one I've read you have at GraphX (haven't tried yours yet), but in Silverlight can't render parts of the scene into bitmaps if those parts are showing media content coming from other URLs (security/DRM related) and since I have video, image and geographical map controls etc. in ClipFlair's foreign-language-learning activities, I didn't bother making that overhead map since I'd have to show rectangles instead of live content in the zoom map.

...However at the WPF/Silverlight version of ZoomAndPanControl (see link above - I merged that control into a common sourcebase from separate Silverlight and WPF implementations on CodeProject and then refactored a lot), there is an example with a zoom map (with rectangles) that one could checkout

So I'll also have in mind to check out your Zooming control and see if I can contribute to that too, port it to Silverlight etc.

[birbilis]

Playing a bit with MSAGL's samples, it seems it supports (though not perfectly) nested graphs

btw there is a list of graph file formats and some info on them mentioned at: http://gephi.github.io/users/supported-graph-formats/ but note that the comparison table there shows features that Gephi implements from those formats, not which features the formats themselves support (e.g. DOT format supports subgraphs I think)

could quickly play around with DOT and MSAGL at http://rise4fun.com/Agl/ to see if and how well they support subgraphs

[panthernet]

As of now (v2.3.5) grouped graphs are supported with a limited functionality using standalone layout algorithm.