graph with fixed level like interactive tree with multiple parents

[nilanjan]

I had posted this on stack-overflow.  I'd like to get some more responses.

I want to create a tree like structure (mostly with 3 levels).  However, my leafs may have multiple parents.
I realize that this is a graph.  However, the data I have is quite structured and I don't need to have connections all over the place.

This is what I have:
1 grandparent
All children (2nd level) have only 1 parent
Grandchildren may have more than 1 parent (all at 2nd level)

Can you recommend any visualization for this?

Is it feasible to modify the tree layout for this problem (I program as a hobby :-( )

Thx,
- Nilanjan

[Hrvoje Marjanović]

I don't think there is solution to this, I am also looking for it.

Check this: http://bl.ocks.org/1079724

I also tried force layout but it simply doesn't look right, and tree layout expect children to have one parent.

Seems like best course of action whould be to somehow hack tree layout but this is beyond my paygrade for now.

Similar post:

https://groups.google.com/forum/?fromgroups=#!topic/d3-js/rTZjf9LFeSM

Hrvoje

[Ger Hobbelt]

Maybe these are of interest. It needs a write-up on constraint programming in a d3 force layout setting as there's some things I've found are really important that didn't occur to me at the beginning regarding how to code constraints and still have a 'functioning' force layout. (See the ...455 gist 'Lessons Learned' section for the lowdown, though)

BTW: I regret I only now saw the PDF mentioned by Mike: http://www.csse.monash.edu.au/~tdwyer/Dwyer2009FastConstraints.pdf

http://bl.ocks.org/3669455

http://bl.ocks.org/3670903

After working with/on force layouts quite a while, I think a faster track towards pure tree-like views of almost-tree-like graphs is hacking the hierarchical layouts -- that should work well enough if the graphs to be drawn are almost trees, i.e. have (very) few nodes which have multiple parents. I think I'll call the extra parents 'godfathers'; the two problems then facing us would be to (a) decide who's gonna be daddy and who'll end up in the Godfather Club (or in serious paper talk: devise heuristic / algorithm to extract a pure hierarchy from a graph), and (b) if and how to reorder nodes so that godfather links look 'neat', i.e. don't pollute the view by zipping across the entire span of it (e.g. positioning godfathered nodes near the godfather(s))

Met vriendelijke groeten / Best regards,

Ger Hobbelt

--------------------------------------------------
web:    http://www.hobbelt.com/
        http://www.hebbut.net/
mail:   g...@hobbelt.com
mobile: +31-6-11 120 978
--------------------------------------------------

[nilanjan]

This looks great.  I wasn't sure if the leaves in your examples have multiple parents - didn't see them

- Nilanjan

[Ger Hobbelt]

Nope, no multiple parents yet. These are tests purely to see whether I could get a force layout to produce a 'classic' tree view and how that would turn out visually / would behave under duress.

Lesson learned there is that layout.force constraints should act as limits AND forces instead of just limits. Also the lesson is that such forces can, or rather, SHOULD, be done as non-point forces, e.g. line forces, if the constraint is like that (force nodes off the edges of the screen = line force: linear force gradient instead of 'standard' radial force gradient for the usual points (forces))

Adding extra parents, i.e. turning it into a 'graph', should be relatively easy -- though worst case you have to come up with an algo to identify and 'fix/break' cycles and decide on 'who's daddy', particularly when 'parents' originate at different 'depth levels' (do you place the children at the maximum = visually-lowest depth ~~ child.depth = 1+max(parents.depth), or should they hang around at the minimum depth level (and other 'parents' of the kid then looking more like an odd sort of sibling from auntie Bertha's side of the happy family tree)

I'm interested in these worst case scenarios and the time to set them up and test the visuals: those will happen in subsequent gists.

I've done some (unpublished) work on gisting (sheesh, loving the verbing, aren't we) some very basic 'who's daddy' logic, but I'm rather unhappy with the result; 'who's daddy' is important to answer in your code as you may need to decide on a single hierarchy root from a graph - I do. The rest of the above is idling in the waiting list...

Met vriendelijke groeten / Best regards,

Ger Hobbelt

--------------------------------------------------
web:    http://www.hobbelt.com/
        http://www.hebbut.net/
mail:   g...@hobbelt.com
mobile: +31-6-11 120 978
--------------------------------------------------

[Greg Felice]

Has anyone had any luck wrestling the multiple parent problem with a standard tree layout, then overlaying additional diagonals onto the layout in a second pass? 

I'm trying to get this to work, but no luck so far.

To explain further: Imagine something like the standard tree layout: http://mbostock.github.com/d3/talk/20111018/tree.html, but with a dotted path connecting the top node to a level 3 node, while preserving the overall hierarchy...

Any thoughts?

Thanks

Greg

[Joo Tatt Tee]

I have done a simple family tree but using JIT (Javascript Infovis Toolkit) for multiple parents e.g. http://teejt.drivehq.com/family/FamilyTree/NgFamilyTree.html

I am looking for one using d3js