Ordering / interaction for large directed networks

[viksit]

I have a large directed graph that represents a flow. For instance, there's a start node and an end node.

A naive version of it looks like this: start -> a -> b -> c -> d -> end a->c # an edge from a to c b->d # an edge from b to d

As a result, I have a requirement that some sort of directed layout be used to represent this graph (left to right).

I'm running into a few issues that I would love feedback on,

• When using a hierarchical layout with "LR" and sortMethod as "directed", the graph becomes really largely spaced out like this, which makes it impossible to draw edges from the top nodes to the bottom ones. However, using 'hubsize' will remove the directionality of the graph so I can't use that.

• And because of the hierarchical rendering, it also renders the edges in a very confusing way,

Notice that the edges towards the bottom of the screenshot are actually overlapping on top of each other because they are forced to be on the same level. So just by looking at the graph, its hard to say what connects where.

Ideally, I would like a mechanism where the graph is rendered left to right, but is not constrained by the concept of "levels" - so the nodes towards the right are rendered "narrowowy" rather than being spread really wide apart. What would be the best way to do this? (I see #2151 and #528 have some information but that seems to involve changing the visjs source. Is there a way to add on a custom sort function?)

• Also, given the graph becomes large and unwieldy with all nodes shown, I'm trying to find the best way to show only the out and in edges for a given node but hide everything else - in some sense, trace a path through the graph. One of the issues there is that I would have to walk through all the out edges of the selected node, and then for each of them, store dependencies, and then mark hidden/not hidden for the remaining ones. This seems a bit complex to do - and I was wondering if there are better ways of doing so?

Thanks!

[wimrijnders]

First, I have to ask: is this network truly hierarchical? This, I define as: every node has at most one parent.

In this case, the Network module does a sincere attempt at minimizing the area used and the total edge length. But it doesn't seem to be doing a good job here....this rearrangement is controlled by the options:

• layout.hierarchical.blockShifting
• layout.hierarchical.edgeMinimization
• layout.hierarchical.parentCentralization

These should be on by default; if you haven't changed them, it's time to consider that something is going wrong.

As a note: If the network is not truly hierarchical, then all bets are off. The layout rearrangement is known to fail so badly in this case that it's been explicitly disabled.

---

Is there a way to add on a custom sort function?

You're not the first to ask this question; some initiative has been made to make this available, but it's currently marked as a TODO somewhere in the code. But your request appears to be slightly different in that it affects nodes according to the population of a level.

Would you mind elaborating on how your think this sorting would work? This is for clarification on my behalf, to so see how it can fit in a more generalized sorting strategy.

---

In and out nodes:

A strategy I've seen used, is to use a group definition for the 'critical path'. This would change some display characteristic so that this path is visible. So, to define this path, it is sufficient to add a group field to the nodes in this path.

As to determining this path, if this network is truly hierarchical and you know the out-node, it is trivial: just make a list of successive parents to the top. This is entirely doable.

If by storing dependencies you mean registering the relationships between nodes, you don't really need to do that. The Network instance already knows this and makes the info available through method getConnectedNodes().

Hiding nodes can be achieved through clustering. Please have a look at this jsbin demo, in which branches can be shown/hidden. I can imagine this being combined with finding a critical path as above; anything not on it is hidden by clustering.

---

HTH.

[viksit]

Thanks for the feedback! Replies in order,

• You're right in that the network isn't purely hierarchical. There may be in certain cases two in edges into a given node, so I agree that something that does a purely hierarchical structure would fail. Would you have suggestions on how to render the grap? Some ideal layouts to me look like,

or

---

• Sure. The way I was thinking (first cut thoughts here) - we use the same logic as what renders the LR directed graph. The difference being - rather than try and fit all subsequent nodes into discrete levels, we keep introducing them into new levels based on the number of in-edges into them. This way, if theres only one connection, then a node goes to the next level (k+1). But if theres more than one, it goes into (k+2) - this way, the graph keeps extending towards the right rather than the node getting added underneath the previously existing (k+1)th node. I would also put in/reuse a constant that controls the spacing of each level, and also use a different CCW or CW curve constant to introduce more visible connections between these nodes rather than have overlaid edges of the same type. Good example is,

---

• Let me try this example.

[wimrijnders]

Your thoughts, essentials redacted:

1. As LR directed graph, but introduce nodes into new levels based on the number of in-edges into them.

   • one connection, node goes to the next level (k+1)
   • > 1 connection: it goes into (k+2)

2. Add a constant that controls the spacing of each level,

3. Use a different CCW or CW curve constant to introduce more visible connections between these nodes.

My feedback tacked on to these:

1. Number of in-nodes given a node id nodeId:

// Note: 2nd parameter available in next release
var numInNodes = network.getConnectedEdges(nodeId, 'from');

So, now you need to adjust the level. I'm trying the helicopter view here, to see how it will fit will other sort function request. This is the current best I can think of:

/**
 * Present 2 nodes to compare for sorting.
 * Params levelA and levelB are current or initial levels
 */
function customSort(nodeA, nodeB, levelA, levelB) {
  var compare;  // < 0, 0, > 0 significant
  // Do your sorting magic here
  return [ compare, newLevelA, newLevelB];  // ignore levels with 'return compare;'
}

Something like this will give you explicit control over which level is assigned. I'll be honest and say I'm not thrilled by this, but it's the best I can think of now. Feedback is welcome.

2. Ooh tough one. The thing here is that in physics there is only one option for the entire network controlling the spacing: layout.hierarchical.nodeSpacing.

How about the following idea: set a negative gravity constant and control the spacing using the mass of the nodes. Mass is node-specific, and since movement is restricted to the 'orthogonal' dimension, the effect on nodes on other levels will not be severe. This does require enabling physics, though.

3. This is what edges.smooth.type: dynamic is good at. Otherwise, you need to figure out CW and CCW yourself.

---

Thusfar. HTH.

[wimrijnders]

Personal Note: Keep this issue as a feature request. There's good stuff in it.