Graphs

Module for rigidity related graph properties.

class pyrigi.graph.Graph(incoming_graph_data=None, **attr)

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().
k_extension(k, vertices, edges[, ...])	Return a dim-dimensional k-extension.
one_extension(vertices, edge[, new_vertex, ...])	Return a dim-dimensional 1-extension.
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])	Check whether the graph is globally dim-rigid.
is_k_redundantly_rigid(k[, dim, combinatorial])	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, combinatorial])	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])	Check whether the graph is redundantly (generically) dim-rigid.
is_rigid([dim, combinatorial])	Check whether the graph is (generically) dim-rigid.
is_vertex_redundantly_rigid([dim, combinatorial])	Check whether the graph is vertex redundantly (generically) dim-rigid.
max_rigid_subgraphs([dim])	List the vertex sets inducing vertex-maximal rigid subgraphs.
min_rigid_subgraphs([dim])	List the vertex sets inducing vertex-minimal non-trivial 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, layout, vertex_size, ...])	Plot the graph.
random_framework([dim, rand_range])	Return framework with random realization.
to_int([vertex_order])	Return the integer representation of 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:

• Graph display

• Directed Graphs

• Linear Algebra on Graphs

• A Database of some Graphs

• Reading and Writing Graphs

• Converting to and from other Data Formats

classmethod CompleteOnVertices(vertices)

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

__eq__(other)

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__()

Return a representation.

Return type:

str

__str__()

Return the string representation.

Return type:

str

add_edges(edges)

Alias for networkx.Graph.add_edges_from().

Parameters:

edges (List[Edge])

Return type:

None

add_vertex(vertex)

Alias for networkx.Graph.add_node().

Parameters:

vertex (Vertex)

Return type:

None

add_vertices(vertices)

Alias for networkx.Graph.add_nodes_from().

Parameters:

vertices (List[Vertex])

Return type:

None

adjacency_matrix(vertex_order=None)

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)

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)

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)

Alias for networkx.Graph.remove_edge()

Parameters:

edge (Edge)

Return type:

None

delete_edges(edges)

Alias for networkx.Graph.remove_edges_from().

Parameters:

edges (List[Edge])

Return type:

None

delete_loops()

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

Return type:

None

delete_vertex(vertex)

Alias for networkx.Graph.remove_node().

Parameters:

vertex (Vertex)

Return type:

None

delete_vertices(vertices)

Alias for networkx.Graph.remove_nodes_from().

Parameters:

vertices (List[Vertex])

Return type:

None

edge_list()

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)

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)

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)

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)

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)

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']]

is_Rd_circuit(dim=2, use_precomputed_pebble_digraph=False)

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

Parameters:

• dim (int)

• use_precomputed_pebble_digraph (bool)

Return type:

bool

is_Rd_closed(dim=2)

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)

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)

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)

Check whether the graph is globally dim-rigid.

Todo

missing definition, implementation for dim>=3

Examples

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

Notes

• dim=1: 2-connectivity

• dim=2: redundantly rigid+3-connected

• dim>=3: Randomized Rigidity Matrix => Stress (symbolic maybe?)

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

Parameters:

dim (int)

Return type:

bool

is_isomorphic(graph)

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)

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

Preliminary checks from Theorem 11, Theorem 12, Theorem 13, Theorem 14, Theorem 2 and Theorem 3. are used

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.

Parameters:

• k (int)

• dim (int)

• combinatorial (bool)

Return type:

bool

is_k_vertex_redundantly_rigid(k, dim=2, combinatorial=True)

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

Preliminary checks from Theorem 4, Theorem 5, Theorem 6, Theorem 7 Theorem 8, Theorem 9, Theorem 10 … are used

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

Parameters:

• k (int)

• dim (int)

• combinatorial (bool)

Return type:

bool

is_min_k_redundantly_rigid(k, dim=2, combinatorial=True)

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

Preliminary checks from Theorem 17 are used.

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

Parameters:

• k (int)

• dim (int)

• combinatorial (bool)

Return type:

bool

is_min_k_vertex_redundantly_rigid(k, dim=2, combinatorial=True)

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

Preliminary checks from Theorem 15, Theorem 16 are used.

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

Parameters:

• k (int)

• dim (int)

• combinatorial (bool)

Return type:

bool

is_min_redundantly_rigid(dim=2, combinatorial=True)

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)

Return type:

bool

is_min_rigid(dim=2, combinatorial=True, use_precomputed_pebble_digraph=False)

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

Parameters:

• 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.

• dim (int)

• combinatorial (bool)

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)

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)

Return type:

bool

is_redundantly_rigid(dim=2, combinatorial=True)

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

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

Parameters:

• dim (int)

• combinatorial (bool)

Return type:

bool

is_rigid(dim=2, combinatorial=True)

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

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.

Parameters:

• dim (int)

• combinatorial (bool)

Return type:

bool

is_sparse(K, L, algorithm='default', use_precomputed_pebble_digraph=False)

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

Todo

examples, tests for other cases than (2,3)

is_tight(K, L, algorithm='default', use_precomputed_pebble_digraph=False)

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.

Return type:

bool

Todo

examples, tests for other cases than (2,3)

is_vertex_redundantly_rigid(dim=2, combinatorial=True)

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)

Return type:

bool

k_extension(k, vertices, edges, new_vertex=None, dim=2, inplace=False)

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

See also zero_extension() and one_extension().

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')

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()

Return the maximum of the vertex degrees.

Examples

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

Return type:

int

max_rigid_subgraphs(dim=2)

List the vertex sets inducing vertex-maximal rigid subgraphs.

Definitions

Maximal rigid subgraph

Todo

missing definition, tests

Notes

We only return nontrivial subgraphs, meaning that there need to be at least dim+1 vertices present. If the graph itself is rigid, it is clearly maximal and is returned.

Examples

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

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

Parameters:

dim (int)

Return type:

List[Graph]

min_degree()

Return the minimum of the vertex degrees.

Examples

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

Return type:

int

min_rigid_subgraphs(dim=2)

List the vertex sets inducing vertex-minimal non-trivial rigid subgraphs.

Definitions

Minimal rigid subgraph

Todo

missing definition, tests

Notes

We only return nontrivial subgraphs, meaning that there need to be at least dim+1 vertices present.

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.CompleteBipartite(3, 3)
>>> G.is_rigid()
True
>>> G.min_rigid_subgraphs()
[[0, 1, 2, 3, 4, 5]]
>>> G = graphs.ThreePrism()
>>> G.is_rigid()
True
>>> G.min_rigid_subgraphs()
[[0, 1, 2], [3, 4, 5]]

Parameters:

dim (int)

Return type:

List[Graph]

one_extension(vertices, edge, new_vertex=None, dim=2, inplace=False)

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, layout='spring', vertex_size=300, vertex_color='#4169E1', vertex_shape='o', vertex_labels=True, edge_width=2.5, edge_color='black', edge_style='solid', font_color='whitesmoke', canvas_width=6.4, canvas_height=4.8, aspect_ratio=1.0, **kwargs)

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.

• 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 (Union(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 ‘-‘.

• 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)

Return framework with random realization.

This method calls Framework.Random().

Parameters:

• dim (int)

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

spanning_sparse_subgraph(K, L, use_precomputed_pebble_digraph=False)

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

to_int(vertex_order=None)

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.

vertex_connectivity()

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

Return type:

int

vertex_list()

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)

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