Graphs¶

Module for rigidity related graph properties.

class pyrigi.graph.Graph(incoming_graph_data=None, **attr)[source]¶

Bases: Graph

Class representing a graph.

One option for incoming_graph_data is a list of edges. See networkx.Graph for the other input formats or use class methods from_vertices_and_edges() or from_vertices() when specifying the vertex set is needed.

Examples

>>> from pyrigi import Graph
>>> G = Graph([(0,1), (1,2), (2,3), (0,3)])
>>> print(G)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 3], [1, 2], [2, 3]]

>>> G = Graph()
>>> G.add_vertices([0,2,5,7,'a'])
>>> G.add_edges([(0,7), (2,5)])
>>> print(G)
Graph with vertices [0, 2, 5, 7, 'a'] and edges [[0, 7], [2, 5]]

Todo

Implement an alias for plotting. Graphical output in Jupyter. Graph names. Describe in the documentation when an output of a randomized algorithm is guaranteed to be correct. Switch from parameter combinatorial=True/False to algorithm=’combinatorial’/’randomized’…

Methods

Attribute getters

`edge_list`()	Return the list of edges.
`vertex_list`()	Return the list of vertices.

Class methods

`CompleteOnVertices`(vertices)	Generate a complete graph on `vertices`.
`from_adjacency_matrix`(M)	Create a graph from a given adjacency matrix.
`from_int`(N)	Return a graph given its integer representation.
`from_vertices`(vertices)	Create a graph with no edges from a list of vertices.
`from_vertices_and_edges`(vertices, edges)	Create a graph from a list of vertices and edges.

Graph manipulation

`add_edges`(edges)	Alias for `networkx.Graph.add_edges_from()`.
`add_vertex`(vertex)	Alias for `networkx.Graph.add_node()`.
`add_vertices`(vertices)	Alias for `networkx.Graph.add_nodes_from()`.
`all_k_extensions`(k[, dim, only_non_isomorphic])	Return an iterator over all possible dim-dimensional k-extensions.
`delete_edge`(edge)	Alias for `networkx.Graph.remove_edge()`
`delete_edges`(edges)	Alias for `networkx.Graph.remove_edges_from()`.
`delete_loops`()	Removes all the loops from the edges to get a loop free graph.
`delete_vertex`(vertex)	Alias for `networkx.Graph.remove_node()`.
`delete_vertices`(vertices)	Alias for `networkx.Graph.remove_nodes_from()`.
`intersection`(G2)	Return the intersection of self and G2.
`k_extension`(k, vertices, edges[, ...])	Return a dim-dimensional k-extension.
`one_extension`(vertices, edge[, new_vertex, ...])	Return a dim-dimensional 1-extension.
`sum_t`(G2, edge[, t])	Return the t-sum of self and G2 along the given edge.
`zero_extension`(vertices[, new_vertex, dim, ...])	Return a dim-dimensional 0-extension.

General graph theoretical properties

`adjacency_matrix`([vertex_order])	Return the adjacency matrix of the graph.
`degree_sequence`([vertex_order])	Return a list of degrees of the vertices of the graph.
`is_isomorphic`(graph)	Check whether two graphs are isomorphic.
`max_degree`()	Return the maximum of the vertex degrees.
`min_degree`()	Return the minimum of the vertex degrees.
`vertex_connectivity`()	Alias for `networkx.algorithms.connectivity.connectivity.node_connectivity()`.

Generic rigidity

`extension_sequence`([dim, return_solution])	Check the existence of a sequence of 0 and 1-extensions.
`is_globally_rigid`([dim, prob])	Check whether the graph is globally dim-rigid.
`is_k_redundantly_rigid`(k[, dim, ...])	Check whether the graph is k-redundantly (generically) dim-rigid.
`is_k_vertex_redundantly_rigid`(k[, dim, ...])	Check whether the graph is k-vertex redundantly (generically) dim-rigid.
`is_min_k_redundantly_rigid`(k[, dim, ...])	Check whether the graph is minimally k-redundantly (generically) dim-rigid.
`is_min_k_vertex_redundantly_rigid`(k[, dim, ...])	Check whether the graph is minimally k-vertex redundantly (generically) dim-rigid.
`is_min_redundantly_rigid`([dim, ...])	Check whether the graph is minimally redundantly (generically) dim-rigid.
`is_min_rigid`([dim, combinatorial, ...])	Check whether the graph is minimally (generically) dim-rigid.
`is_min_vertex_redundantly_rigid`([dim, ...])	Check whether the graph is minimally vertex redundantly (generically) dim-rigid.
`is_redundantly_rigid`([dim, combinatorial, prob])	Check whether the graph is redundantly (generically) dim-rigid.
`is_rigid`([dim, combinatorial, prob])	Check whether the graph is (generically) dim-rigid.
`is_vertex_redundantly_rigid`([dim, ...])	Check whether the graph is vertex redundantly (generically) dim-rigid.
`max_rigid_dimension`()	Compute the maximum dimension, in which a graph is generically rigid.
`number_of_realizations`([...])	Count the number of complex planar or spherical realizations of a minimally 2-rigid graph.
`rigid_components`([dim])	List the vertex sets inducing vertex-maximal rigid subgraphs.

Sparseness

`_build_pebble_digraph`(K, L)	Build and save the pebble digraph from scratch.
`_is_pebble_digraph_sparse`(K, L[, ...])	Check whether the pebble digraph has the same number of edges as the graph.
`_pebble_values_are_correct`(K, L)	Check if K and L satisfy pebble game conditions.
`is_sparse`(K, L[, algorithm, ...])	Check whether the graph is (K, L)-sparse.
`is_tight`(K, L[, algorithm, ...])	Check whether the graph is (K, L)-tight.
`spanning_sparse_subgraph`(K, L[, ...])	Return a maximal (K, L)-sparse subgraph.

Other

`layout`([layout_type])	Generate a placement of the vertices.
`plot`([placement, inf_flex, layout, ...])	Plot the graph.
`random_framework`([dim, rand_range])	Return framework with random realization.
`to_int`([vertex_order])	Return the integer representation of the graph.
`to_tikz`([layout_type, placement, ...])	Create a TikZ code for the graph.

Waiting for implementation

is_Rd_closed([dim])

Partially implemented

`is_Rd_circuit`([dim, ...])
`is_Rd_dependent`([dim, ...])
`is_Rd_independent`([dim, ...])

Notes

This class inherits the class networkx.Graph. Some of the inherited methods are for instance:

networkx.Graph.add_edge(u_of_edge, ...)

Add an edge between u and v.

Many of the NetworkX algorithms are implemented as functions, namely, a Graph instance has to be passed as the first parameter. See for instance:

`degree`(G[, nbunch, weight])	Returns a degree view of single node or of nbunch of nodes.
`neighbors`(G, n)	Returns an iterator over all neighbors of node n.
`non_neighbors`(graph, node)	Returns the non-neighbors of the node in the graph.
`subgraph`(G, nbunch)	Returns the subgraph induced on nodes in nbunch.
`edge_subgraph`(G, edges)	Returns a view of the subgraph induced by the specified edges.
`edges`(G[, nbunch])	Returns an edge view of edges incident to nodes in nbunch.
`is_k_edge_connected`(G, k, *[, backend])	Tests to see if a graph is k-edge-connected.
`is_connected`(G, *[, backend])	Returns True if the graph is connected, False otherwise.
`is_tree`(G, *[, backend])	Returns True if G is a tree.

The following links give more information on networkx.Graph functionality:

classmethod CompleteOnVertices(vertices)[source]¶

Generate a complete graph on vertices.

Examples

>>> Graph.CompleteOnVertices([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]]
>>> Graph.CompleteOnVertices(['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']]

Parameters:: vertices (List[Vertex])
Return type:: Graph

__add__(other)[source]¶

Return the union of self and other.

Definitions

Union of two graphs

Examples

>>> G = Graph([[0,1],[1,2],[2,0]])
>>> H = Graph([[2,3],[3,4],[4,2]])
>>> G + H
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 1], [0, 2], [1, 2], [2, 3], [2, 4], [3, 4]]

Parameters:: other (Graph)

__eq__(other)[source]¶

Return whether the other graph has the same vertices and edges.

Examples

>>> from pyrigi import Graph
>>> G = Graph([[1,2]])
>>> H = Graph([[2,1]])
>>> G == H
True

Note

graphs_equal(self, other)() behaves strangely, hence it is not used.

Parameters:: other (Graph)

__repr__()[source]¶

Return a representation.

Return type:: str

__str__()[source]¶

Return the string representation.

Return type:: str

add_edges(edges)[source]¶

Alias for networkx.Graph.add_edges_from().

Parameters:: edges (List[Edge])
Return type:: None

add_vertex(vertex)[source]¶

Alias for networkx.Graph.add_node().

Parameters:: vertex (Vertex)
Return type:: None

add_vertices(vertices)[source]¶

Alias for networkx.Graph.add_nodes_from().

Parameters:: vertices (List[Vertex])
Return type:: None

adjacency_matrix(vertex_order=None)[source]¶

Return the adjacency matrix of the graph.

Parameters:: vertex_order (List[Vertex] | None) – By listing vertices in the preferred order, the adjacency matrix can be computed in a way the user expects. If no vertex order is provided, vertex_list() is used.
Return type:: MutableDenseMatrix

Examples

>>> G = Graph([(0,1), (1,2), (1,3)])
>>> G.adjacency_matrix()
Matrix([
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 0],
[0, 1, 0, 0]])

Notes

networkx.linalg.graphmatrix.adjacency_matrix() requires scipy. To avoid unnecessary imports, the method is implemented here.

all_k_extensions(k, dim=2, only_non_isomorphic=False)[source]¶

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

Parameters:

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(G.all_k_extensions(0))
<class 'generator'>
>>> len(list(G.all_k_extensions(0)))
3
>>> len(list(G.all_k_extensions(0, only_non_isomorphic=True)))
1

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

degree_sequence(vertex_order=None)[source]¶

Return a list of degrees of the vertices of the graph.

Parameters:: vertex_order (List[Vertex] | None) – By listing vertices in the preferred order, the degree_sequence can be computed in a way the user expects. If no vertex order is provided, vertex_list() is used.
Return type:: List[int]

Examples

>>> G = Graph([(0,1), (1,2)])
>>> G.degree_sequence()
[1, 2, 1]

delete_edge(edge)[source]¶

Alias for networkx.Graph.remove_edge()

Parameters:: edge (Edge)
Return type:: None

delete_edges(edges)[source]¶

Alias for networkx.Graph.remove_edges_from().

Parameters:: edges (List[Edge])
Return type:: None

delete_loops()[source]¶

Removes all the loops from the edges to get a loop free graph.

Return type:: None

delete_vertex(vertex)[source]¶

Alias for networkx.Graph.remove_node().

Parameters:: vertex (Vertex)
Return type:: None

delete_vertices(vertices)[source]¶

Alias for networkx.Graph.remove_nodes_from().

Parameters:: vertices (List[Vertex])
Return type:: None

edge_list()[source]¶

Return the list of edges.

The output is sorted if possible, otherwise, the internal order is used instead.

Examples

>>> G = Graph([[0, 3], [3, 1], [0, 1], [2, 0]])
>>> G.edge_list()
[[0, 1], [0, 2], [0, 3], [1, 3]]

>>> G = Graph.from_vertices(['a', 'c', 'b'])
>>> G.edge_list()
[]

>>> G = Graph([['c', 'b'], ['b', 'a']])
>>> G.edge_list()
[['a', 'b'], ['b', 'c']]

>>> G = Graph([['c', 1], [2, 'a']]) # incomparable vertices
>>> G.edge_list()
[('c', 1), (2, 'a')]

Return type:: List[Edge]

extension_sequence(dim=2, return_solution=False)[source]¶

Check the existence of a sequence of 0 and 1-extensions.

The method returns whether the graph can be constructed by a sequence of 0 and 1-extensions starting from an edge.

Parameters:

dim (int) – The dimension in which the extensions are created. Currently implemented only for dim==2.
return_solution (bool) – If False, a boolean value indicating if the graph can be created by a sequence of extensions is returned. If True, an extension sequence of graphs that creates the graph is returned, or None if no such extension sequence exists.

Return type:

List[Graph] | bool

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.ThreePrism()
>>> 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]]
>>> G.extension_sequence()
True
>>> G = graphs.CompleteBipartite(1, 2)
>>> G
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2]]
>>> G.extension_sequence()
False
>>> G = graphs.Complete(3)
>>> G
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> G.extension_sequence(return_solution=True)
[Graph with vertices [1, 2] and edges [[1, 2]], Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]]
>>> G = graphs.Diamond()
>>> G
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [2, 3]]
>>> G.extension_sequence(return_solution=True)
[Graph with vertices [2, 3] and edges [[2, 3]], Graph with vertices [0, 2, 3] and edges [[0, 2], [0, 3], [2, 3]], Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [2, 3]]]

classmethod from_adjacency_matrix(M)[source]¶

Create a graph from a given adjacency matrix.

Examples

>>> M = Matrix([[0,1],[1,0]])
>>> G = Graph.from_adjacency_matrix(M)
>>> print(G)
Graph with vertices [0, 1] and edges [[0, 1]]

Parameters:: M (MutableDenseMatrix)
Return type:: Graph

classmethod from_int(N)[source]¶

Return a graph given its integer representation.

See to_int() for the description of the integer representation.

Parameters:: N (int)
Return type:: Graph

classmethod from_vertices(vertices)[source]¶

Create a graph with no edges from a list of vertices.

Examples

>>> from pyrigi import Graph
>>> G = Graph.from_vertices([3, 1, 7, 2, 12, 3, 0])
>>> G
Graph with vertices [0, 1, 2, 3, 7, 12] and edges []

Parameters:: vertices (List[Vertex])
Return type:: Graph

classmethod from_vertices_and_edges(vertices, edges)[source]¶

Create a graph from a list of vertices and edges.

Parameters:

vertices (List[Vertex])
edges (List[Edge])

Return type:

Graph

Examples

>>> Graph.from_vertices_and_edges([0, 1, 2, 3], [])
Graph with vertices [0, 1, 2, 3] and edges []
>>> Graph.from_vertices_and_edges([0, 1, 2, 3], [[0, 1], [0, 2], [1, 3]])
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [1, 3]]
>>> Graph.from_vertices_and_edges(['a', 'b', 'c', 'd'], [['a','c'], ['a', 'd']])
Graph with vertices ['a', 'b', 'c', 'd'] and edges [['a', 'c'], ['a', 'd']]

intersection(G2)[source]¶

Return the intersection of self and G2.

Parameters:: G2 (Graph)

Examples

>>> H = Graph([[1,2],[2,3],[3,1],[3,4]])
>>> G = Graph([[0,1],[1,2],[2,3],[3,1]])
>>> G.intersection(H)
Graph with vertices [1, 2, 3] and edges [[1, 2], [1, 3], [2, 3]]
>>> G = Graph([[0,1],[0,2],[1,2]])
>>> G.add_vertex(3)
>>> H = Graph([[0,1],[1,2],[2,4],[4,0]])
>>> H.add_vertex(3)
>>> G.intersection(H)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [1, 2]]

is_Rd_circuit(dim=2, use_precomputed_pebble_digraph=False)[source]¶

Notes

dim=1: Graphic Matroid
dim=2: It is not sparse, but remove any edge and it becomes sparse
Fundamental circuit is the whole graph
Not combinatorially:
dim>=1: Dependent + Remove every edge and compute the rigidity matrix’ rank

use_precomputed_pebble_digraph:: Only relevant if dim=2. If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.

Todo

Add unit tests, make computation of remaining_edge more robust

Parameters:

dim (int)
use_precomputed_pebble_digraph (bool)

Return type:

bool

is_Rd_closed(dim=2)[source]¶

Notes

dim=1: Graphic Matroid
dim=2: ??
dim>=1: Adding any edge does not increase the rigidity matrix rank

Parameters:: dim (int)
Return type:: bool

is_Rd_dependent(dim=2, use_precomputed_pebble_digraph=False)[source]¶

Notes

dim=1: Graphic Matroid
dim=2: not (2,3)-sparse
dim>=1: Compute the rank of the rigidity matrix and compare with edge count

use_precomputed_pebble_digraph:: Only relevant if dim=2. If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.

Todo

Add unit tests

Parameters:

dim (int)
use_precomputed_pebble_digraph (bool)

Return type:

bool

is_Rd_independent(dim=2, use_precomputed_pebble_digraph=False)[source]¶

Notes

dim=1: Graphic Matroid
dim=2: (2,3)-sparse
dim>=1: Compute the rank of the rigidity matrix and compare with edge count

use_precomputed_pebble_digraph:: Only relevant if dim=2. If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.

Todo

Add unit tests

Parameters:

dim (int)
use_precomputed_pebble_digraph (bool)

Return type:

bool

is_globally_rigid(dim=2, prob=0.0001)[source]¶

Check whether the graph is globally dim-rigid.

Parameters:

dim (dimension d for which we test whether the graph is globally $d$-rigid)
prob (probability of getting a wrong `False answer`)

Return type:

bool

Definitions

Globally d-rigid graph

Examples

>>> G = Graph([(0,1), (1,2), (2,0)])
>>> G.is_globally_rigid()
True
>>> import pyrigi.graphDB as graphs
>>> J = graphs.ThreePrism()
>>> J.is_globally_rigid(dim=3)
False
>>> J.is_globally_rigid()
False
>>> K = graphs.Complete(6)
>>> K.is_globally_rigid()
True
>>> K.is_globally_rigid(dim=3)
True
>>> C = graphs.CompleteMinusOne(5)
>>> C.is_globally_rigid()
True
>>> C.is_globally_rigid(dim=3)
False

Notes

dim=1: 2-connectivity
dim=2: Theorem globally 2-rigid graph
dim>=3: Theorem randomize algorithm

By default, the graph is in dimension 2. A complete graph is automatically globally rigid

Since the deterministic algorithm is not very efficient, in the code we use a polynomial-time randomize algorithm, which will answer False all the time if the graph is not generically globally d-rigid, and it will give a wrong answer False with probability less than prob, which is 0.0001 by default.

is_isomorphic(graph)[source]¶

Check whether two graphs are isomorphic.

Notes

For further details, see networkx.algorithms.isomorphism.is_isomorphic().

Examples

>>> G = Graph([(0,1), (1,2)])
>>> G_ = Graph([('b','c'), ('c','a')])
>>> G.is_isomorphic(G_)
True

Parameters:: graph (Graph)
Return type:: bool

is_k_redundantly_rigid(k, dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is k-redundantly (generically) dim-rigid.

Preliminary checks from Theorem 10, Theorem 11, Theorem 12, Theorem 13, Theorem 5 and Theorem 6. are used

Parameters:

k (int) – level of redundancy
dim (int) – dimension
combinatorial (bool) – determines whether a combinatinatorial algorithm shall be used in rigidity checking. Otherwise a probabilistic check is used that may give false results. See is_rigid() for details.
prob (float) – bound on the probability for false negatives of the rigidity testing Warning: this is not the probability of wrong results in this method but is just passed on to rigidity testing

Return type:

bool

Examples

>>> G = Graph([[0, 1], [0, 2], [0, 3], [0, 5], [1, 2], [1, 4], [2, 5], [3, 4], [3, 5], [4, 5]])
>>> G.is_k_redundantly_rigid(1, 2)
True
>>> G = Graph([[0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
>>> G.is_k_redundantly_rigid(1, 2)
False
>>> G = Graph([[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
>>> G.is_k_redundantly_rigid(2, 2)
True

Todo

Improve with pebble games.

is_k_vertex_redundantly_rigid(k, dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is k-vertex redundantly (generically) dim-rigid.

Preliminary checks from Theorem 15, Theorem 16, Theorem 17, Theorem 18 Theorem 19, Theorem 20, Theorem 21 … are used

Parameters:

k (int) – level of redundancy
dim (int) – dimension
combinatorial (bool) – determines whether a combinatinatorial algorithm shall be used in rigidity checking. Otherwise a probabilistic check is used that may give false results. See is_rigid() for details.
prob (float) – bound on the probability for false negatives of the rigidity testing Warning: this is not the probability of wrong results in this method but is just passed on to rigidity testing

Return type:

bool

Examples

>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
>>> G.is_k_vertex_redundantly_rigid(1, 2)
True
>>> G.is_k_vertex_redundantly_rigid(2, 2)
False
>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 4], [3, 4]])
>>> G.is_k_vertex_redundantly_rigid(1, 2)
False

is_min_k_redundantly_rigid(k, dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is minimally k-redundantly (generically) dim-rigid.

Preliminary checks from Theorem 14 are used.

Parameters:

k (int) – level of redundancy
dim (int) – dimension
combinatorial (bool) – determines whether a combinatinatorial algorithm shall be used in rigidity checking. Otherwise a probabilistic check is used that may give false results. See is_rigid() for details.
prob (float) – bound on the probability for false negatives of the rigidity testing Warning: this is not the probability of wrong results in this method but is just passed on to rigidity testing

Return type:

bool

Examples

>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 4], [3, 4]])

>>> G.is_min_k_redundantly_rigid(1, 2)
True
>>> G.is_min_k_redundantly_rigid(2, 2)
False
>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
>>> G.is_k_redundantly_rigid(1, 2)
True
>>> G.is_min_k_redundantly_rigid(1, 2)
False

is_min_k_vertex_redundantly_rigid(k, dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is minimally k-vertex redundantly (generically) dim-rigid.

Preliminary checks from Theorem 22, Theorem 23 are used.

Parameters:

k (int) – level of redundancy
dim (int) – dimension
combinatorial (bool) – determines whether a combinatinatorial algorithm shall be used in rigidity checking. Otherwise a probabilistic check is used that may give false results. See is_rigid() for details.
prob (float) – bound on the probability for false negatives of the rigidity testing Warning: this is not the probability of wrong results in this method but is just passed on to rigidity testing

Return type:

bool

Examples

>>> G = Graph([[0, 3], [0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]])
>>> G.is_min_k_vertex_redundantly_rigid(1, 2)
True
>>> G.is_min_k_vertex_redundantly_rigid(2, 2)
False
>>> G = 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]])
>>> G.is_k_vertex_redundantly_rigid(1, 2)
True
>>> G.is_min_k_vertex_redundantly_rigid(1, 2)
False

is_min_redundantly_rigid(dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is minimally redundantly (generically) dim-rigid.

See is_min_k_redundantly_rigid() (using k = 1) for details.

Parameters:

dim (int)
combinatorial (bool)
prob (float)

Return type:

bool

is_min_rigid(dim=2, combinatorial=True, use_precomputed_pebble_digraph=False, prob=0.0001)[source]¶

Check whether the graph is minimally (generically) dim-rigid.

Parameters:

dim (int) – dimension
combinatorial (bool) – determines whether a combinatinatorial algorithm shall be used If combinatorial is true, a pebble game algorithm is used. Otherwise a probabilistic check is used that may give false negatives (see Theorem 4).
use_precomputed_pebble_digraph (bool) – Only relevant if dim=2 and combinatorial=True. If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.
prob (float) – bound on the probability of a randomized algorithm to yield false negatives

Return type:

bool

Examples

>>> G = Graph([(0,1), (1,2), (2,3), (3,0), (1,3)])
>>> G.is_min_rigid()
True
>>> G.add_edge(0,2)
>>> G.is_min_rigid()
False

Notes

dim=1: Tree
dim=2: Pebble-game/(2,3)-tight
dim>=1: Probabilistic Rigidity Matrix (maybe symbolic?)

is_min_vertex_redundantly_rigid(dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is minimally vertex redundantly (generically) dim-rigid.

See is_min_k_vertex_redundantly_rigid() (using k = 1) for details.

Parameters:

dim (int)
combinatorial (bool)
prob (float)

Return type:

bool

is_redundantly_rigid(dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is redundantly (generically) dim-rigid.

See is_k_redundantly_rigid() (using k = 1) for details.

Parameters:

dim (int)
combinatorial (bool)
prob (float)

Return type:

bool

is_rigid(dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is (generically) dim-rigid.

Parameters:

dim (int) – dimension
combinatorial (bool) – determines whether a combinatinatorial algorithm shall be used If combinatorial is true, a pebble game algorithm is used. Otherwise a probabilistic check is used that may give false negatives (see Theorem 4).
prob (float) – bound on the probability of a randomized algorithm to yield false negatives

Return type:

bool

Examples

>>> G = Graph([(0,1), (1,2), (2,3), (3,0)])
>>> G.is_rigid()
False
>>> G.add_edge(0,2)
>>> G.is_rigid()
True

Todo

Pebble game algorithm for d=2.

Notes

dim=1: Connectivity
dim=2: Pebble-game/(2,3)-rigidity
dim>=1: Rigidity Matrix if combinatorial==False

By default, the graph is in dimension two and a combinatorial check is employed.

is_sparse(K, L, algorithm='default', use_precomputed_pebble_digraph=False)[source]¶

Check whether the graph is (K, L)-sparse.

Parameters:

K (int)
L (int)
algorithm (str) – “pebble” or “subgraph”. If “pebble”, the function uses the pebble game algorithm to check for sparseness. If “subgraph”, it uses the subgraph method. If not specified, it defaults to “pebble” whenever possible, otherwise “subgraph”.
use_precomputed_pebble_digraph (bool) – If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.

Return type:

bool

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.DoubleBanana()
>>> G.is_sparse(3,6)
True
>>> G.add_edge(0,1)
>>> G.is_sparse(3,6)
False

is_tight(K, L, algorithm='default', use_precomputed_pebble_digraph=False)[source]¶

Check whether the graph is (K, L)-tight.

Parameters:

K (int)
L (int)
algorithm (str) – “pebble” or “subgraph”. If “pebble”, the function uses the pebble game algorithm to check for sparseness. If “subgraph”, it uses the subgraph method. If not specified, it defaults to “pebble”.
use_precomputed_pebble_digraph (bool) – If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.
Examples
----´
graphs (>>> import pyrigi.graphDB as)
graphs.Complete(4) (>>> G =)
G.is_tight(2 (>>>)
2)
True
graphs.CompleteBipartite(4 (>>> G1 =)
4)
G1.is_tight(3 (>>>)
6)
False

Return type:

bool

is_vertex_redundantly_rigid(dim=2, combinatorial=True, prob=0.0001)[source]¶

Check whether the graph is vertex redundantly (generically) dim-rigid.

See is_k_vertex_redundantly_rigid() (using k = 1) for details.

Parameters:

dim (int)
combinatorial (bool)
prob (float)

Return type:

bool

k_extension(k, vertices, edges, new_vertex=None, dim=2, inplace=False)[source]¶

Return a dim-dimensional k-extension.

Parameters:

k (int)
vertices (List[Vertex]) – A new vertex will be connected to these vertices. All the vertices must be contained in the graph and there must be dim + k of them.
edges (List[Edge]) – A list of edges that will be 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 | None) – Newly added vertex will be named according to this parameter. If None, the name will be 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 will be modified, otherwise a new modified graph will be created, while the original graph remains unchanged (default).

Return type:

Graph

Notes

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(5)
>>> 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]]
>>> G.k_extension(2, [0, 1, 2, 3], [[0, 1], [0,2]])
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
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]]
>>> G = graphs.Complete(5)
>>> 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]]
>>> G.k_extension(2, [0, 1, 2, 3, 4], [[0, 1], [0,2]], dim = 3)
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)
>>> G
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
>>> G.k_extension(2, [0, 1, 2], [[0, 1], [1,2]], dim = 1, inplace = True)
Graph with vertices [0, 1, 2, 3, 4, 5, 6] and edges [[0, 6], [1, 6], [2, 3], [2, 6], [3, 4], [4, 5]]
>>> 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]]

layout(layout_type='spring')[source]¶

Generate a placement of the vertices.

This method a is wrapper for the functions spring_layout(), random_layout(), circular_layout() and planar_layout()

Parameters:: layout_type (str) – The supported layouts are circular, planar, random and spring (default).
Return type:: Dict[Vertex, Point]

max_degree()[source]¶

Return the maximum of the vertex degrees.

Examples

>>> G = Graph([(0,1), (1,2)])
>>> G.max_degree()
2

Return type:: int

max_rigid_dimension()[source]¶

Compute the maximum dimension, in which a graph is generically rigid.

Notes

This is done by taking the dimension predicted by the Maxwell count as a starting point and iteratively reducing the dimension until generic rigidity is found. This method returns sympy.oo (infinity) if and only if the graph is complete. It has the data type Inf.

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> rigid_dim = G.max_rigid_dimension(); rigid_dim
oo
>>> rigid_dim.is_infinite
True

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(4)
>>> G.add_edges([(0,4),(1,4),(2,4)])
>>> G.max_rigid_dimension()
3

Return type:: int | Number

min_degree()[source]¶

Return the minimum of the vertex degrees.

Examples

>>> G = Graph([(0,1), (1,2)])
>>> G.min_degree()
1

Return type:: int

number_of_realizations(spherical_realizations=False, check_min_rigid=True, count_reflection=False)[source]¶

Count the number of complex planar or spherical realizations of a minimally 2-rigid graph.

Algorithms of [CGG+18] and [GGS20] are used. Note, however, that here the result from these algorithms is by default divided by two. This behaviour accounts better for global rigidity, but it can be changed using the parameter count_reflection.

Note that by default, the method checks if the input graph is indeed minimally 2-rigid.

Caution: Currently the method only works if the python package lnumber is installed [Cap24]. See Installation Guide for details on installing.

Definitions

Number of complex realizations

Number of complex spherical realizations

Parameters:

check_min_rigid (bool) – If True, ValueError is raised if the graph is not minimally 2-rigid If False, it is assumed that the user is inputing a minimally rigid graph.
spherical_realizations (bool) – If True, the number of spherical realizations of the graph is returned. If False (default), the number of planar realizations is returned.
count_reflection (bool) – If True, the number of realizations is computed modulo direct isometries. But reflection is counted to be non-congruent as used in [CGG+18] and [GGS20]. If False (default), reflection is not counted.

Return type:

int

Examples

>>> from pyrigi import Graph
>>> import pyrigi.graphDB as graphs
>>> G = Graph([(0,1),(1,2),(2,0)])
>>> G.number_of_realizations() # number of planar realizations
1
>>> G.number_of_realizations(spherical_realizations=True)
1
>>> G = graphs.ThreePrism()
>>> G.number_of_realizations() # number of planar realizations
12

one_extension(vertices, edge, new_vertex=None, dim=2, inplace=False)[source]¶

Return a dim-dimensional 1-extension.

Parameters:

vertices (List[Vertex]) – A new vertex will be 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 will be deleted. The edge must be contained in the graph.
new_vertex (Vertex | None) – Newly added vertex will be named according to this parameter. If None, the name will be 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 will be modified, otherwise a new modified graph will be created, while the original graph remains unchanged (default).

Return type:

Graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> G
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> G.one_extension([0, 1, 2], [0, 1])
Graph with vertices [0, 1, 2, 3] and edges [[0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
>>> G
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> G = graphs.ThreePrism()
>>> 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]]
>>> G.one_extension([0, 1], [0, 1], dim=1)
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)
>>> G
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 3], [0, 4], [1, 3], [1, 4], [2, 3], [2, 4]]
>>> G.one_extension([0, 1, 2, 3, 4], [0, 3], dim=4, inplace = True)
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]]
>>> 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]]

plot(placement=None, inf_flex=None, layout='spring', vertex_size=300, vertex_color='#4169E1', vertex_shape='o', vertex_labels=True, edge_width=2.5, edge_color='black', edge_style='solid', flex_width=2.5, flex_length=0.15, flex_color='limegreen', flex_style='solid', flex_arrowsize=20, font_color='whitesmoke', canvas_width=6.4, canvas_height=4.8, aspect_ratio=1.0, **kwargs)[source]¶

Plot the graph.

See tutorial Plotting for illustration of the options.

Parameters:

placement (Dict[Vertex, Point]) – If placement is not specified, then it is generated depending on parameter layout.
inf_flex (Dict[Vertex, Sequence[Coordinate]]) – It is possible to plot an infinitesimal flex alongside the realization of your graph. It is specified as a Dict of flexes.
layout (str) – The possibilities are spring (default), circular, random or planar, see also layout().
vertex_size (int) – The size of the vertices.
vertex_color (str) – The color of the vertices. The color can be a string or an rgb (or rgba) tuple of floats from 0-1.
vertex_shape (str) – The shape of the vertices specified as as matplotlib.scatter marker, one of so^>v<dph8.
vertex_labels (bool) – If True (default), vertex labels are displayed.
edge_width (float)
edge_color (str | List[List[Edge]] | Dict[str:List[Edge]]) – If a single color is given as a string or rgb (or rgba) tuple of floats from 0-1, then all edges get this color. If a (possibly incomplete) partition of the edges is given, then each part gets a different color. If a dictionary from colors to a list of edge is given, edges are colored accordingly. The edges missing in the partition/dictionary, are colored black.
edge_style (str) – Edge line style: -/solid, --/dashed, -./dashdot or :/dotted. By default ‘-‘.
flex_width (float) – The width of the infinitesimal flex’s arrow tail.
flex_color (str | List[List[Edge]] | Dict[str:List[Edge]]) – The color of the infinitesimal flex is by default ‘limegreen’.
flex_style (str) – Line Style: -/solid, --/dashed, -./dashdot or :/dotted. By default ‘-‘.
flex_length (float) – Length of the displayed flex relative to the total canvas diagonal in percent. By default 15%.
flex_arrowsize (int) – Size of the arrowhead’s length and width.
font_size – The size of the font used for the labels.
font_color (str) – The color of the font used for the labels.
canvas_width (float) – The width of the canvas in inches.
canvas_height (float) – The height of the canvas in inches.
aspect_ratio (float) – The ratio of y-unit to x-unit. By default 1.0.

Return type:

None

random_framework(dim=2, rand_range=None)[source]¶

Return framework with random realization.

This method calls Framework.Random().

Parameters:

dim (int)
rand_range (Union(int, List[int]))

rigid_components(dim=2)[source]¶

List the vertex sets inducing vertex-maximal rigid subgraphs.

Definitions

Rigid components

Notes

If the graph itself is rigid, it is clearly maximal and is returned. Every edge is part of a rigid component. Isolated vertices form additional rigid components.

Examples

>>> G = Graph([(0,1), (1,2), (2,3), (3,0)])
>>> G.rigid_components()
[[0, 1], [0, 3], [1, 2], [2, 3]]

>>> G = Graph([(0,1), (1,2), (2,3), (3,4), (4,5), (5,0), (0,2), (5,3)])
>>> G.is_rigid()
False
>>> G.rigid_components()
[[0, 5], [2, 3], [0, 1, 2], [3, 4, 5]]

Parameters:: dim (int)
Return type:: List[List[Vertex]]

spanning_sparse_subgraph(K, L, use_precomputed_pebble_digraph=False)[source]¶

Return a maximal (K, L)-sparse subgraph.

Based on the directed graph calculated by the pebble game algorithm, return a maximal (K, L)-sparse of the graph. There are multiple possible maximal (K, L)-sparse subgraphs, all of which have the same number of edges.

Parameters:

K (int)
L (int)
use_precomputed_pebble_digraph (bool) – If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.

Return type:

Graph

sum_t(G2, edge, t=2)[source]¶

Return the t-sum of self and G2 along the given edge.

Parameters:

G2 (Graph)
edge (Edge)
t (integer, default value 2)

Definitions

t-sum

Examples

>>> H = Graph([[1,2],[2,3],[3,1],[3,4]])
>>> G = Graph([[0,1],[1,2],[2,3],[3,1]])
>>> H.sum_t(G, [1, 2], 3)
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 1], [1, 3], [2, 3], [3, 4]]

to_int(vertex_order=None)[source]¶

Return the integer representation of the graph.

The graph integer representation is the integer whose binary expansion is given by the sequence obtained by concatenation of the rows of the upper triangle of the adjacency matrix, excluding the diagonal.

Parameters:: vertex_order (List[Vertex] | None) – By listing vertices in the preferred order, the adjacency matrix is computed with the given order. If no vertex order is provided, vertex_list() is used.
Return type:: int

Examples

>>> G = Graph([(0,1), (1,2)])
>>> G.adjacency_matrix()
Matrix([
[0, 1, 0],
[1, 0, 1],
[0, 1, 0]])
>>> G.to_int()
5

Todo

Implement taking canonical before computing the integer representation. Tests.

to_tikz(layout_type='spring', placement=None, vertex_style='gvertex', edge_style='edge', label_style='labelsty', figure_opts='', vertex_in_labels=False, vertex_out_labels=False, default_styles=True)[source]¶

Create a TikZ code for the graph.

For using it in LaTeX you need to use the tikz package.

Parameters:

placement (dict[Vertex, Point]) – If placement is not specified, then it is generated depending on parameter layout.
layout – The possibilities are spring (default), circular, random or planar, see also layout().
vertex_style (Union(str, dict[str:list[Vertex]])) – If a single style is given as a string, then all vertices get this style. If a dictionary from styles to a list of vertices is given, vertices are put in style accordingly. The vertices missing in the dictionary do not get a style.
edge_style (Union(str, dict[str:list[Edge]])) – If a single style is given as a string, then all edges get this style. If a dictionary from styles to a list of edges is given, edges are put in style accordingly. The edges missing in the dictionary do not get a style.
label_style (str) – The style for labels that are placed next to vertices.
figure_opts (str) – Options for the tikzpicture environment.
vertex_in_labels (bool) – A bool on whether vertex names should be put as labels on the vertices.
vertex_out_labels (bool) – A bool on whether vertex names should be put next to vertices.
default_styles (bool) – A bool on whether default style definitions should be put to the options.
layout_type (str)

Return type:

str

Examples

>>> G = Graph([(0,1), (1,2), (2,3), (0,3)])
>>> print(G.to_tikz()) 
\begin{tikzpicture}[gvertex/.style={fill=black,draw=white,circle,inner sep=0pt,minimum size=4pt},edge/.style={line width=1.5pt,black!60!white}]
    \node[gvertex] (0) at (-0.98794, -0.61705) {};
    \node[gvertex] (1) at (0.62772, -1.0) {};
    \node[gvertex] (2) at (0.98514, 0.62151) {};
    \node[gvertex] (3) at (-0.62492, 0.99554) {};
    \draw[edge] (0) to (1) (0) to (3) (1) to (2) (2) to (3);
\end{tikzpicture}

>>> print(G.to_tikz(layout_type = "circular")) 
\begin{tikzpicture}[gvertex/.style={fill=black,draw=white,circle,inner sep=0pt,minimum size=4pt},edge/.style={line width=1.5pt,black!60!white}]
    \node[gvertex] (0) at (1.0, 0.0) {};
    \node[gvertex] (1) at (-0.0, 1.0) {};
    \node[gvertex] (2) at (-1.0, -0.0) {};
    \node[gvertex] (3) at (0.0, -1.0) {};
    \draw[edge] (0) to (1) (0) to (3) (1) to (2) (2) to (3);
\end{tikzpicture}

>>> print(G.to_tikz(placement = [[0, 0], [1, 1], [2, 2], [3, 3]])) 
\begin{tikzpicture}[gvertex/.style={fill=black,draw=white,circle,inner sep=0pt,minimum size=4pt},edge/.style={line width=1.5pt,black!60!white}]
    \node[gvertex] (0) at (0, 0) {};
    \node[gvertex] (1) at (1, 1) {};
    \node[gvertex] (2) at (2, 2) {};
    \node[gvertex] (3) at (3, 3) {};
    \draw[edge] (0) to (1) (0) to (3) (1) to (2) (2) to (3);
\end{tikzpicture}

>>> print(G.to_tikz(layout_type = "circular", vertex_out_labels = True)) 
\begin{tikzpicture}[gvertex/.style={fill=black,draw=white,circle,inner sep=0pt,minimum size=4pt},edge/.style={line width=1.5pt,black!60!white},labelsty/.style={font=\scriptsize,black!70!white}]
    \node[gvertex,label={[labelsty]right:$0$}] (0) at (1.0, 0.0) {};
    \node[gvertex,label={[labelsty]right:$1$}] (1) at (-0.0, 1.0) {};
    \node[gvertex,label={[labelsty]right:$2$}] (2) at (-1.0, -0.0) {};
    \node[gvertex,label={[labelsty]right:$3$}] (3) at (0.0, -1.0) {};
    \draw[edge] (0) to (1) (0) to (3) (1) to (2) (2) to (3);
\end{tikzpicture}

>>> print(G.to_tikz(layout_type = "circular", vertex_in_labels = True)) 
\begin{tikzpicture}[gvertex/.style={white,fill=black,draw=black,circle,inner sep=1pt,font=\scriptsize},edge/.style={line width=1.5pt,black!60!white}]
    \node[gvertex] (0) at (1.0, 0.0) {$0$};
    \node[gvertex] (1) at (-0.0, 1.0) {$1$};
    \node[gvertex] (2) at (-1.0, -0.0) {$2$};
    \node[gvertex] (3) at (0.0, -1.0) {$3$};
    \draw[edge] (0) to (1) (0) to (3) (1) to (2) (2) to (3);
\end{tikzpicture}

>>> print(G.to_tikz(layout_type = "circular", vertex_style = "myvertex", edge_style = "myedge")) 
\begin{tikzpicture}[]
    \node[myvertex] (0) at (1.0, 0.0) {};
    \node[myvertex] (1) at (-0.0, 1.0) {};
    \node[myvertex] (2) at (-1.0, -0.0) {};
    \node[myvertex] (3) at (0.0, -1.0) {};
    \draw[myedge] (0) to (1) (0) to (3) (1) to (2) (2) to (3);
\end{tikzpicture}

>>> print(G.to_tikz(layout_type = "circular", edge_style = {"red edge": [[1, 2]], "green edge": [[2, 3], [0, 1]]}, vertex_style = {"red vertex": [0], "blue vertex": [2, 3]})) 
\begin{tikzpicture}[]
    \node[red vertex] (0) at (1.0, 0.0) {};
    \node[blue vertex] (2) at (-1.0, -0.0) {};
    \node[blue vertex] (3) at (0.0, -1.0) {};
    \node[] (1) at (-0.0, 1.0) {};
    \draw[red edge] (1) to (2);
    \draw[green edge] (2) to (3) (0) to (1);
    \draw[] (3) to (0);
\end{tikzpicture}

vertex_connectivity()[source]¶

Alias for networkx.algorithms.connectivity.connectivity.node_connectivity().

Return type:: int

vertex_list()[source]¶

Return the list of vertices.

The output is sorted if possible, otherwise, the internal order is used instead.

Examples

>>> G = Graph.from_vertices_and_edges([2, 0, 3, 1], [[0, 1], [0, 2], [0, 3]])
>>> G.vertex_list()
[0, 1, 2, 3]

>>> G = Graph.from_vertices(['c', 'a', 'b'])
>>> G.vertex_list()
['a', 'b', 'c']

>>> G = Graph.from_vertices(['b', 1, 'a']) # incomparable vertices
>>> G.vertex_list()
['b', 1, 'a']

Return type:: List[Vertex]

zero_extension(vertices, new_vertex=None, dim=2, inplace=False)[source]¶

Return a dim-dimensional 0-extension.

Parameters:

vertices (List[Vertex]) – A new vertex will be connected to these vertices. All the vertices must be contained in the graph and there must be dim of them.
new_vertex (Vertex | None) – Newly added vertex will be named according to this parameter. If None, the name will be 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 will be modified, otherwise a new modified graph will be created, while the original graph remains unchanged (default).

Return type:

Graph

Examples

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