acyclic

Make a directed graph acyclic by reversing some edges

$ acyclic [path/to/input.gv] > [path/to/output.gv]

$ acyclic -v -n [path/to/input.gv]

$ acyclic -?

acyclic [-n|-N] [-o outfile] [files]

-n
    Assume input is acyclic; copy to output and warn if cycle detected

-N
    Like -n, but exit with error if cycle found

-o outfile
    Write output to specified file instead of stdout

acyclic is a Graphviz utility that processes directed graphs in DOT format, detecting and breaking cycles by reversing specific edges to produce a Directed Acyclic Graph (DAG). This enables applications like topological sorting, dependency resolution, and layout with tools requiring acyclicity.

The tool reads graphs from files or stdin and writes to stdout or a specified file. Its heuristic algorithm computes a spanning tree of the graph; edges closing cycles (not in the tree) are reversed, approximating a minimum feedback arc set. While efficient, it does not guarantee the optimal solution.

Options allow non-destructive cycle checking: -n warns on cycles while copying input, and -N errors instead. Ideal for preprocessing graphs before layout engines like dot or neato. Requires Graphviz installation; input must strictly follow DOT syntax.

Uses heuristic, not optimal feedback arc set; input must be valid DOT format; multi-graph cycles handled but may require iteration for complex cases.

Computes spanning tree via longest path; reverses feedback edges greedily for efficiency over exact NP-hard minimum feedback arc set.

acyclic input.dot -o dag.dot
dot -Tpng dag.dot -o layout.png

Part of Graphviz toolkit from AT&T Bell Labs Research (origins 1991); acyclic added in early 2000s for graph preprocessing; evolved with Graphviz releases, now at version 12+ with stability across Unix-like systems.

dot(1), neato(1), gvpr(1), graphviz(7)