Bytecode Visualizer

Inspect, understand and debug Java bytecode, no matter if you have the corresponding source.

Sourcecode Visualizer

Draws a control flow graph alongside of Java source code.

Control Flow Graph Factory

Eclipse plugin for generating, editing and exporting control flow graphs.

Control Flow Graph Factory - Graph Comparison

Graph Comparison is a feature in the Dr. Garbage tool which provides a graphical user interface to investigate isomorphism between graphs.

How to compare graphs

Two graphs produced by Control Flow Graph Factory can be compared by the following way:

  • Select two graphs in Eclipse Package Explorer
  • Right click over selected items, then Compare with > Each other as depicted below

sd

Graphical user interface

After the first steps of graph comparison a new Eclipse tab Compare pops up. sd

The graphical user interface represents two selected graphs side by side in the new opened tab. On the upper-left corner the drop-down list indicates that the current window presents Graph compare. In case the graphs keep any meta information, it makes possible to choose text-to-text compare.

The management panel of actions is placed in the upper-right corner and looks as follows:

This button executes:

Execute Top-Down Maximum Common SubTree Isomorphism

The algorithm described in book Algorithms on Trees and Graphs from Gabriel Valiente in is able to define isomorphism under tree structures. Therefore after clicking on the button execute Top-Down Algorithm the input graph structures firstly converted into trees using Spanning Tree Algorithm. Thus all backward edges are being removed that ensures algorithm's execution on trees.

The algorithm finds the largest common subtree between two unordered trees starting from the root. This maximum common subtree is green highlighted. Notice that this subtree may not be unique, since there are different combinations of maximum common subtrees. However the number of nodes of this subtree is constant.

In order to define the largest subtree the algorithm uses an auxiliary Maximum Weight Bipartite Matching sub-algorithm. The Maximum Weight Bipartite Matching implements remarkable Hungarian Method that promotes to find edges in a weighted bipartite graph so that the sum of the weights in the matching has a maximal value. The Hungarian Method solves the assignment problem and uses a modified shortest path search in the augmenting path algorithm.

sd

The picture above demonstrates a result of the algorithm's execution.

Execute Bottom-Up Maximum Common SubTree Isomorphism

This button is responsible for execution of Bottom-Up Algorithm. The algorithm is described from Gabriel Valiente in his book Algorithms on Trees and Graphs. The algorithm functions only with tree structures thereby the input graph are converted into trees using Spanning Tree Algorithm.

Unlike Top-Down Algorithm, the search for the largest subtree is performed starting from leaves between two unordered trees.

sd

The picture above demonstrates a result of the algorithm's execution.

Compared graphs are reset from comparison

The reset button hides green highlighted subtrees after the algorithm's execution and recreates the original colour of nodes on the represented trees. sd

Reset input graphs.

Swap inputs of the graphs

The button firstly resets the colour of the graphs to original and then replaces them. The algorithms described above can be also applied for swapped graphs. sd

The graphs are swapped.

Zoom in / Zoom out

If the input graphs are too small or large, this feature provides synchronized zoom in/out of input diagrams. It allows to view the maximum common subtrees when the input graphs are large, for example Abstract Syntax Tree.

sd

The picture above demonstrates a result of the Top-Down algorithm in fitted zoomed out view.

For detailed information about used algorithms please check our JavaDoc