Expand d3-dag to handle multiple paths from parent->child

[curiouserrandy]

d3-dag currently rejects graphs in which a single parent has the same child multiple times. However, this type of dag (multiple arcs from parent to child) can have meaning in some cases, such as in a process flow diagram when edges represent transformations and there are multiple different ways to transform one material into another.

I don't consider this particular feature high priority, but I'm filing the issue anyway because of its relevance to issue #80 . Specifically, I could imagine resolution of a simple cycle (A -> B -> A) resulting in this situation (A -> B, A -> B) in the result graph, so handling the full range of possible cycles may require making some allowance for multiple paths from parent to child.

I'll also note that if it's possible to handle multiple paths from parent to child, a self-loop (A -> A) would be fairly easy to handle: Insert a ghost node for layout to turn it into A -> B -> A and handle it as above.

[erikbrinkman]

I see how this could be related, but I do consider these significantly different. The sugiyama method as it's currently written makes several assumptions about edges being distinct. It may be possible to relax this by forcing that nodes that have more than one edge between them must be at least two layers apart, but it needs more thought.

It is true that the dag methods themselves don't require such a guarantee so it would be possible to allow the dags to be built and for the time being, not allow any of the layout methods to run on them, although it's not clear how useful that is.

I also want to point out that self loops are still a problem because the dag representation doesn't have a concept of dummy nodes, and a self loop necessarily requires it. In this sense I think the solution would be to augment the initial data to do this, and then in rendering handle appropriately. I think building that in may overcomplicate the library, but maybe I should see what seems to make the most sense for handling non-dags in the api, and maybe dummy nodes in this fashion will then also make sense.

[curiouserrandy]

Hmm. I'm sure there's something I'm not understanding, but two questions. Worst case, you'll teach me something :-}:

• If you just put in two dummy nodes (A -> B, A -> B ===> A-> C -> B, A -> D -> B) doesn't that solve the mismatch between the Sugiyama method and supporting multiple paths?

• Why does the dag representation need to have a concept of dummy nodes? It currently has a concept of nodes and edges, and the edges are (IIUC) created from the previously existing dummy nodes. So why isn't the current representation fine, with a spline with a series of points where the midpoint is where the dummy node was, and both of the endpoints are at the same node?

[erikbrinkman]

• Yes, I think that generally would, but that adds a different constraint to the layering step, which currently isn't there, and more importantly, I'm not sure there aren't parts of the code that make that assumption implicitly. So yes, it is possible, but slightly more complicated.
• A dummy representation isn't necessary for multi-graphs, but it is necessary to allow self loops because the self loop edge violates the dag criteria.

[erikbrinkman]

@curiouserrandy since you're the only one who requested it I think it was fine to close on master. multi dags should now be fully supported. Note that now ichildren() iterates over unique children, while ichildLinks() iterates over all links regardless of duplicate children.

I considered adding a way to tell links that have identical targets and data apart, but have held off. You can use the index when iterating, or modify the data to add relevant features.