tred

Construct the transitive reduction graph of one or more directed graphs

$ tred [path/to/input1.gv path/to/input2.gv ...] > [path/to/output.gv]

$ tred -?

tred [ -csV ] [ file ... ]

-c
    Treats cycles as single edges for reduction. If an edge (u,v) is part of a cycle, and u and v are already connected by a path within that cycle, the edge is preserved if -c is used.

-s
    Strict mode. If the input graph is strict (no multiple edges between the same two nodes), the output will also be strict. This option ensures unique edges in the output.

-V
    Prints version information for the tred utility to standard error.

file ...
    One or more input files containing graph descriptions in the DOT language. If no files are specified, tred reads from standard input (stdin).

tred is a utility from the Graphviz suite designed to compute the transitive reduction of a directed graph. It takes a graph description in the DOT language as input, typically from a file or standard input, and outputs a new graph description in the same format. The core function of tred is to remove redundant edges: an edge (u, v) is removed if there is an alternative path from u to v that does not use the direct edge (u, v). This process simplifies the graph by showing only the essential relationships and dependencies. tred is particularly useful for visualizing complex hierarchies or workflows where direct connections might obscure underlying multi-step paths. When cycles are present, tred can treat them specially, for instance, by reducing each cycle to a single edge if the -c option is used. It's a powerful tool for graph simplification and analysis within the Graphviz ecosystem.

tred is part of the Graphviz package, not a standard core Linux utility. Its functionality is specifically designed for directed graphs described in the DOT language. The output graph's structure, especially regarding cycles, can be nuanced. If cycles are present and -c is not used, tred will behave as if it's processing a DAG (Directed Acyclic Graph) and might not produce the expected reduction for cyclic components. The transitive reduction of a graph with cycles is not always unique.

tred exclusively operates on graphs described in the DOT language. Input files (or stdin) must conform to DOT syntax, and the output is also a DOT graph description, making it seamlessly compatible with other Graphviz tools like dot or neato for rendering.

Transitive reduction is the process of removing redundant edges from a directed graph. An edge (u, v) is redundant if there exists a path from u to v that does not use the direct edge (u, v). The resulting graph, while having fewer edges, preserves all reachability relationships of the original graph. This means if you can get from A to B in the original graph, you can still get from A to B in the transitively reduced graph, possibly through a longer path.

tred is an integral component of the Graphviz open-source graph visualization software package, originally developed at AT&T Labs Research. Its development is tied directly to the evolution of Graphviz, providing a specialized utility for graph simplification since the early days of the project. It embodies fundamental graph theory concepts, making it a stable and long-standing tool within the Graphviz suite for graph analysis and preparation for visualization.

dot(1), gvpr(1), gc(1), acyclic(1), neato(1)