GraphTool

A small tool that reads a subset from Graphviz'DOT language and calculates several dominance-related properties:

• pre-, post-, and reverse-post order numbers for the input rooted at the entry and exit
• dominance tree
• postdominance tree
• dominance frontiers
• postdominance tree frontieres (aka control dependence)
• optionally eliminate critical edges beforehand

Usage

USAGE:
graphtool [-?|-h|--help] [-v|--version] [-d|--dump] [-e|--eval] [<file>]
Display usage information.
OPTIONS, ARGUMENTS:
-?, -h, --help
-v, --version Display version info and exit.
-c, --crit Eliminate critical edges.
<file> Input file.

Building

If you have a GitHub account setup with SSH, just do this:

git clone --recurse-submodules git@github.com:leissa/graphtool.git

Otherwise, clone via HTTPS:

git clone --recurse-submodules https://github.com/leissa/graphtool.git

Then, build with:

cd graphtool
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j $(nproc)

For a Release build simply use -DCMAKE_BUILD_TYPE=Release.

Invoke the GraphTool like so:

./build/bin/graphtool test/test.dot

Grammar

d='digraph'IDg (*digraph*)
g='{'S'}' (*subgraph*)
S=s ... s (*statementlist*)
s=','|';'| (ID|g) '->' ... '->' (ID|g) (*edgestatement*)

where

• ID = [a-zA-Z][a-zA-Z0-9]*

In addition, GraphTool supports

• • /* C-style */ and
• • // C++-sytle comments.

Entry & Exit

The first node mentioned is considered the entry, the last one the exit.

Caveats

Right now, GraphTool can't handle graphs with unreachable nodes.