Separating Sets

This module provides algorithms related to separating sets.

It includes an algorithm for a stable separating set search in a 2-flexible graph according to Algorithm 1 in [CGH+24].

pyrigi.graph._other.separating_set.is_separating_set(graph, vertices, use_copy=True)[source]

Return whether vertices are a separating set.

Definitions

Separating set

Parameters:

  • graph (Graph)

  • vertices (Collection[Vertex]) – The vertices to check.

  • use_copy (bool) – If True (default), create a copy of the graph before the vertices are removed and connectivity is checked. Otherwise, the graph is modified in-place. In that case, some metadata may be lost.

Return type:

bool

Examples

>>> from pyrigi.graph import Graph
>>> import pyrigi.graphDB as graphs
>>> H = graphs.Cycle(5)
>>> is_separating_set(H, [1,3])
True
>>> G = Graph([[0,1],[1,2],[2,3],[2,4],[4,3],[4,5]])
>>> is_separating_set(G, [2])
True
>>> is_separating_set(G, [3])
False
>>> is_separating_set(G, [3,4])
True
pyrigi.graph._other.separating_set.is_stable_separating_set(graph, vertices, use_copy=True)[source]

Return whether vertices are a stable separating set.

See is_stable_set() and is_separating_set() for the description of the parameters.

Definitions

Parameters:
Return type:

bool

Examples

>>> import pyrigi.graphDB as graphs
>>> H = graphs.Cycle(5)
>>> is_stable_separating_set(H, [1,3])
True
>>> is_stable_separating_set(H, [1,2])
False
pyrigi.graph._other.separating_set.is_stable_set(graph, vertices, certificate=False)[source]

Return whether given vertices form a stable set.

If the set is not stable, a pair of adjacent vertices is also returned depending on certificate.

Definitions

Stable set

Parameters:

  • graph (Graph)

  • vertices (Collection[Vertex]) – A set of vertices to be checked.

  • certificate (bool) – If False, a boolean is returned whether the set is stable or not. If True, a tuple is returned where the first boolean states whether the set is stable and the second item gives a pair of vertices contradicting the stable property if applicable (otherwise None).

Return type:

bool | tuple[bool, Optional[Edge]]

Examples

>>> import pyrigi.graphDB as graphs
>>> H = graphs.Cycle(5)
>>> is_stable_set(H, [1,3])
True
>>> is_stable_set(H, [1,3], certificate=False)
True
>>> is_stable_set(H, [1,3], certificate=True)
(True, None)
>>> is_stable_set(H, [1,2], certificate=True)
(False, (1, 2))
>>> is_stable_set(H, [0,2,4], certificate=True)
(False, (0, 4))
pyrigi.graph._other.separating_set.is_uv_separating_set(graph, vertices, u, v, use_copy=True)[source]

Return whether vertices separate the vertices u and v.

Definitions

Separating set

Parameters:

  • graph (Graph)

  • vertices (Collection[Vertex]) – The set of vertices to be checked to separate u and v. If u or v is contained in vertices, ValueError is raised.

  • u (Vertex)

  • v (Vertex)

  • use_copy (bool) – If True (default), create a copy of the graph before the vertices are removed and connectivity is checked. Otherwise, the graph is modified in-place. In that case, some metadata may be lost.

Return type:

bool

Examples

>>> import pyrigi.graphDB as graphs
>>> H = graphs.Cycle(5)
>>> is_uv_separating_set(H, [1,3], 0, 2)
True
>>> is_uv_separating_set(H, [2,4], 0, 1)
False
pyrigi.graph._other.separating_set.stable_separating_set(graph, u=None, v=None, check_flexible=True, check_connected=True, check_distinct_rigid_components=True)[source]

Find a stable separating set if the graph is 2-flexible.

If two vertices u and v that are not in the same 2-rigid component are provided, then the returned stable separating set separates them. If a single vertex u is specified, the returned stable separating set avoids u, provided u is not contained in all 2-rigid components. Algorithm 1 in [CGH+24] is used. An empty set can be returned when the graph is disconnected.

Definitions

Parameters:

  • graph (Graph)

  • u (Optional[Vertex]) – See the description above, an arbitrary vertex is chosen if none is specified.

  • v (Optional[Vertex]) – See the description above, a suitable vertex is chosen if none is specified. It cannot be in the same 2-rigid component as u.

  • check_flexible (bool) – If True, it is checked that the graph is 2-flexible as the algorithm only works for those. If False and the graph is 2-rigid, the behaviour might be arbitrary.

  • check_connected (bool) – If True, checks for graph connectivity are run and the result may alter based on them. If False and the graph is disconnected, the behaviour might be arbitrary.

  • check_distinct_rigid_components (bool) – If True, it is checked that u and v are in different 2-rigid components. If False, both u and v must be specified.

Return type:

set[Vertex]