Crossing Minimization (MinCross)

Reimplementation of Graphviz’s mincross algorithm for edge crossing minimization in leveled logic networks. This algorithm iteratively reorders nodes within ranks to reduce the total number of edge crossings, using the median and transpose heuristics originally described in Graphviz’s dot layout engine. It operates on networks with explicit rank information (e.g., mutable_rank_view) and produces a layout-friendly node ordering that improves readability and wire routing efficiency.

The algorithm consists of three main optimization passes:

  1. Initialization pass — explores simple reorderings to quickly lower crossings.

  2. Refinement pass — stabilizes ordering while checking convergence thresholds.

  3. Full optimization pass — performs iterative median and transposition steps until no further improvement is observed.

Each pass alternates between upward and downward traversal through the network ranks to refine node orderings based on the median positions of their fanin and fanout connections.

Header: include/fiction/algorithms/graph/mincross.hpp

struct mincross_params

Parameters for the mincross crossing minimization algorithm.

Public Members

bool fixed_pis = false

Whether the rank positions of primary inputs (PIs) should remain fixed during the minimization process. If set to true, PIs will not be reordered.

bool optimize = true

If false, skips optimization and only reports the current number of crossings.

uint64_t max_iter = 24

Maximum number of iterations per optimization pass (heuristic from Graphviz). Larger values allow more refinement but increase runtime. Default (24) works well for small and medium-sized networks.

uint64_t min_quit = 8

Minimum number of consecutive iterations without sufficient improvement before quitting early (heuristic from Graphviz). Prevents wasting time when the number of crossings no longer decreases.

double convergence = 0.995

Convergence threshold: relative improvement factor required to reset the early-quit counter (heuristic from Graphviz). If the current crossing count drops below (convergence * best_cross), where best_cross is the best/lowest crossing count found so far, the process continues. Default is 0.995 (i.e., at least 0.5% improvement required).

uint64_t init_refine_max_iters = 4

Maximum number of iterations in the initial (pass 0) and refinement (pass 1) phases of the crossing minimization procedure (heuristic from Graphviz).

  • In these early passes, the algorithm explores simple reorderings to quickly reduce crossings without investing in the full optimization effort.

  • By default, the number of iterations is capped at 4 to prevent excessive runtime during initialization and refinement. This cap can be lifted if a larger global maximum (ps.max_iter) is set.

  • In the full optimization pass (pass 2), ps.max_iter is always used instead.

struct mincross_stats

Statistics collected during the execution of the mincross algorithm.

Public Members

uint64_t num_crossings = std::numeric_limits<uint64_t>::max()

The total number of edge crossings after optimization.

template<typename Ntk>
Ntk fiction::mincross(Ntk &ntk, const mincross_params &ps = {}, mincross_stats *pst = nullptr)

Reimplementation of Graphviz’s mincross algorithm for edge crossing minimization. This function reorders nodes in a leveled logic network to minimize the number of edge crossings using iterative median and transpose heuristics.

Reference implementation: https://gitlab.com/graphviz/graphviz/-/blob/main/lib/dotgen/mincross.c

For more on Graphviz’s dot layout generation: https://graphviz.org/docs/layouts/dot/

Template Parameters:

Ntk – A logic network type with level and fanout support.

Parameters:

  • ntk – The input leveled network whose ranks are to be reordered.

  • ps – Configuration parameters for the minimization algorithm.

  • pst – Optional pointer to a statistics structure for storing the resulting number of crossings.

Returns:

A copy of the input network with reordered ranks to reduce edge crossings.