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' ID g                  (* digraph *)
g = '{' S '}'                       (* subgraph *)
S = s ... s                         (* statement list *)
s = ','
  | ';'
  | (ID | g) '->' ... '->' (ID | g) (* edge statement *)

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.