scanwidth

scanwidth is a research-oriented Python package for computing edge-scanwidth and node-scanwidth of directed acyclic graphs (DAGs). The package includes exact and heuristic algorithms to compute both parameters and also returns the corresponding extension or tree-extension. See the corresponding paper (below) for more details on the algorithms and the mathematical background.

Use the pages below to get started quickly:

Contents

• Installation
  • Base package
  • Optional dependency groups
  • Development dependencies:
• Dependencies
• Quickstart
  • Reductions
• API reference
  • Main classes
  • Edge-scanwidth
  • Node-scanwidth

Citation

If you use this package in research, please cite:

Niels Holtgrefe, Leo van Iersel, and Mark Jones. Exact and heuristic computation of the scanwidth of directed acyclic graphs. Journal of Computer and System Sciences, 160:103802, 2026. doi: 10.1016/j.jcss.2026.103802.

If your work builds specifically on the node-scanwidth algorithms, please also cite the following paper describing them:

Niels Holtgrefe and Jannik Schestag. Tractable Optimization of Budgeted Phylogenetic Diversity on Networks Utilizing Node-Scanwidth.. 2026. doi: 10.48550/arXiv.2605.23319.