"""
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