Source code for pyrigi.graphDB

"""
This is a module for providing common types of graphs.
"""

import networkx as nx

import pyrigi._input_check as _input_check
from pyrigi.graph import Graph
from pyrigi.data_type import Vertex, Sequence
from itertools import combinations


[docs] def Cycle(n: int) -> Graph: """Return the cycle graph on ``n`` vertices.""" return Graph(nx.cycle_graph(n))
[docs] def Complete(n: int = None, vertices: Sequence[Vertex] = None) -> Graph: """ Return the complete graph on ``n`` vertices. The vertex labels can also be specified explicitly via the keyword ``vertices``. Parameters ---------- n: The number of vertices. vertices: An optional parameter for the vertices. Examples -------- >>> print(Complete(5)) 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]] >>> print(Complete(5, [0, 1, 2, 3, 4])) 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]] >>> print(Complete(vertices=['a', 'b', 'c', 'd'])) Graph with vertices ['a', 'b', 'c', 'd'] and edges [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']] """ # noqa: E501 if vertices is None: _input_check.integrality_and_range(n, "number of vertices n", min_val=0) return Graph(nx.complete_graph(n)) if n is None: n = len(vertices) _input_check.equal(len(vertices), n, "number of `vertices`", "the parameter `n`") edges = list(combinations(vertices, 2)) return Graph.from_vertices_and_edges(vertices, edges)
[docs] def Path(n: int) -> Graph: """Return the path graph with ``n`` vertices.""" _input_check.integrality_and_range(n, "number of vertices n", min_val=0) return Graph(nx.path_graph(n))
[docs] def CompleteBipartite(n1: int, n2: int) -> Graph: """Return the complete bipartite graph on ``n1+n2`` vertices.""" _input_check.integrality_and_range(n1, "number of vertices n1", min_val=1) _input_check.integrality_and_range(n2, "number of vertices n2", min_val=1) return Graph(nx.complete_multipartite_graph(n1, n2))
[docs] def K33plusEdge() -> Graph: """Return the complete bipartite graph on 3+3 vertices with an extra edge.""" G = CompleteBipartite(3, 3) G.add_edge(0, 1) return G
[docs] def Diamond() -> Graph: """Return the complete graph on 4 vertices minus an edge.""" return Graph([(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)])
[docs] def ThreePrism() -> Graph: """Return the 3-prism graph.""" return Graph( [(0, 1), (1, 2), (0, 2), (3, 4), (4, 5), (3, 5), (0, 3), (1, 4), (2, 5)] )
[docs] def ThreePrismPlusEdge() -> Graph: """Return the 3-prism graph with one extra edge.""" return Graph( [(0, 1), (1, 2), (0, 2), (3, 4), (4, 5), (3, 5), (0, 3), (1, 4), (2, 5), (0, 5)] )
[docs] def CubeWithDiagonal() -> Graph: """Return the graph given by the skeleton of the cube with a main diagonal.""" return Graph( [(0, 1), (1, 2), (2, 3), (0, 3)] + [(4, 5), (5, 6), (6, 7), (4, 7)] + [(0, 4), (1, 5), (2, 6), (3, 7)] + [(0, 6)] )
[docs] def DoubleBanana(dim: int = 3, t: int = 2) -> Graph: r""" Return the ``dim``-dimensional double banana graph. Definitions ----- :prf:ref:`Generalized Double Banana <def-generalized-double-banana>` Parameters ---------- dim: An integer greater or equal 3. t: An integer such that ``2 <= t <= dim-1``. Examples -------- >>> print(DoubleBanana()) Graph with vertices [0, 1, 2, 3, 4, 5, 6, 7] and edges [[0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [3, 4], [5, 6], [5, 7], [6, 7]] >>> print(DoubleBanana(dim = 4)) Graph with vertices [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and edges [[0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [0, 9], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5], [6, 7], [6, 8], [6, 9], [7, 8], [7, 9], [8, 9]] """ # noqa: E501 _input_check.integrality_and_range(dim, "dimension dim", min_val=3) _input_check.integrality_and_range(t, "parameter t", min_val=2) _input_check.smaller_equal(t, dim - 1, "parameter t", "dim - 1") r = (dim + 2) - t Kt = Complete(t) Kt1 = Kt.copy() for i in range(t, dim + 2): Kt1.add_edges([[i, v] for v in Kt1.nodes]) Kt2 = Kt.copy() for i in range(dim + 2, dim + 2 + r): Kt2.add_edges([[i, v] for v in Kt2.nodes]) return Kt1.sum_t(Kt2, [0, 1], t)
[docs] def CompleteMinusOne(n: int) -> Graph: """Return the complete graph on ``n`` vertices minus one edge.""" G = Complete(n) G.delete_edge((0, 1)) return G
[docs] def Octahedral() -> Graph: """Return the graph given by the skeleton of an octahedron.""" return Graph( [ (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5), ] )
[docs] def Icosahedral() -> Graph: """Return the graph given by the skeleton of an icosahedron.""" return Graph(nx.icosahedral_graph().edges)
[docs] def Dodecahedral() -> Graph: """Return the graph given by the skeleton of a dodecahedron.""" return Graph( [ (0, 8), (0, 12), (0, 16), (1, 8), (1, 13), (1, 18), (2, 10), (2, 12), (2, 17), (3, 9), (3, 14), (3, 16), (4, 10), (4, 13), (4, 19), (5, 9), (5, 15), (5, 18), (6, 11), (6, 14), (6, 17), (7, 11), (7, 15), (7, 19), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), ] )
[docs] def Frustum(n: int) -> Graph: """ Return the ``n``-Frustum graph. Definitions ----------- :prf:ref:`n-Frustum graph <def-n-frustum>` """ return Graph( [(j, (j + 1) % n) for j in range(0, n)] + [(j, (j + 1 - n) % n + n) for j in range(n, 2 * n)] + [(j, j + n) for j in range(0, n)] )
[docs] def K66MinusPerfectMatching() -> Graph: """ Return the complete bipartite graph minus a perfect matching. A matching is formed by six non-incident edges. """ G = CompleteBipartite(6, 6) G.delete_edges([(i, i + 6) for i in range(0, 6)]) return G
[docs] def CnSymmetricFourRegular(n: int = 8) -> Graph: """ Return a $C_n$-symmetric 4-regular graph. The value ``n`` must be even and at least 8. Definitions ----------- * :prf:ref:`Example with a free group action <def-Cn-symmetric>` """ _input_check.integrality_and_range(n, "number of vertices n", min_val=8) if not n % 2 == 0: raise ValueError( "To generate this graph, the cyclic group " + "must have an even order!" ) G = Graph() G.add_edges([(0, n - 1), (n - 3, 0), (n - 2, 1), (n - 1, 2)]) for i in range(1, n): G.add_edges([(i, i - 1)]) for i in range(n - 3): G.add_edge(i, i + 3) return G
[docs] def CnSymmetricWithFixedVertex(n: int = 8) -> Graph: """ Return a $C_n$-symmetric graph with a fixed vertex. The value ``n`` must be even and at least 8. The returned graph satisfies the expected symmetry-adapted Laman count for rotation but is (generically) infinitesimally flexible. Definitions ----------- :prf:ref:`Example with joint at origin <def-Cn-symmetric-joint-at-origin>` """ _input_check.integrality_and_range(n, "order of cyclic group n", min_val=8) if not n % 2 == 0: raise ValueError( "To generate this graph, the cyclic group " + "must have an even order!" ) G = CnSymmetricFourRegular(n) G.add_edges([(0, n), (n, 2 * n), (n + 1, 2 * n - 1), (n, 2 * n - 2)]) for i in range(1, n): G.add_edges([(i, i + n), (2 * n, i + n), ((i + 1) + n, (i + 1) + n - 2)]) return G
[docs] def ThreeConnectedR3Circuit() -> Graph: """ Return a 3-connected $R_3$-circuit. The returned graph is hypothesized to be the smallest 3-connected $R_3$-circuit. """ return Graph( [ (0, 1), (0, 2), (0, 3), (0, 5), (0, 6), (0, 8), (0, 9), (0, 11), (0, 12), (1, 2), (1, 3), (1, 4), (1, 10), (1, 11), (1, 12), (2, 3), (2, 4), (3, 4), (4, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 7), (7, 8), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10), (10, 11), (10, 12), (11, 12), ] )
[docs] def Wheel(n: int) -> Graph: """ Create the wheel graph on ``n+1`` vertices. """ _input_check.integrality_and_range(n + 1, "number of vertices n+1", min_val=4) G = Cycle(n) G.add_edges([(i, n) for i in range(n)]) return G