cut_set#

This module provides tools for identifying and analyzing (arc) cut sets in planar diagrams.

Ana arc cut set in a graph or diagram is a set of edges (arcs) that, when removed, disconnects the graph into two or more disjoint components. These functions are designed to work with planar diagram representations, allowing the detection of such critical subsets of arcs and vertices.

We need arc cut sets for these operations: - detecting connected sus - detecting 3-sums - tangle decomposition & flyping

Functions

arc_cut_sets(k, order[, ...])

Computes the arc cut sets for a given planar diagram or oriented planar diagram.

cut_decomposition(k, cut_path[, vertex_maker])

Cuts the diagram into two parts by cutting each arc with an endpoint in the cut path.

cut_nodes(k)

Identify the cut vertices (articulation nodes) in a planar diagram.

find_arc_cut_set(k, order[, ...])

Find one arc cut set of size order in a planar diagram.
arc_cut_sets(k, order, minimum_partition_nodes=1, return_partition=False, return_ccw_ordered_endpoints=False)#

Computes the arc cut sets for a given planar diagram or oriented planar diagram. An arc cut sets is a set of arcs that, when removed, disconnects the diagram.

Parameters:

  • k (PlanarDiagram | OrientedPlanarDiagram) – A PlanarDiagram or OrientedPlanarDiagram instance of the diagram for which the arc cut sets are to be computed.

  • order (int) – An integer representing the order of the cut. The order defines the number of arcs of the arc cut sets.

  • minimum_partition_nodes – An integer specifying the minimum number of nodes required in each partition generated by the cuts. Default is 1.

  • return_partition – If True, also returns the partitions resulting after removing the arcs. Default is False.

  • return_ccw_ordered_endpoints – If True, the arcs are put in CCW order of the cut (slower), otherwise they are unordered (faster). Default is False.

Returns:

List – A list of arc cut sets computed based on the input parameters.

cut_nodes(k)#

Identify the cut vertices (articulation nodes) in a planar diagram.

A cut vertex is a node whose removal increases the number of connected components in the diagram. In the context of this function, it detects nodes that belong to multiple faces in the planar diagram.

Parameters:

k (PlanarDiagram) – The planar diagram to analyze.

Returns:

set – A set of nodes that are cut vertices (articulation points) in the diagram.

Return type:

set

find_arc_cut_set(k, order, minimum_partition_nodes=1)#

Find one arc cut set of size order in a planar diagram.

Parameters:

  • k (PlanarDiagram | OrientedPlanarDiagram) – The planar diagram or oriented planar diagram to analyze.

  • order (int) – The number of arcs in the desired cut set.

  • minimum_partition_nodes – The minimum required number of nodes in each resulting partition. Defaults to 1.

Returns:

A tuple containing the selected arcs if an arc cut set satisfying the criteria is found, or None if no such set exists.

cut_decomposition(k, cut_path, vertex_maker='cut')#

Cuts the diagram into two parts by cutting each arc with an endpoint in the cut path. The first component of the cut contains the nodes from the cut path.

Parameters:
Return type:

list