Extensions

This module provides algorithms related to k-extensions of graphs.

pyrigi.graph._constructions.extensions.all_extensions(graph, dim=2, only_non_isomorphic=False, k_min=0, k_max=None)[source]

Return an iterator over all dim-dimensional extensions.

All possible k-extensions for k such that k_min <= k <= k_max are considered.

Definitions

k-extension

Parameters:

  • graph (Graph)

  • dim (int)

  • only_non_isomorphic (bool) – If True, only one graph per isomorphism class is included.

  • k_min (int) – Minimal value of k for the k-extensions (default 0).

  • k_max (int | None) – Maximal value of k for the k-extensions (default dim - 1).

Return type:

Iterable[Graph]

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> type(all_extensions(G))
<class 'generator'>
>>> len(list(all_extensions(G)))
6
>>> len(list(all_extensions(G, only_non_isomorphic=True)))
1

>>> diamond_graph = graphs.Diamond()
>>> result1 = list(all_extensions(diamond_graph, 2, only_non_isomorphic=True, k_min=1, k_max=1))  # noqa: E501
>>> result2 = list(all_k_extensions(diamond_graph, 1, 2, only_non_isomorphic=True))
>>> result1 == result2
True

Notes

It turns out that possible errors on bad input parameters are only raised, when the output iterator is actually used, not when it is created.

pyrigi.graph._constructions.extensions.all_k_extensions(graph, k, dim=2, only_non_isomorphic=False)[source]

Return an iterator over all possible dim-dimensional k-extensions.

Definitions

k-extension

Parameters:

  • graph (Graph)

  • k (int)

  • dim (int)

  • only_non_isomorphic (bool) – If True, only one graph per isomorphism class is included.

Return type:

Iterable[Graph]

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> type(all_k_extensions(G, 0))
<class 'generator'>
>>> len(list(all_k_extensions(G, 0)))
3
>>> len(list(all_k_extensions(G, 0, only_non_isomorphic=True)))
1

>>> diamond_graph = graphs.Diamond()
>>> len(list(all_k_extensions(diamond_graph, 1, 2, only_non_isomorphic=True)))
2

Notes

It turns out that possible errors on bad input parameters are only raised, when the output iterator is actually used, not when it is created.

pyrigi.graph._constructions.extensions.extension_sequence(graph, dim=2, return_type='extensions')[source]

Compute a sequence of dim-dimensional extensions.

The k-extensions for k from 0 to 2 * dim - 1 are considered. The sequence then starts from a complete graph on dim vertices. If no such sequence exists, None is returned.

The function returns either a sequence of graphs, data on the extension, or both.

Note that for dimensions larger than two, the extensions are not always preserving rigidity.

Definitions

k-extension

Parameters:

  • graph (Graph)

  • dim (int) – The dimension in which the extensions are created.

  • return_type (str) –

    Can have values "graphs", "extensions" or "both".

    If "graphs", then the sequence of graphs obtained from the extensions is returned.

    If "extensions", then an initial graph and a sequence of extensions of the form [k, vertices, edges, new_vertex] as needed for the input of k_extension() is returned.

    If "both", then an initial graph and a sequence of pairs [graph, extension], where the latter has the form from above, is returned.

Return type:

list[Graph] | list | None

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> extension_sequence(G, return_type="graphs")
[Graph.from_vertices_and_edges([1, 2], [(1, 2)]), Graph.from_vertices_and_edges([0, 1, 2], [(0, 1), (0, 2), (1, 2)])]
>>> G = graphs.Diamond()
>>> print(G)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [2, 3]]
>>> extension_sequence(G, return_type="graphs")
[Graph.from_vertices_and_edges([2, 3], [(2, 3)]), Graph.from_vertices_and_edges([0, 2, 3], [(0, 2), (0, 3), (2, 3)]), Graph.from_vertices_and_edges([0, 1, 2, 3], [(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)])]
>>> extension_sequence(G, return_type="extensions")
[Graph.from_vertices_and_edges([2, 3], [(2, 3)]), [0, [3, 2], [], 0], [0, [0, 2], [], 1]]
pyrigi.graph._constructions.extensions.has_extension_sequence(graph, dim=2)[source]

Return if there exists a sequence of dim-dimensional extensions.

The function returns whether there exists a sequence of extensions as described in extension_sequence().

Definitions

k-extension

Parameters:

  • graph (Graph)

  • dim (int) – The dimension in which the extensions are created.

Return type:

bool

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.ThreePrism()
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [1, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> has_extension_sequence(G)
True
>>> G = graphs.CompleteBipartite(1, 2)
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2]]
>>> has_extension_sequence(G)
False
pyrigi.graph._constructions.extensions.k_extension(graph, k, vertices, edges, new_vertex=None, dim=2, inplace=False)[source]

Return a dim-dimensional k-extension.

See also zero_extension() and one_extension().

Definitions

k-extension

Parameters:

  • graph (Graph)

  • k (int)

  • vertices (Sequence[Vertex]) – A new vertex is connected to these vertices. All the vertices must be contained in the graph and there must be dim + k of them.

  • edges (Sequence[Edge]) – A list of edges that are deleted. The endvertices of all the edges must be contained in the list vertices. The edges must be contained in the graph and there must be k of them.

  • new_vertex (Vertex) – Newly added vertex is named according to this parameter. If None, the name is set as the lowest possible integer value greater or equal than the number of nodes.

  • dim (int) – The dimension in which the k-extension is created.

  • inplace (bool) – If True, the graph is modified, otherwise a new modified graph is created, while the original graph remains unchanged (default).

Return type:

Graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(5)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
>>> H = k_extension(G, 2, [0, 1, 2, 3], [[0, 1], [0,2]])
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 3], [0, 4], [0, 5], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5]]
>>> G = graphs.Complete(5)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
>>> H = k_extension(G, 2, [0, 1, 2, 3, 4], [[0, 1], [0,2]], dim = 3)
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 3], [0, 4], [0, 5], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> G = graphs.Path(6)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
>>> H = k_extension(G, 2, [0, 1, 2], [[0, 1], [1,2]], dim = 1, inplace = True);
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5, 6] and edges [[0, 6], [1, 6], [2, 3], [2, 6], [3, 4], [4, 5]]
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5, 6] and edges [[0, 6], [1, 6], [2, 3], [2, 6], [3, 4], [4, 5]]
pyrigi.graph._constructions.extensions.one_extension(graph, vertices, edge, new_vertex=None, dim=2, inplace=False)[source]

Return a dim-dimensional 1-extension.

Definitions

1-extension

Parameters:

  • graph (Graph)

  • vertices (Sequence[Vertex]) – A new vertex is connected to these vertices. All the vertices must be contained in the graph and there must be dim + 1 of them.

  • edge (Edge) – An edge with endvertices from the list vertices that is deleted. The edge must be contained in the graph.

  • new_vertex (Vertex) – Newly added vertex is named according to this parameter. If None, the name is set as the lowest possible integer value greater or equal than the number of nodes.

  • dim (int) – The dimension in which the 1-extension is created.

  • inplace (bool) – If True, the graph is modified, otherwise a new modified graph is created, while the original graph remains unchanged (default).

Return type:

Graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> H = one_extension(G, [0, 1, 2], [0, 1])
>>> print(H)
Graph with vertices [0, 1, 2, 3] and edges [[0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> G = graphs.ThreePrism()
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [1, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> H = one_extension(G, [0, 1], [0, 1], dim=1)
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5, 6] and edges [[0, 2], [0, 3], [0, 6], [1, 2], [1, 4], [1, 6], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> G = graphs.CompleteBipartite(3, 2)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 3], [0, 4], [1, 3], [1, 4], [2, 3], [2, 4]]
>>> H = one_extension(G, [0, 1, 2, 3, 4], [0, 3], dim=4, inplace = True)
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]]
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]]
pyrigi.graph._constructions.extensions.zero_extension(graph, vertices, new_vertex=None, dim=2, inplace=False)[source]

Return a dim-dimensional 0-extension.

Definitions

0-extension

Parameters:

  • graph (Graph)

  • vertices (Sequence[Vertex]) – A new vertex is connected to these vertices. All the vertices must be contained in the graph and there must be dim of them.

  • new_vertex (Vertex) – Newly added vertex is named according to this parameter. If None, the name is set as the lowest possible integer value greater or equal than the number of nodes.

  • dim (int) – The dimension in which the 0-extension is created.

  • inplace (bool) – If True, the graph is modified, otherwise a new modified graph is created, while the original graph remains unchanged (default).

Return type:

Graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> H = zero_extension(G, [0, 2])
>>> print(H)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [2, 3]]
>>> H = zero_extension(G, [0, 2], 5)
>>> print(H)
Graph with vertices [0, 1, 2, 5] and edges [[0, 1], [0, 2], [0, 5], [1, 2], [2, 5]]
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> H = zero_extension(G, [0, 1, 2], 5, dim=3, inplace=True)
>>> print(H)
Graph with vertices [0, 1, 2, 5] and edges [[0, 1], [0, 2], [0, 5], [1, 2], [1, 5], [2, 5]]
>>> print(G)
Graph with vertices [0, 1, 2, 5] and edges [[0, 1], [0, 2], [0, 5], [1, 2], [1, 5], [2, 5]]