Node-scanwidth#

Public function#

scanwidth.node_scanwidth(dag: DAG, algorithm: str = 'xp', reduce: bool = True, **kwargs: object) → Tuple[int, Extension]#

Compute node scanwidth of a DAG using the selected algorithm.

Parameters:

  • dag (DAG) – Input directed acyclic graph.

  • algorithm (str, optional) –

    Solver name. Supported values are:

    • "xp": exact XP algorithm with increasing k.

    • "brute_force": exact brute-force search over all extensions.

    • "ilp": exact MILP solver with backend selection (backend="scipy" or backend="gurobi").

    • "greedy": greedy heuristic.

    • "random": random extension heuristic.

    • "simulated_annealing": simulated-annealing heuristic.

  • reduce (bool, optional) – If True, apply reduction rules before solving. Default is True.

  • **kwargs (object) – Algorithm-specific keyword arguments plus optional reducer_config=ReducerConfig(...). Set ReducerConfig(parallel_sblocks=True) to solve independent s-blocks concurrently.

Returns:

Node-scanwidth value and the corresponding extension.

Return type:

Tuple[int, Extension]

Examples

>>> import networkx as nx
>>> from scanwidth import DAG, node_scanwidth
>>> from scanwidth.node_scanwidth.reduction.config import ReducerConfig
>>> graph = nx.DiGraph([(1, 3), (2, 3)])
>>> value, extension = node_scanwidth(
...     DAG(graph),
...     algorithm="brute_force",
...     reducer_config=ReducerConfig(parallel_sblocks=True, sblock_max_workers=2),
... )
>>> value == extension.node_scanwidth()
True

Module details#

Public API entry point for node-scanwidth algorithms.

scanwidth.node_scanwidth.api.node_scanwidth(dag: DAG, algorithm: str = 'xp', reduce: bool = True, **kwargs: object) → Tuple[int, Extension]#

Compute node scanwidth of a DAG using the selected algorithm.

Parameters:

  • dag (DAG) – Input directed acyclic graph.

  • algorithm (str, optional) –

    Solver name. Supported values are:

    • "xp": exact XP algorithm with increasing k.

    • "brute_force": exact brute-force search over all extensions.

    • "ilp": exact MILP solver with backend selection (backend="scipy" or backend="gurobi").

    • "greedy": greedy heuristic.

    • "random": random extension heuristic.

    • "simulated_annealing": simulated-annealing heuristic.

  • reduce (bool, optional) – If True, apply reduction rules before solving. Default is True.

  • **kwargs (object) – Algorithm-specific keyword arguments plus optional reducer_config=ReducerConfig(...). Set ReducerConfig(parallel_sblocks=True) to solve independent s-blocks concurrently.

Returns:

Node-scanwidth value and the corresponding extension.

Return type:

Tuple[int, Extension]

Examples

>>> import networkx as nx
>>> from scanwidth import DAG, node_scanwidth
>>> from scanwidth.node_scanwidth.reduction.config import ReducerConfig
>>> graph = nx.DiGraph([(1, 3), (2, 3)])
>>> value, extension = node_scanwidth(
...     DAG(graph),
...     algorithm="brute_force",
...     reducer_config=ReducerConfig(parallel_sblocks=True, sblock_max_workers=2),
... )
>>> value == extension.node_scanwidth()
True

Solver classes#

Node-scanwidth solver hierarchy.

class scanwidth.node_scanwidth.solver.BruteForceSolver#

Bases: Solver

Exhaustive search over all topological orders for node scanwidth.

solve(dag: DAG) → SolverResult#

Solve node scanwidth by exhaustive search.

class scanwidth.node_scanwidth.solver.GreedySolver#

Bases: Solver

Greedy node-scanwidth solver.

solve(dag: DAG) → SolverResult#

Solve node scanwidth using the greedy heuristic.

class scanwidth.node_scanwidth.solver.ILPSolver(backend: Literal['scipy', 'gurobi'] = 'scipy', time_limit: float | None = None, mip_rel_gap: float = 0.0, verbose: bool = False)#

Bases: Solver

Exact node-scanwidth solver based on an ILP formulation.

Parameters:

  • backend (Literal["scipy", "gurobi"], optional) – MILP backend used to solve the ILP model.

  • time_limit (Optional[float], optional) – Time limit in seconds for the MILP solve.

  • mip_rel_gap (float, optional) – Relative MIP gap tolerance for the selected backend.

  • verbose (bool, optional) – If True, enable backend output.

backend: Literal['scipy', 'gurobi'] = 'scipy'#
mip_rel_gap: float = 0.0#
solve(dag: DAG) → SolverResult#

Solve node scanwidth exactly via ILP.

time_limit: float | None = None#
verbose: bool = False#
class scanwidth.node_scanwidth.solver.RandomSolver(seed: int = 42)#

Bases: Solver

Random-extension node-scanwidth solver.

seed: int = 42#
solve(dag: DAG) → SolverResult#

Generate a random extension and compute its node scanwidth.

class scanwidth.node_scanwidth.solver.SimulatedAnnealingSolver(max_iter: int = 100, p_in: float = 0.9, p_stop: float = 0.01, init_ext: str | Extension = 'greedy', verbose: bool = False, seed: int = 42)#

Bases: Solver

Simulated-annealing node-scanwidth solver.

init_ext: str | Extension = 'greedy'#
max_iter: int = 100#
p_in: float = 0.9#
p_stop: float = 0.01#
seed: int = 42#
solve(dag: DAG) → SolverResult#

Solve node scanwidth using simulated annealing.

verbose: bool = False#
class scanwidth.node_scanwidth.solver.XpSolver(k: int | None = None)#

Bases: Solver

Exact XP node-scanwidth solver using increasing k.

k: int | None = None#
solve(dag: DAG) → SolverResult#

Solve node scanwidth exactly using the XP algorithm.

Reduction configuration and reducer#

Configuration for node-scanwidth reduction pipeline.

class scanwidth.node_scanwidth.reduction.config.ReducerConfig(use_sblocks: bool = True, use_single_edge_shortcut: bool = True, use_single_root_cycle_rule: bool = True, use_tree_shortcut: bool = True, use_chain_suppression: bool = True, use_reticulation_path_shortcut: bool = True, parallel_sblocks: bool = False, sblock_max_workers: int | None = None)#

Bases: object

Toggle reduction rules for scanwidth.node_scanwidth.reduction.Reducer.

Parameters:

  • use_sblocks (bool, optional) – If True, decompose into s-block subproblems.

  • use_single_edge_shortcut (bool, optional) – If True, solve two-vertex single-edge blocks directly.

  • use_single_root_cycle_rule (bool, optional) – If True, solve single-root cycle-like blocks directly with node scanwidth 2 (same structure as edge reducer).

  • use_tree_shortcut (bool, optional) – If True, solve directed rooted trees directly.

  • use_chain_suppression (bool, optional) – If True, apply chain-parent suppression on blocks before solving.

  • use_reticulation_path_shortcut (bool, optional) – If True, apply the reticulation-path closed-form shortcut on eligible non-root s-blocks after chain suppression.

  • parallel_sblocks (bool, optional) – If True, solve independent s-block subproblems concurrently.

  • sblock_max_workers (Optional[int], optional) – Maximum number of workers used for s-block parallelization. None delegates worker selection to the executor default.

parallel_sblocks: bool = False#
sblock_max_workers: int | None = None#
use_chain_suppression: bool = True#
use_reticulation_path_shortcut: bool = True#
use_sblocks: bool = True#
use_single_edge_shortcut: bool = True#
use_single_root_cycle_rule: bool = True#
use_tree_shortcut: bool = True#

Reducer abstraction for node-scanwidth algorithms.

class scanwidth.node_scanwidth.reduction.reducer.Reducer(config: ReducerConfig = ReducerConfig(use_sblocks=True, use_single_edge_shortcut=True, use_single_root_cycle_rule=True, use_tree_shortcut=True, use_chain_suppression=True, use_reticulation_path_shortcut=True, parallel_sblocks=False, sblock_max_workers=None))#

Bases: object

Apply node-scanwidth reductions and delegate each block to a solver.

config: ReducerConfig = ReducerConfig(use_sblocks=True, use_single_edge_shortcut=True, use_single_root_cycle_rule=True, use_tree_shortcut=True, use_chain_suppression=True, use_reticulation_path_shortcut=True, parallel_sblocks=False, sblock_max_workers=None)#
reduce_and_solve(dag: DAG, solver: Solver) → SolverResult#

Solve node scanwidth via reduction pipeline.