One of the most challenging aspects of data visualization is the task of automatically arranging a graph. Then, when we introduce hierarchical data into the equation, the difficulty escalates rapidly. In some cases, default graph layouts may not align well with specific use cases. In such situations, opting for a custom layout is the best choice. Here in this article, we will demonstrate how to create a custom hierarchical layout using features provided by Cytoscape.js.
What topics does this article cover?
In this article, we will begin by sharing generic and fundamental information about graph layouts. Subsequently, our focus will shift to discussing the sequential layout. This is the type of graph layout that piques our interest. We will explore the optimal metrics to consider for generating an effective layout, while also delving into alternative approaches.
In the second part of the article, our discussion will center on our algorithm and its core functionalities. We will conclude the article by elucidating the steps to follow in order to replicate it.
Graph theory
A first definition of Graph Layout
Graph layout is the science and art of positioning nodes and edges in a way that ensures the resulting drawings are unambiguous and easy to interpret. A well-executed graph layout enables humans to effortlessly see each element, follow each edge, and extrapolate information hidden in the data. Graph layout finds applications across both private and public sectors. It is employed by developers, researchers, IT administrators, scientists, and data scientists.
Conversely, a Graph Layout represents a set of rules to follow for computing the placement position of nodes. Without these rules, it becomes challenging to effectively utilize and interact with the current graph. We can assume that graph layouts constitute a pivotal aspect of graph visualization. Developers and users are consistently in search of a layout that seamlessly aligns with the specific situation they are facing. Employing a specific and customized layout enables us to visualize data in a manner that is visually appealing and serves our purpose.
Hierarchical Layout
Sequential layout (even called Hierarchical) is a layout designed to emphasize the levels among the nodes. In a Hierarchical layout, nodes and edges are positiones and distributed across different levels or layers. Therefore, the data employed in these layouts must encompass hierarchical connections.
For example, consider data representing control information, where Node A controls Nodes B, C, and D. Node B, in turn, controls other nodes, creating a hierarchical structure. Another suitable dataset involves information flow from one level to another, as seen in blockchain and financial data. All such data integrates seamlessly with this layout.
Sequential layouts occasionally provide the flexibility to visualize small graphs as well as expansive trees of nodes with densely populated levels. In each scenario, they aim to conserve space by arranging nodes in a specific manner. When the dataset contains disconnected sequences rather than extensive networks, the sequential layout caters to these requirements seamlessly.
For the complete implementation of the algorithm that visualizes these types of data, we have to take into account some general guidelines such as:
- Avoiding node overlapping
- Minimizing crossings between edges
- Ensuring a symmetric structure of the graph
1) Avoid node overlapping
This concept is fairly simple yet crucial: we must avoid having overlapping nodes within the visualization. The issue arises because almost all existing graph layout algorithms assume that nodes are points. In practice, nodes may be labeled, leading to potential label overlaps and other related problems. The primary consequence of overlapping is the obscuring of information. In a general context based on graph layout, some algorithms have been designed to address node overlapping (one commonly used solution involves employing a Spring Algorithm). But in our specific context, it was sufficient to use a custom post-processing algorithm for its removal.
2) Minimize crossings between edges
In sequential/hierarchical graph layouts, links typically connect nodes across different levels. The smaller the graph, the simpler the application of the algorithm to minimize crossings. The simplest case is when links connect adjacent nodes in the same level, but, in general, scenarios may involve links between non-adjacent nodes, resulting in potential edge crossings. Our strategy aims to minimize, and in certain cases eliminate, edge crossings through a custom procedure.
Once we have ordered the nodes within their respective levels, we allow ourselves some flexibility to adjust their positioning based on metrics that calculate the possibility of edge overlapping. The nodes distribution on each level influences this calculation. This way, we arrange the nodes in specific sequences that minimize edge crossings.
3) Ensure a symmetric structure of the graph
We incorporated this highly subjective criterion during the algorithm’s development. Indeed, at this stage, we realized that all the optimizations we employed to achieve a more visually appealing effect led us to a structure that could be symmetrically positioned around a specific point, referred to as the ‘middle point,’ calculated based on the root’s positions. From this point, we attempted to recreate such a structure by introducing a translation effect before the final placement of nodes on each level of the graph. After various experiments, we also recognized that this ‘adjustment’ could not be applicable to every graph, but rather to those that are relatively small and have a comparable number of nodes within each level. Nevertheless, this criterion is an integral part of the graph layout and is utilized whenever possible in the visualization.
Alternatives to Hierarchical Layout
The alternatives to Hierarchical Layout involve similar aspects and structures:
- Radial Layout: This type of layout arranges nodes in rounded circles positioned around the original subject in a radial tree. Each generation of nodes becomes a new orbit extending outwards, illustrating a so-called ‘dependency chain.’ This serves as an alternative to the sequential layout, particularly for trees that resemble networks with a large number of child nodes for each parent.
- Spatial Architectures: These architectures attempt to position nodes to effectively manage available space in a geometrical manner. We can assume that these architectures are based on geometric figures. Although they may rely on various structures that they can transform into, we usually associate them with issues like edge crossings.
- Other Structures: In specific situations, it might be preferable to use alternative structures, such as diagrams that offer a different perspective and mode of displaying information compared to graphs.”
How to create a custom hierarchical graph layout with Cytoscape.js
The algorithm we developed is founded on the aforementioned guidelines and addresses various challenges we encountered. We can considered it as a custom hierarchical layout specifically designed for data containing father-son relationships. This layout is tailored to work with this particular type of data and is not suitable for other data structures.
Let’s see how to create a custom hierarchical graph layout with Cytoscape.js.
We recreated a top-down layout divided into levels containing nodes. All nodes within the graph are connected with edges to establish a father-son relationship, originating from the father and extending to the child, and so forth. This arrangement allows us to control the graph flow in the vertical dimension, as opposed to the horizontal dimension, enhancing the graph’s readability. In the process of creating levels, we strive to maintain a symmetric structure within the graph through a ‘post-processing adjustment.’ Using calculations based on the midpoint of the preceding level (the point expressed in ‘x,y’ coordinates that horizontally marks the center of the current level), subsequent levels are compelled to develop symmetrically from that point.
Now that we have grasped that concept, we can talk about the graph library we used to develop it.
Cytoscape.js
Cytoscape.js is an open-source graph theory library for visualization and analysis. It includes a comprehensive graph theory model along with various options for rendering and displaying interactive graphs. The design prioritizes user-friendliness, making it easy for programmers to integrate graph theory into their applications. The level of interaction with the graph is fully customizable, granting us the flexibility to choose the degree of freedom that that best suits our needs.
We integrate this library into a React micro-frontend application, utilizing React.js + TypeScript for its implementation to leverage the power of:
- Components Pattern: we employ the component pattern to construct an overviewed Graph Component based on other small React components. Each component works and cooperates with other structures to provide an interactive and real-time user experience.
- Static Typing: provided by TypeScript, we employed it to ensure code development safety and facilitate error fixing, enhancing readability for developers.
- Micro Frontend. We use the power of Webpack + React.js to develop a React application that we can include as black box inside other applications. It ensured flexibility and reusability of the graph component, making it a portable and adaptable component.
Other software components used:
- Material UI, the React component library that bases its core on the Google UI pattern. It provides a comprehensive suite of UI tools that expedite the implementation of new features.
- Axios: we employed this library to handle HTTP requests for retrieving graph data from the databases we encountered.
- Cytoscape extensions. These extensions play a crucial role in improving and enhancing graph interactions. Specifically, we utilize an extension for managing double-clicks on nodes, another for implementing a custom context menu for nodes, and finally, an extension for displaying a popper during specific situations (for instance, when an error occurs within the data). These extensions are freely available, and users also have the option to develop their own extensions and share them with the entire Cytoscape community. This fosters a collaborative and innovative environment.
Phases of a Hierarchical Layout creation
At first glance, we undergo a ‘calculation step’: we partition the area modeled by the Cytoscape layout (for rendering the graph) into levels. These calculations are based on the available width and height. Following this dimensional preparation, we can then begin iterating over nodes and edges.
Especially, the next step involves the graph roots. These roots are nodes that stand in the first layout level. The roots could be multiple or single. Depending on the number of roots, we use different approaches to develop the next level (e.g., the second level).
If there are multiple roots, we arrange them from left to right based on calculations that consider their number of children, potential edge crossings, and the possibility to expand the children to create another section of the graph. Following this initial calculation, we display the roots starting from a specific point, chosen through the calculations applied to the roots, ensuring their positioning is as close as possible to the ‘point of symmetry’ of the root level.
Conversely, if there is a single root, we skip the initial step and proceed directly to ordering the children.
The next step involves expanding all other nodes to calculate their positions. Starting from the leftmost child of the deepest level, we expand nodes case by case, considering those that have children in the lower level. Once the expansion of one level is complete, we apply a post-processing adjustment to symmetrically reposition the nodes for better alignment. This step ensures the specific structure of this graph.
This is how to create a custom hierarchical graph layout with Cytoscape.js. When all nodes are expanded, the job is done!
Conclusion
We undertook the development of this layout to address a significant issue for both us and our partners. We thoroughly examined all the criteria utilized in this process and applied them to the best of our ability to resolve various challenges we encountered. Perhaps this article on how to create a custom hierarchical graph layout with Cytoscape.js can serve as a helpful guide for developing a similar layout or, at the very least, as an inspiration to explore specific use cases.