Main classes

Top-level public API objects:

• scanwidth.DAG

• scanwidth.Extension

• scanwidth.TreeExtension

• scanwidth.edge_scanwidth()

• scanwidth.node_scanwidth()

class scanwidth.DAG(graph: DiGraph | None = None)

Bases: object

Core directed acyclic graph data object.

The DAG is a lightweight wrapper around a networkx.DiGraph intended purely as a data carrier. It exposes no algorithm methods; algorithms are implemented in dedicated solver classes in scanwidth.edge_scanwidth.

Parameters:

graph (Optional[nx.DiGraph], optional) – NetworkX directed graph instance. If None, an empty directed graph is created.

Raises:

• TypeError – If graph is not a networkx.DiGraph.

• ValueError – If graph is directed but contains at least one cycle.

property graph: DiGraph

Return the underlying networkx.DiGraph.

Returns:

Internal directed graph.

Return type:

nx.DiGraph

class scanwidth.Extension(dag: DAG, ordering: List)

Bases: object

Class for an extension of a graph, starting with the leafnodes.

canonical_tree_extension() → TreeExtension

Return the canonical tree extension.

This forwards to to_canonical_tree_extension().

property dag: DAG

Return the underlying DAG object.

edge_scanwidth() → int

Calculate edge scanwidth of the extension ordering for the DAG.

Returns:

The scanwidth value.

Return type:

int

edge_scanwidth_bag(vertex: object) → set

Return the set of edges in the edge scanwidth bag for a vertex.

Parameters:

vertex (object) – Vertex in the extension order ordering.

Returns:

Set of edges in SW_v.

Return type:

set

Raises:

ValueError – If vertex is not in the extension order.

node_scanwidth() → int

Calculate node scanwidth of the extension ordering for the DAG.

Returns:

The node scanwidth value.

Return type:

int

node_scanwidth_bag(vertex: object) → set

Return node scanwidth bag for a vertex in the extension ordering.

Parameters:

vertex (object) – Vertex in the extension order ordering.

Returns:

Set of parent vertices of edges in SW_v.

Return type:

set

Raises:

ValueError – If vertex is not in the extension order.

property ordering: List

Return the extension order.

to_canonical_tree_extension() → TreeExtension

Create canonical tree extension with same edge scanwidth as ordering.

Returns:

A TreeExtension object with the same scanwidth as this extension.

Return type:

TreeExtension

class scanwidth.TreeExtension(dag: DAG, tree: DiGraph)

Bases: object

Class for a tree extension of a graph.

property dag: DAG

Return the underlying DAG object.

edge_scanwidth() → int

Calculate the edge scanwidth of the tree extension for the DAG.

Returns:

The scanwidth value.

Return type:

int

edge_scanwidth_bag(vertex: object) → set

Return the set of edges in the edge scanwidth bag for a tree vertex.

Parameters:

vertex (object) – Vertex of the tree extension.

Returns:

Set of edges in GW_v.

Return type:

set

Raises:

ValueError – If vertex is not a vertex of self.tree.

edge_scanwidth_bags() → dict[object, set[tuple[object, object]]]

Return edge scanwidth bags for all tree vertices.

Returns:

Mapping from tree vertex to its edge scanwidth bag.

Return type:

dict[object, set[tuple[object, object]]]

is_canonical() → bool

Report whether the tree extension is canonical.

Returns:

True if the tree extension is canonical, False otherwise.

Return type:

bool

node_scanwidth() → int

Calculate node scanwidth of the tree extension for the DAG.

Returns:

The node scanwidth value.

Return type:

int

node_scanwidth_bag(vertex: object) → set

Return node scanwidth bag for a tree extension vertex.

Parameters:

vertex (object) – Vertex of the tree extension.

Returns:

Set of parent vertices of edges in GW_v.

Return type:

set

Raises:

ValueError – If vertex is not a vertex of self.tree.

node_scanwidth_bags() → dict[object, set[object]]

Return node scanwidth bags for all tree vertices.

Returns:

Mapping from tree vertex to its node scanwidth bag.

Return type:

dict[object, set[object]]

to_extension() → Extension

Return an extension of the tree.

If the tree extension is canonical, this extension gives the same scanwidth.

Returns:

An Extension object corresponding to this tree extension.

Return type:

Extension

property tree: DiGraph

Return the tree extension graph.

The detailed function API for scanwidth.edge_scanwidth() and scanwidth.node_scanwidth() is documented on the dedicated pages: Edge-scanwidth and Node-scanwidth.