RFR: 8309463: IGV: Dynamic graph layout algorithm

emmyyin duke at openjdk.org
Thu Aug 17 10:02:14 UTC 2023


### Purpose

IGV currently uses a static layout algorithm to visualize graphs. However, this is problematic due to the use cases of IGV. Most often, the graphs that are visualized are dynamic, meaning the graphs change over time. A dynamic graph can be thought of as a sequence of graphs where a given graph in the sequence is the state of the dynamic graph at that point in time. Static layout algorithms do not account for the rest of the sequence when visualizing a given graph. On one hand, it makes each layout more readable. But on the other hand, the layout for two consecutive graphs in the sequence can be vastly different even though the difference between the graphs is small. This makes it difficult to identify the changes that has occurred to the graph and can damage the internal understanding of the graph that the viewer has obtained. A dynamic layout algorithm takes the changes into account when visualizing a graph. To enhance IGV, such an algorithm has been implemented in this PR.

The layout drawn by the static layout algorithm is called "sea of nodes", while the layout drawn by the dynamic algorithm is called "stable sea of nodes".

The difference between the algorithms is illustrated in the following video:


https://github.com/openjdk/jdk/assets/52547536/35023362-a191-425e-b066-c7474db631f1


This work is the result of my Master's thesis which can be found [here](https://kth.diva-portal.org/smash/get/diva2:1770643/FULLTEXT01.pdf).


### Implementation

The algorithm is based on update actions that are applied incrementally to a graph layout in order to obtain the layout of the next graph in the sequence. By doing so, the nodes that appears in both graphs remain in their relative positions. A new layout manager called `HierarchicalStableLayoutManager` has been added which holds the core algorithm. The corresponding layout manager with the static layout algorithm is called `HierarchicalLayoutManager`.

If no layouts have been drawn yet, the `HierarchicalLayoutManager` is used. This is because the dynamic algorithm needs an initial layout to apply the update actions on.

The whole graph is represented by `LayoutNode` and `LayoutEdge` objects, that holds the positions of the nodes and edges along with other relevant information such as ID, name and size. These are updated, added and removed in accordance with the update actions.

Since `HierarchicalStableLayoutManager` tries to preserve the node positions, the layouts might get unreadable after a few iterations. In case that happens, one can "reset" the layout using the `HierarchicalLayoutManager` by clicking the icon for the sea of nodes layout and then go back to the stable sea of nodes layout.


### Testing

The testing has mostly been through manual testing. A program that randomly tests graphs has also been utilized, which can be [found on this branch](https://github.com/emmyyin/jdk/tree/JDK-8309463-test). 


### Miscellaneous

Some things that are helpful to be aware of:

* The code used to test the layout quality and stability for the thesis still remains in the class.
* The dynamic algorithm works best for small changes and is recommended for exploration (expanding and collapsing nodes).
* Every time a change occurs to the displayed graph, the obtained graph is treated as a completely new graph. It is therefore necessary to go through all the `LayoutNode` objects in both graphs to see if they appear in both graphs, and if so update the reference from the old to the new node. Similarly for the edges.


To further enhance the algorithm, one could explore:

* Automatic resetting with `HierarchicalLayoutManager`
* The order of which the update actions are applied
* How the layers and positions are chosen for nodes that are to be inserted into the graph


### Known issues
* The difference graph functionality (layout highlighting the difference between two chosen graphs) is not working for the `HierarchicalStableLayoutManager`.

-------------

Commit messages:
 - removing trailing ws
 - removing unnecessary call
 - clean up comments
 - move link check to stable layout manager
 - speed up layout manager
 - fic bug: let layout stay the same when no changes to graph
 - removing trailing ws
 - fix bug: CFG
 - bug fix: enable removal of empty layers
 - fix bug: adding node to empty graph
 - ... and 20 more: https://git.openjdk.org/jdk/compare/97df6cf5...9e33de52

Changes: https://git.openjdk.org/jdk/pull/14349/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=14349&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8309463
  Stats: 2194 lines in 12 files changed: 2121 ins; 51 del; 22 mod
  Patch: https://git.openjdk.org/jdk/pull/14349.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/14349/head:pull/14349

PR: https://git.openjdk.org/jdk/pull/14349


More information about the hotspot-compiler-dev mailing list