hierarchical layout

main considerations

Hierarchical layouts are usually implemented for trees, and even in these cases achieving an optimal layout in some respects is NP-Hard 2. The straight forward recursive algorithm of depth or breadth-first searches is acceptable and used (e.g. in Cytoscape) although there are optimizations (e.g. in Julia implementations cited in the wiki page about layouts in general).

One aspect to think about is the order of the branches (trees) or of nodes in each layer (graphs in general).

implementation for any graph

For general graphs (including non-trees, undirected graphs and directed graphs that allows bidirectional edges), the hierarchy criterion (or criteria) is not obvious and there does not seem to be a standard hierarchical layout. We next subdivide this problem for specific graphs.

digraphs with edges in only one direction

In this case, the problem can be stated as:

• parent -> child relations are yield by origin -> destiny of edges.
• Find the roots:
  1. they can be nodes without incoming edges (no parents), they should allow the discovery of all other nodes or
  2. nodes with greatest degree or out-degree or another (e.g. centrality) measure or
  3. nodes are defined by user as the roots.

In the last two cases, not all nodes might be discovered by following links from roots, which might: 1) yield incomplete representations of graphs or 2) require adding of parents to nodes after following links from roots on.

digraphs with bidirectional edges (or that allows edges in both directions)

The roots might be derived from the criteria above, but (i) might not yield roots. In this case, the parent-child relations are not so well behaved as before, but can be inspired by the same criterion. In other words, children are yield by out-going edges or by all edges.

undirected graphs

In this case, the root nodes and the parent-child relations are even more arbitrary. One might derive roots from (ii) or (iii) above (not i) and consider each layer as parents to any nodes reachable by one edge.

conclusions

A good news on all this complexity is that the most obvious criterion for choosing roots is degree or strength, not another of all the possible measures. The centrality measures of closeness and betweenness also make sense for choosing the roots and might be implemented. IMHO we should also account for roots defined by users. Another good news is that parent-child relations are by far most obviously yielded by edges, i.e. each layer consists of nodes that have at least one edge to the previous layer.

Additional criteria for deriving hierarchical layouts might be:

• minimum number of layers;
• minimum number of edges crossing;
• positioning of nodes in a layer with respect to measures (e.g. greatest degree are on top of the layer).

ideas for new hierarchical layouts

We might obtain meaningful hierarchical layouts in many ways. One of them is inspired by n-ary trees:

• Choose a root of n roots by selection of the n vertices with greatest values in a measure (e.g. degree).
• Each node has n children which are the n neighbors which were not visited yet with the greatest measure value.
• After the recursion has exhausted the nodes, check for unvisited nodes and attach them as children to highest layer possible.

In digraphs, this last step might be taken to yield other dimensions of the tree. These ideas were not found in the literature and might be good contributions for us to handle.

implementations in Cytoscape

In Cytoscape there is a hierarchical layout that is compliant with the discussion above.

Cytoscape.js' breadth-first algorithm 1

Their implementation is not trivial and should be ported to our layouts as a way to achieve both greater simplicity and compliance with ccNetViz. Also, because cytoscape uses elaborated data structures (and functions) that are suitable for analyzing graphs more deeply than just with layouts, our simplified implementation should be less computationally expensive.

In understanding the code, I have the following notes and questions:

• 'eles' seems to be computed in 6.
• nodes = eles.nodes().not( ":parent" ) in line 35 is also not trivial since the usage in code makes clear that these nodes are not the roots or nodes without parents. Maybe take a careful look at the collection/ directory.
• The roots can be defined (lines 42-90 of 1):
  • by the user;
  • by nodes.roots() if graph is directed. Seems to handle only cases where there are nodes with in-degree = 0 (Line 147 of 6);
  • by the greatest degree nodes (in each connected? component) if graph is undirected.
• graph.bfs is implemented in collection/algorithms/bfs-dfs.js 5.
• Nodes not found in the BFS are assigned the depth of any random neighbor (this can be enhanced by us).
• Seems clumsy by reassigning depths to nodes (this does not seem necessary if algorithm is well written).
• Sorts nodes in a layer by their connectivity to the above layer (this is just one of the possibilities).
• Can display each layer both in successive lines or concentric circles.

Cytoscape's algorithm 7

Is seems mostly the same as in Cytoscape.js. Might be studied in depth in near future.

implementation in yFiles 4

Has many more options than what is implemented in Cytoscape. Is not open source AFAIK.

implementation milestones

• General implementation for trees (done, needs debugging).
• General implementation for undirected graphs (roots are the most connected nodes, layers are successive neighbors).
• General implementation for Digraphs (assumes roots as nodes without incoming edges and theirs existence).
• Implementation of user-defined options such as roots, ordering of nodes in each layer, direction of flow, circular or linear.
• Implementation of non-degree criteria.
• Implementation of other hierarchical criteria such as defined in the ideas section above.
• Implementation of options found in other implementations (such as yFiles).