NAME

tred - transitive reduction filter for directed graphs

SYNOPSIS

tred [ -ovr? ] [ files ]

DESCRIPTION

tred computes the transitive reduction of directed graphs, and prints the resulting graphs to a file or standard output. This removes edges implied by transitivity. Nodes and subgraphs are not otherwise affected. The ``meaning'' and validity of the reduced graphs is application dependent. tred is particularly useful as a preprocessor to dot to reduce clutter in dense layouts.

Undirected graphs are silently ignored.

OPTIONS

The following options are supported:

-o FILE: Redirect output to the given file. By default, output goes to stdout.
-v: Verbose output to stderr.
-r: Print information of removed edges to stderr.
-?: Print usage information.

OPERANDS

The following operand is supported:

files: Names of files containing 1 or more graphs in dot format. If no files operand is specified, the standard input will be used.

BUGS

Using bitmaps internally would substantially decrease running time.

DIAGNOSTICS

If a graph has cycles, its transitive reduction is not uniquely defined. In this case tred emits a warning.

AUTHORS

Stephen C. North <north@research.att.com>
Emden R. Gansner <erg@research.att.com>