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.|
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
After the first steps of graph comparison a new Eclipse tab Compare pops up.
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:
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.
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.
The reset button hides green highlighted subtrees after the algorithm's execution and recreates the original colour of nodes on the represented trees.
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.
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.
For detailed information about used algorithms please check our JavaDoc