HOW-TO: Use xdot to analyze schedules

Based on Graphviz dot language there is the tool xdot. A GSI fork of xdot (one of 136 forks) enhances this to analyze schedules.

xdot

xdot is an interactive viewer for graphs written in Graphviz's dot language. The fork for GSI has additional features to analyze schedule graphs. For each vertex in the graph you can open an inspection window to display the attributes of a vertex. With a button from the toolbar you can color the graph such that each pattern has its own color. With the keys 'page up' and 'page down' you can move through the graph along the default destinations as long as these are unique.

The GSI version of xdot has more buttons in the toolbar and looks like this:

How to use:

1. From Git repository
   1. Clone https://github.com/GSI-CS-CO-Forks/xdot.py
   2. In folder xdot use PYTHONPATH=. python3 -m xdot <dot file > &
   3. For more options see PYTHONPATH=. python3 -m xdot --help
2. Installation on asl75x.acc.gsi.de
   1. On command line use: /common/usr/timing/bin/xdot <dot file> &

Use graph modifier and renderer with xdot:

Although xdot can be used with different renderers known as filters as command line arguments, you may use pipes. <graph modifier> | <renderer> | xdot -n -

Examples:

1. replaceChain -s <dot file> | xdot -
   Replace all chains in the graph and use default dot to render the graph and visualize it with xdot.
2. replaceChain -s -c 1 <dot file> | xdot -
   The same, but replace only one chain (-c 1).
3. replaceChain -s -b <dot file> | xdot -
   Replace all chains (obey the types of the vertices, -b) in the graph and use default dot to render the graph and visualize it with xdot.
4. replaceChain -s <dot file> | dot -Txdot | xdot -n -
   Replace all chains in the graph and uses dot explicitly to render the graph and visualize it with xdot.
5. replaceChain -s <dot file> | neato -Txdot -Gmodel=subset -Goverlap=compress | xdot -n -
   Replace all chains in the graph and use neato with extra options to render the graph and visualize it with xdot.

The three parts:

1. Graph modifier: here replaceChain
   The option -s is mandatory to get only dot output on stdout. The options -v, -vv, -o, -w are forbidden. Allowed are -b and -c <n>. -b separates blocks (vertices in a chain have the same type). -c <n> defines the maximal number of chains which are replaced.
2. Renderer: the allowed graphviz filters are dot (default), neato, twopi, circo, or fdp
   The option -Txdot is mandatory to get the output format needed for xdot. Other options are specific to the renderer. For example, -Gmodel\=subset -Goverlap\=compress are options for neato. See Graphviz Documentation for details.
3. Viewer: xdot
   The option - is mandatory to instruct xdot to read the input from stdin. The option -n is necessary when a renderer is explicitly used. This tells xdot not to use its own renderer.
   dot -Txdot <dot file> | xdot -n - is equivalent to xdot <dot file>.

Additional tools

replaceChain

replaceChain helps to analyze the structure of a schedule. It replaces all chains by single vertices. This reduced the number of vertices and the size of the drawing. However, the location of the new vertex may be not the same as the chain.

The new vertex gets the shape, color and other attributes of the first (top) vertex of the replaced chain. The new vertex is connected to the vertices connected to the first and last vertex of the chain.

Example: A schedule from INT

original	2 chains replaced

Located in bel_projects, path modules/ftm/analysis/scheduleCompare/main, make replaceChain.

How to use:

1. From Git repository Clone https://github.com/GSI-CS-CO/bel_projects.git, branch dm-fallout-tests-2
   Run make in folder modules/ftm/analysis/scheduleCompare/main
   Tests are in folder modules/ftm/analysis/scheduleCompare/test
   Documentation in folder modules/ftm/doc/ReplaceChain
2. Installation on asl75x.acc.gsi.de
   In folder /common/usr/timing/bin

Command line example: replaceChain -v <dot file> ‐o <output dot file>. If no output file is given, stdout is used and you can pipe the output to other commands: replaceChain ‐s <dot file> | dot ‐Txdot . This replaces all chains in the original graph and adds coordinates for drawing with xdot.

Usage: replaceChain <dot file>
Replace chains in the schedule graph with a single vertex.
Options: 
        -b: 'blocks separated', vertices in a chain have the same type.
        -c <n>: optional, replace n chains. Default is to replace all chains.
        -h: help and usage.
        -o <file name>: name of output file.
        -w: overwrite output file if it exists.
        -s: silent mode, no output, only return code. Usefull for automated tests.
        -v: verbose output.
        -vv: super verbose, more output than verbose.
        -V: print version and exit.
Return codes: 
0 EXIT_SUCCESS, all chains are replaced.
1 1, some chains are replaced. There may be more chains in the graph.
11 BAD_ARGUMENTS, unknown arguments on command line.
12 MISSING_ARGUMENT, at least one of the file names is missing.
13 FILE_NOT_FOUND, one of the dot files not found.
14 USAGE_MESSAGE, usage message displayed.
15 PARSE_ERROR, error while parsing, unknown tag or attribute.
16 PARSE_ERROR_GRAPHVIZ, error while parsing Graphviz syntax.
19 VERSION_MESSAGE, version displayed.
negative values are UNIX signals

scheduleCompare

scheduleCompare is a command line tool to test if two dot files represent the same schedule.

How to use:

1. From Git repository Clone https://github.com/GSI-CS-CO/bel_projects.git, branch dm-fallout-tests-2
   Run make in folder modules/ftm/analysis/scheduleCompare/main
   Tests are in folder modules/ftm/analysis/scheduleCompare/test
   Documentation in folder modules/ftm/analysis/scheduleCompare/doc
2. Installation on asl75x.acc.gsi.de
   In folder /common/usr/timing/bin

Usage: scheduleCompare <dot file 1> <dot file 2>
Checks that graphs in <dot file 1> and <dot file 2> are isomorphic, i.e. describe the same schedule.
Options: 
        -c: check dot syntax (stops parsing on all unknown attributes).
        -h: help and usage.
        -n: do not compare names of vertices. Not applicable with option -t.
        -s: silent mode, no output, only return code. Usefull for automated tests.
        -t: test a single graph: compare each vertex with itself. This tests the vertex comparator.
        -v: verbose output.
        -vv: super verbose, more output than verbose.
        -V: print version and exit.
Return codes: 
0 EXIT_SUCCESS, graphs are isomorphic.
1 NOT_ISOMORPHIC, graphs are not isomorphic.
2 SUBGRAPH_ISOMORPHIC, graph is isomorphic to a subgraph of the larger graph.
11 BAD_ARGUMENTS, unknown arguments on command line.
12 MISSING_ARGUMENT, at least one of the file names is missing.
13 FILE_NOT_FOUND, one of the dot files not found.
14 USAGE_MESSAGE, usage message displayed.
15 PARSE_ERROR, error while parsing, unknown tag or attribute.
16 PARSE_ERROR_GRAPHVIZ, error while parsing Graphviz syntax.
17 TEST_SUCCESS, test a single graph with success.
18 TEST_FAIL, test a single graph with failure.
19 VERSION_MESSAGE, version displayed.
negative values are UNIX signals

For developers of xdot only

Installation of xdot:

1. In folder xdot use './setup.py build && ./setup.py install --user' to install xdot as a user package.
2. pip list --user lists all user packages
3. pip show xdot shows the description and the location of the xdot package.
4. Use ./setup.py install --prefix /common/usr/timing to install the GSI version of xdot to /common/usr/timing. The globally installed xdot is the original version without GSI features.