Transitive reduction of a DAG

Version 1.2.0.0 (12.9 KB) by Frederik Gwinner
Computes the transitive reduction of a directed acyclic graph (DAG)
0.0
(0)
443 Downloads
Updated 29 Aug 2011

View License

Given a DAG in adjacency matrix format, this code will determine the topological ordering of the nodes and, using that ordering, efficiently compute the transitive reduction of the DAG. The package furthermore contains code to generate random non-transitive DAGs as well as derived transitive DAGs as test cases for the algorithm. A function writing the generated DAGs to graph file formats .sif or .dot for visualization is included. Code was developed as an alternative to the GraphViz tool tred, which has incredibly long run times on some medium-sized but highly connected DAGs (see file tred_vs_dag_trans_red.pdf included in the package).

Cite As

Frederik Gwinner (2024). Transitive reduction of a DAG (https://www.mathworks.com/matlabcentral/fileexchange/32723-transitive-reduction-of-a-dag), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2011a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Verification, Validation, and Test in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

dag_trans_red/

Version Published Release Notes
1.2.0.0

Changed unclear sentence in the comments for the file 'generate_testcase.m'
1.0.0.0