Edge-scanwidth#

Public function#

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

Compute edge 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 (default).

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

    • "two_partition": exact two-partition recursion.

    • "three_partition": exact 3-partition recursion.

    • "greedy": greedy heuristic.

    • "random": random extension.

    • "cut_splitting": recursive cut-splitting 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:

Edge-scanwidth value and the corresponding extension.

Return type:

Tuple[int, Extension]

Examples

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

Module details#

Public API entry point for edge-scanwidth algorithms.

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

Compute edge 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 (default).

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

    • "two_partition": exact two-partition recursion.

    • "three_partition": exact 3-partition recursion.

    • "greedy": greedy heuristic.

    • "random": random extension.

    • "cut_splitting": recursive cut-splitting 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:

Edge-scanwidth value and the corresponding extension.

Return type:

Tuple[int, Extension]

Examples

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

Solver classes#

Solver classes for edge scanwidth.

class scanwidth.edge_scanwidth.solver.BruteForceSolver#

Bases: Solver

Exhaustive search over all topological orders.

Enumerates every topological order of the input DAG, evaluates the scanwidth of the corresponding extension, and returns the best one. Only tractable on very small inputs.

solve(dag: DAG) → SolverResult#

Solve edge scanwidth by exhaustive search.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result.

Return type:

SolverResult

class scanwidth.edge_scanwidth.solver.CutSplittingSolver#

Bases: Solver

Recursive cut-splitting edge-scanwidth solver.

solve(dag: DAG) → SolverResult#

Solve edge scanwidth using recursive cut-splitting.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result.

Return type:

SolverResult

class scanwidth.edge_scanwidth.solver.GreedySolver#

Bases: Solver

Greedy edge-scanwidth solver.

solve(dag: DAG) → SolverResult#

Solve edge scanwidth using the greedy heuristic.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result.

Return type:

SolverResult

class scanwidth.edge_scanwidth.solver.RandomSolver(seed: int = 42)#

Bases: Solver

Random-extension edge-scanwidth solver.

Parameters:

seed (int, optional) – Random seed for reproducibility.

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

Generate a random extension and compute its edge scanwidth.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result.

Return type:

SolverResult

class scanwidth.edge_scanwidth.solver.RpswTable#

Bases: object

Memoization table for restricted partial scanwidth (rpsw).

Each entry maps a canonical key (derived from the root set of the current subgraph) to the best (rpsw, sigma) found for that set.

drop_infeasible(infinity: int) → None#

Remove entries whose cached rpsw equals infinity.

These entries correspond to subgraphs that were infeasible at the previous threshold and must be recomputed at the next one.

Parameters:

infinity (int) – Sentinel value representing infeasibility.

get(key: str) → Tuple[int, List] | None#

Return the cached value for key or None.

Parameters:

key (str) – Lookup key.

Returns:

The cached (rpsw, sigma) tuple or None.

Return type:

Optional[Tuple[int, List]]

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

Bases: Solver

Simulated-annealing edge-scanwidth solver.

Parameters:

  • max_iter (int, optional) – Maximum number of iterations. Default is 100.

  • p_in (float, optional) – Initial acceptance probability. Default is 0.9.

  • p_stop (float, optional) – Final acceptance probability. Default is 0.01.

  • init_ext (Union[str, Extension], optional) – Initial extension. Either an Extension or one of {"greedy", "cut", "random"}.

  • verbose (bool, optional) – If True, print progress. Default is True.

  • seed (int, optional) – Random seed. Default is 42.

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 edge scanwidth using simulated annealing.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result including the trace of best scanwidths under history.

Return type:

SolverResult

verbose: bool = True#
class scanwidth.edge_scanwidth.solver.ThreePartitionSolver#

Bases: Solver

Exact solver based on ordered 3-partition recursion.

Recursively splits the vertex set into an ordered 3-partition (L, W, R) with W halved at each step, under the constraint that there are no edges from W' to W \ W'.

solve(dag: DAG) → SolverResult#

Solve edge scanwidth using 3-partition recursion.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result.

Return type:

SolverResult

class scanwidth.edge_scanwidth.solver.TwoPartitionSolver#

Bases: Solver

Exact solver using recursive two-partition decomposition.

This corresponds to the component-splitting restricted-partial-scanwidth recursion without memoization.

solve(dag: DAG) → SolverResult#

Solve edge scanwidth exactly using two-partition recursion.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result.

Return type:

SolverResult

class scanwidth.edge_scanwidth.solver.XpSolver(k: int | None = None)#

Bases: Solver

Exact XP edge-scanwidth solver using increasing k.

Parameters:

k (Optional[int], optional) – If provided, solve the fixed-parameter variant at threshold k instead of iterating.

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

Solve edge scanwidth exactly using the XP algorithm.

Parameters:

dag (DAG) – Input graph instance.

Returns:

Standardized solver result.

Return type:

SolverResult

Reduction configuration and reducer#

Configuration for edge-scanwidth reduction pipeline.

class scanwidth.edge_scanwidth.reduction.config.ReducerConfig(use_sblocks: bool = True, use_single_edge_rule: bool = True, use_single_root_cycle_rule: bool = True, use_chain_suppression: bool = True, parallel_sblocks: bool = False, sblock_max_workers: int | None = None)#

Bases: object

Toggle reduction rules for scanwidth.edge_scanwidth.reduction.Reducer.

Parameters:

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

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

  • use_single_root_cycle_rule (bool, optional) – If True, solve single-root cycle blocks directly.

  • use_chain_suppression (bool, optional) – If True, apply chain-vertex suppression before delegating to solver.

  • 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_sblocks: bool = True#
use_single_edge_rule: bool = True#
use_single_root_cycle_rule: bool = True#

Reducer abstraction for edge-scanwidth algorithms.

class scanwidth.edge_scanwidth.reduction.reducer.Reducer(config: ReducerConfig = ReducerConfig(use_sblocks=True, use_single_edge_rule=True, use_single_root_cycle_rule=True, use_chain_suppression=True, parallel_sblocks=False, sblock_max_workers=None))#

Bases: object

Apply s-block reduction and delegate each subproblem to a solver.

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

Solve edge scanwidth via s-block decomposition.

Splits dag into s-blocks, handles trivial blocks directly, contracts chain vertices inside non-trivial blocks, and delegates the contracted subproblem to solver. Partial extensions are then reassembled into a single extension.

Parameters:

  • dag (DAG) – Input graph instance.

  • solver (Solver) – Solver instance used on each contracted, non-trivial block.

Returns:

Solver result for the full graph.

Return type:

SolverResult