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

Methods

Attribute getters

edge_list([as_tuples])

Return the list of edges.

vertex_list()

Return the list of vertices.

Class methods

from_adjacency_matrix(adj_matrix)

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_extensions([dim, only_non_isomorphic, ...])

Return an iterator over all dim-dimensional extensions.

all_k_extensions(k[, dim, only_non_isomorphic])

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

cone([inplace, vertex])

Return a coned version of the graph.

delete_edge(edge)

Alias for networkx.Graph.remove_edge()

delete_edges(edges)

Alias for networkx.Graph.remove_edges_from().

delete_loops()

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

Return the intersection with other_graph.

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(other_graph, edge[, t])

Return the t-sum with other_graph 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_critically_edge_apex()

Return whether the graph is critically edge apex.

is_critically_k_edge_apex(k)

Return whether the graph is critically k-edge apex.

is_critically_k_vertex_apex(k)

Return whether the graph is critically k-vertex apex.

is_critically_vertex_apex()

Return whether the graph is critically vertex apex.

is_edge_apex()

Return whether the graph is edge apex.

is_isomorphic(graph)

Return whether two graphs are isomorphic.

is_k_edge_apex(k)

Return whether the graph is k-edge apex.

is_k_vertex_apex(k)

Return whether the graph is k-vertex apex.

is_vertex_apex()

Return whether the graph is vertex apex.

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

Compute a sequence of dim-dimensional extensions.

has_extension_sequence([dim])

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

is_globally_rigid([dim, algorithm, prob])

Return whether the graph is globally dim-rigid.

is_k_redundantly_rigid(k[, dim, algorithm, prob])

Return whether the graph is k-redundantly dim-rigid.

is_k_vertex_redundantly_rigid(k[, dim, ...])

Return whether the graph is k-vertex redundantly dim-rigid.

is_linked(u, v[, dim])

Return whether a pair of vertices is dim-linked.

is_min_k_redundantly_rigid(k[, dim, ...])

Return whether the graph is minimally k-redundantly dim-rigid.

is_min_k_vertex_redundantly_rigid(k[, dim, ...])

Return whether the graph is minimally k-vertex redundantly dim-rigid.

is_min_redundantly_rigid([dim, algorithm, prob])

Return whether the graph is minimally redundantly dim-rigid.

is_min_rigid([dim, algorithm, ...])

Return whether the graph is minimally dim-rigid.

is_min_vertex_redundantly_rigid([dim, ...])

Return whether the graph is minimally vertex redundantly dim-rigid.

is_redundantly_rigid([dim, algorithm, prob])

Return whether the graph is redundantly dim-rigid.

is_rigid([dim, algorithm, prob])

Return whether the graph is dim-rigid.

is_separating_set(vertices)

Check if a set of vertices is a separating set.

is_vertex_redundantly_rigid([dim, ...])

Return whether the graph is vertex redundantly dim-rigid.

is_weakly_globally_linked(u, v[, dim])

Return whether the vertices u and v are weakly globally dim-linked.

max_rigid_dimension([prob])

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

number_of_realizations([dim, spherical, ...])

Count the number of complex realizations of a minimally dim-rigid graph.

rigid_components([dim, algorithm, prob])

Return the list of the vertex sets of dim-rigid components.

Sparseness

is_kl_sparse(K, L[, algorithm, ...])

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

is_kl_tight(K, L[, algorithm, ...])

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

is_sparse()

Return whether the graph is (2,3)-sparse.

is_tight()

Return whether the graph is (2,3)-tight.

spanning_kl_sparse_subgraph(K, L[, ...])

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

Rigidity Matroid

Rd_closure([dim, algorithm])

Return the set of edges given by closure in the generic dim-rigidity matroid.

is_Rd_circuit([dim, algorithm, ...])

Return whether the edge set is a circuit in the generic dim-rigidity matroid.

is_Rd_closed([dim, algorithm])

Return whether the edge set is closed in the generic dim-rigidity matroid.

is_Rd_dependent([dim, algorithm, ...])

Return whether the edge set is dependent in the generic dim-rigidity matroid.

is_Rd_independent([dim, algorithm, ...])

Return whether the edge set is independent in the generic dim-rigidity matroid.

Other

layout([layout_type])

Generate a placement of the vertices.

plot([plot_style, placement, layout])

Plot the graph.

random_framework([dim, rand_range])

Return a 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.

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:

Rd_closure(dim=2, algorithm='default')[source]

Return the set of edges given by closure in the generic dim-rigidity matroid.

Definitions

Parameters:
  • dim (int) – Dimension of the rigidity matroid.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the closure is computed using connected components.

    If "pebble" (only if dim=2), then pebble games are used.

    If "randomized", then adding non-edges is tested one by one on a random framework.

    If "default", then "graphic" is used for dim=1, "pebble" for dim=2 and "randomized" for dim>=3.

Return type:

list[Edge]

Examples

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

Notes

The pebble game algorithm proceeds as follows: Iterate through the vertex pairs of each connected component and check if there exists a rigid component containing both. This can be done by trying to add a new edge between the vertices. If there is such a rigid component, we can add every vertex pair from there: they are certainly within a rigid component.

Suggested Improvements

prob parameter for the randomized algorithm

__add__(other)[source]

Return the union of self and other.

Return type:

Graph

Parameters:

other (Graph)

Definitions

Union of two graphs

Examples

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

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

Return type:

bool

Parameters:

other (Graph)

Examples

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

Notes

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

__repr__()[source]

Return a representation of a graph.

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 (Sequence[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 (Sequence[Vertex])

Return type:

None

adjacency_matrix(vertex_order=None)[source]

Return the adjacency matrix of the graph.

Parameters:

vertex_order (Sequence[Vertex]) – 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_extensions(dim=2, only_non_isomorphic=False, k_min=0, k_max=None)[source]

Return an iterator over all dim-dimensional extensions.

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

Definitions

k-extension

Parameters:
  • dim (int)

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

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

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

Return type:

Iterable[Graph]

Examples

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

Notes

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

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

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

Definitions

k-extension

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

Notes

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

cone(inplace=False, vertex=None)[source]

Return a coned version of the graph.

Definitions

Cone graph

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

  • vertex (Vertex) – It is possible to give the added cone vertex a name using the keyword vertex.

Return type:

Graph

Examples

>>> G = Graph([(0,1)]).cone()
>>> G.is_isomorphic(Graph([(0,1),(1,2),(0,2)]))
True
degree_sequence(vertex_order=None)[source]

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

Parameters:

vertex_order (Sequence[Vertex]) – 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 (Sequence[Edge])

Return type:

None

delete_loops()[source]

Remove 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 (Sequence[Vertex])

Return type:

None

edge_list(as_tuples=False)[source]

Return the list of edges.

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

Parameters:

as_tuples (bool) – If True, all edges are returned as tuples instead of lists.

Return type:

list[Edge]

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')]
extension_sequence(dim=2, return_type='extensions')[source]

Compute a sequence of dim-dimensional extensions.

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

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

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

Definitions

k-extension

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

  • return_type (str) –

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

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

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

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

Return type:

list[Graph] | list | None

Examples

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

Create a graph from a given adjacency matrix.

Return type:

Graph

Parameters:

adj_matrix (MutableDenseMatrix)

Examples

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

Return a graph given its integer representation.

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

Return type:

Graph

Parameters:

N (int)

classmethod from_vertices(vertices)[source]

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

Parameters:

vertices (Sequence[Vertex])

Return type:

Graph

Examples

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

Create a graph from a list of vertices and edges.

Parameters:
Return type:

Graph

Examples

>>> G = Graph.from_vertices_and_edges([0, 1, 2, 3], [])
>>> print(G)
Graph with vertices [0, 1, 2, 3] and edges []
>>> G = Graph.from_vertices_and_edges([0, 1, 2, 3], [[0, 1], [0, 2], [1, 3]])
>>> print(G)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [1, 3]]
>>> G = Graph.from_vertices_and_edges(['a', 'b', 'c', 'd'], [['a','c'], ['a', 'd']])
>>> print(G)
Graph with vertices ['a', 'b', 'c', 'd'] and edges [['a', 'c'], ['a', 'd']]
has_extension_sequence(dim=2)[source]

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

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

Definitions

k-extension

Parameters:

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

Return type:

bool

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.ThreePrism()
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [1, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> G.has_extension_sequence()
True
>>> G = graphs.CompleteBipartite(1, 2)
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2]]
>>> G.has_extension_sequence()
False
intersection(other_graph)[source]

Return the intersection with other_graph.

Parameters:

other_graph (Graph)

Return type:

Graph

Examples

>>> H = Graph([[1,2],[2,3],[3,1],[3,4]])
>>> G = Graph([[0,1],[1,2],[2,3],[3,1]])
>>> graph = G.intersection(H)
>>> print(graph)
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)
>>> graph = G.intersection(H)
>>> print(graph)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [1, 2]]
is_Rd_circuit(dim=2, algorithm='default', use_precomputed_pebble_digraph=False)[source]

Return whether the edge set is a circuit in the generic dim-rigidity matroid.

Definitions

Parameters:
  • dim (int) – Dimension of the rigidity matroid.

  • algorithm (str) –

    If "graphic" (only if dim=1), it is checked whether the graph is a union of cycles.

    If "sparsity" (only if dim=2), a (2,3)-sparse spanning subgraph is computed and it is checked (using pebble games) whether it misses only a single edge whose fundamental circuit is the whole graph.

    If "randomized", it is checked using randomized is_Rd_independent() whether removing every single edge from the graph results in an Rd-independent graph.

    If "default", then "graphic" is used for dim=1, "sparsity" for dim=2, and "randomized" for dim>=3.

  • use_precomputed_pebble_digraph (bool) – Only relevant if algorithm="sparsity". 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

>>> from pyrigi import graphDB
>>> G = graphDB.K33plusEdge()
>>> G.is_Rd_circuit()
True
>>> G.add_edge(1,2)
>>> G.is_Rd_circuit()
False

Suggested Improvements

prob parameter for the randomized algorithm

is_Rd_closed(dim=2, algorithm='default')[source]

Return whether the edge set is closed in the generic dim-rigidity matroid.

Definitions

Parameters:
  • dim (int) – Dimension of the rigidity matroid.

  • algorithm (str) – See Rd_closure() for the options.

Return type:

bool

Examples

>>> G = Graph([(0,1),(1,2),(0,2),(3,4)])
>>> G.is_Rd_closed(dim=1)
True
is_Rd_dependent(dim=2, algorithm='default', use_precomputed_pebble_digraph=False)[source]

Return whether the edge set is dependent in the generic dim-rigidity matroid.

See is_Rd_dependent() for the possible parameters.

Return type:

bool

Parameters:
  • dim (int)

  • algorithm (str)

  • use_precomputed_pebble_digraph (bool)

Definitions

Examples

>>> from pyrigi import graphDB
>>> G = graphDB.K33plusEdge()
>>> G.is_Rd_dependent()
True

Notes

See is_independent() for details.

is_Rd_independent(dim=2, algorithm='default', use_precomputed_pebble_digraph=False)[source]

Return whether the edge set is independent in the generic dim-rigidity matroid.

Definitions

Parameters:
  • dim (int) – Dimension of the rigidity matroid.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the (non-)presence of cycles is checked.

    If "sparsity" (only if dim=2), then (2,3)-sparsity is checked.

    If "randomized", the following check is performed on a random framework: a set of edges forms an independent set in the rigidity matroid if and only if it has no self-stress, i.e., there are no linear relations between the rows of the rigidity matrix.

    If "default", then "graphic" is used for dim=1, "sparsity" for dim=2, and "randomized" for dim>=3.

  • use_precomputed_pebble_digraph (bool) – Only relevant if algorithm="sparsity". 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

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

Suggested Improvements

prob parameter for the randomized algorithm.

is_critically_edge_apex()[source]

Return whether the graph is critically edge apex.

Alias for is_critically_k_edge_apex() with k=1.

Return type:

bool

Definitions

Critically edge apex graph

is_critically_k_edge_apex(k)[source]

Return whether the graph is critically k-edge apex.

Return type:

bool

Parameters:

k (int)

Definitions

Critically k-edge apex graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(5)
>>> G.is_critically_k_edge_apex(1)
True
is_critically_k_vertex_apex(k)[source]

Return whether the graph is critically k-vertex apex.

Return type:

bool

Parameters:

k (int)

Definitions

Critically k-vertex apex graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(5)
>>> G.is_critically_k_vertex_apex(1)
True
is_critically_vertex_apex()[source]

Return whether the graph is critically vertex apex.

Alias for is_critically_k_vertex_apex() with k=1.

Return type:

bool

Definitions

Critically vertex apex graph

is_edge_apex()[source]

Return whether the graph is edge apex.

Alias for is_k_edge_apex() with k=1

Return type:

bool

Definitions

Edge apex graph

is_globally_rigid(dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is globally dim-rigid.

Definitions

Global dim-rigidity

Parameters:
  • dim (int) – Dimension.

  • algorithm (str) –

    If "graphic" (only if dim=1), then 2-connectivity is checked.

    If "redundancy" (only if dim=2), then Theorem 5 is used.

    If "randomized", a probabilistic check is performed. It may give false negatives (with probability at most prob), but no false positives. See Theorem 9.

    If "default", then "graphic" is used for dim=1, "redundancy" for dim=2, and "randomized" for dim>=3.

  • prob (float) – Only relevant if algorithm="randomized". It determines the bound on the probability of the randomized algorithm to yield false negatives.

Return type:

bool

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
is_isomorphic(graph)[source]

Return whether two graphs are isomorphic.

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

Return type:

bool

Parameters:

graph (Graph)

Examples

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

Return whether the graph is k-edge apex.

Return type:

bool

Parameters:

k (int)

Definitions

k-edge apex graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(5)
>>> G.is_k_edge_apex(1)
True
is_k_redundantly_rigid(k, dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is k-redundantly dim-rigid.

Preliminary checks from Theorem 6, Theorem 5, Theorem 14, Theorem 15, Theorem 16 and Theorem 17 are used.

Definitions

k-redundant dim-rigidity

Parameters:
  • k (int) – Level of redundancy.

  • dim (int) – Dimension.

  • algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this method.

  • prob (float) –

    A bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

    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

Suggested Improvements

Improve with pebble games.

is_k_vertex_apex(k)[source]

Return whether the graph is k-vertex apex.

Return type:

bool

Parameters:

k (int)

Definitions

k-vertex apex graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(5)
>>> G.is_k_vertex_apex(1)
True
is_k_vertex_redundantly_rigid(k, dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is k-vertex redundantly dim-rigid.

Preliminary checks from Theorem 21, Theorem 22, Theorem 23, Theorem 24, Theorem 25, Theorem 26 and Theorem 27 are used.

Definitions

k-vertex redundant dim-rigidity

Parameters:
  • k (int) – level of redundancy

  • dim (int) – dimension

  • algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this method.

  • prob (float) –

    bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

    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_kl_sparse(K, L, algorithm='default', use_precomputed_pebble_digraph=False)[source]

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

Definitions

(K, L)-sparsity

Parameters:
  • K (int)

  • L (int)

  • algorithm (str) – If "pebble", the function uses the pebble game algorithm to check for sparseness. If "subgraph", it checks each subgraph following the definition. It defaults to "pebble" whenever K>0 and 0<=L<2K, otherwise to "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_kl_sparse(3,6)
True
>>> G.add_edge(0,1)
>>> G.is_kl_sparse(3,6)
False
is_kl_tight(K, L, algorithm='default', use_precomputed_pebble_digraph=False)[source]

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

Definitions

(K, L)-tightness

Parameters:
  • K (int)

  • L (int)

  • algorithm (str) – See is_kl_sparse().

  • 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.Complete(4)
>>> G.is_kl_tight(2,2)
True
>>> G1 = graphs.CompleteBipartite(4,4)
>>> G1.is_kl_tight(3,6)
False
is_linked(u, v, dim=2)[source]

Return whether a pair of vertices is dim-linked.

Lemma 2 is used for the check.

Definitions

dim-linked pair

Parameters:
  • u (Vertex)

  • v (Vertex)

  • dim (int) – Currently, only the dimension dim=2 is supported.

Return type:

bool

Examples

>>> H = Graph([[0, 1], [0, 2], [1, 3], [1, 5], [2, 3], [2, 6], [3, 5], [3, 7], [5, 7], [6, 7], [3, 6]])
>>> H.is_linked(1,7)
True
>>> H = Graph([[0, 1], [0, 2], [1, 3], [2, 3]])
>>> H.is_linked(0,3)
False
>>> H.is_linked(1,3)
True

Suggested Improvements

Implement also for other dimensions.

is_min_k_redundantly_rigid(k, dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is minimally k-redundantly dim-rigid.

Preliminary checks from Theorem 18 are used.

Definitions

Minimal k-redundant dim-rigidity

Parameters:
  • k (int) – Level of redundancy.

  • dim (int) – Dimension.

  • algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this method.

  • prob (float) –

    A bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

    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, algorithm='default', prob=0.0001)[source]

Return whether the graph is minimally k-vertex redundantly dim-rigid.

Preliminary checks from Theorem 28, Theorem 29 are used.

Definitions

Minimal k-vertex redundant dim-rigidity

Parameters:
  • k (int) – Level of redundancy.

  • dim (int) – Dimension.

  • algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this method.

  • prob (float) –

    A bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

    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, algorithm='default', prob=0.0001)[source]

Return whether the graph is minimally redundantly dim-rigid.

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

Return type:

bool

Parameters:

Definitions

Minimal redundant dim-rigidity

is_min_rigid(dim=2, algorithm='default', use_precomputed_pebble_digraph=False, prob=0.0001)[source]

Return whether the graph is minimally dim-rigid.

Definitions

Minimal dim-rigidity

Parameters:
  • dim (int) – Dimension.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the graphic matroid is used, namely, it is checked whether the graph is a tree.

    If "sparsity" (only if dim=2), then (2,3)-tightness and Theorem 1 are used.

    If "randomized", a probabilistic check is performed. It may give false negatives (with probability at most prob), but no false positives. See Theorem 4.

    If "extension_sequence" (only if dim=2), then the existence of a sequence of rigidity preserving extensions is checked, see has_extension_sequence().

    If "default", then "graphic" is used for dim=1 and "sparsity" for dim=2 and "randomized" for dim>=3.

  • use_precomputed_pebble_digraph (bool) – Only relevant if algorithm="sparsity". 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) – Only relevant if algorithm="randomized". It determines the bound on the probability of the 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
is_min_vertex_redundantly_rigid(dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is minimally vertex redundantly dim-rigid.

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

Return type:

bool

Parameters:

Definitions

Minimal vertex redundant dim-rigidity

is_redundantly_rigid(dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is redundantly dim-rigid.

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

Return type:

bool

Parameters:

Definitions

Redundant dim-rigidity

is_rigid(dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is dim-rigid.

Definitions

Generic dim-rigidity

Parameters:
  • dim (int) – Dimension.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the graphic matroid is used, namely, it is checked whether the graph is connected.

    If "sparsity" (only if dim=2), then the existence of a spanning (2,3)-tight subgraph and Theorem 1 are used.

    If "randomized", a probabilistic check is performed. It may give false negatives (with probability at most prob), but no false positives. See Theorem 4.

    If "default", then "graphic" is used for dim=1 and "sparsity" for dim=2 and "randomized" for dim>=3.

  • prob (float) – Only relevant if algorithm="randomized". It determines the bound on the probability of the 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
is_separating_set(vertices)[source]

Check if a set of vertices is a separating set.

Return type:

bool

Parameters:

vertices (list[TypeAliasForwardRef(':type:`~pyrigi.data_type.Vertex`')] | set[TypeAliasForwardRef(':type:`~pyrigi.data_type.Vertex`')])

Definitions

separating-set

Examples

>>> import pyrigi.graphDB as graphs
>>> H = graphs.Cycle(5)
>>> H.is_separating_set([1,3])
True
>>> G = Graph([[0,1],[1,2],[2,3],[2,4],[4,3],[4,5]])
>>> G.is_separating_set([2])
True
>>> G.is_separating_set([3])
False
>>> G.is_separating_set([3,4])
True
is_sparse()[source]

Return whether the graph is (2,3)-sparse.

For general \((k,\ell)\)-sparsity, see is_kl_sparse().

Return type:

bool

Definitions

(2,3)-sparsity

Examples

>>> import pyrigi.graphDB as graphs
>>> graphs.Path(3).is_sparse()
True
>>> graphs.Complete(4).is_sparse()
False
>>> graphs.ThreePrism().is_sparse()
True
is_tight()[source]

Return whether the graph is (2,3)-tight.

For general \((k,\ell)\)-tightness, see is_kl_tight().

Return type:

bool

Definitions

(2,3)-tightness

Examples

>>> import pyrigi.graphDB as graphs
>>> graphs.Path(4).is_tight()
False
>>> graphs.ThreePrism().is_tight()
True
is_vertex_apex()[source]

Return whether the graph is vertex apex.

Alias for is_k_vertex_apex() with k=1.

Return type:

bool

Definitions

Vertex apex graph

is_vertex_redundantly_rigid(dim=2, algorithm='default', prob=0.0001)[source]

Return whether the graph is vertex redundantly dim-rigid.

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

Return type:

bool

Parameters:

Definitions

vertex redundantly dim-rigid

is_weakly_globally_linked(u, v, dim=2)[source]

Return whether the vertices u and v are weakly globally dim-linked.

Theorem 11 is used for the check.

Definitions

Weakly globally linked pair

Parameters:
  • u (Vertex)

  • v (Vertex)

  • dim (int) – Currently, only the dimension dim=2 is supported.

Return type:

bool

Examples

>>> G = Graph([[0,4],[0,6],[0,7],[1,3],[1,6],[1,7],[2,6],[2,7],[3,5],[4,5],[4,7],[5,6],[5,7],[6,7]])
>>> G.is_weakly_globally_linked(0,1)
True
>>> G.is_weakly_globally_linked(1,5)
True
>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(10)
>>> G.is_weakly_globally_linked(0,1)
True

The following example is Figure 1 of the article [JV24]

>>> G = Graph([[0,1],[0,2],[0,4],[1,2],[1,4],[2,3],[3,4]])
>>> G.is_weakly_globally_linked(2,4)
True
k_extension(k, vertices, edges, new_vertex=None, dim=2, inplace=False)[source]

Return a dim-dimensional k-extension.

See also zero_extension() and one_extension().

Definitions

k-extension

Parameters:
  • k (int)

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

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

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

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

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

Return type:

Graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(5)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
>>> H = G.k_extension(2, [0, 1, 2, 3], [[0, 1], [0,2]])
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 3], [0, 4], [0, 5], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5]]
>>> G = graphs.Complete(5)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
>>> H = G.k_extension(2, [0, 1, 2, 3, 4], [[0, 1], [0,2]], dim = 3)
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 3], [0, 4], [0, 5], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> G = graphs.Path(6)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
>>> H = G.k_extension(2, [0, 1, 2], [[0, 1], [1,2]], dim = 1, inplace = True);
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5, 6] and edges [[0, 6], [1, 6], [2, 3], [2, 6], [3, 4], [4, 5]]
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5, 6] and edges [[0, 6], [1, 6], [2, 3], [2, 6], [3, 4], [4, 5]]
layout(layout_type='spring')[source]

Generate a placement of the vertices.

This method is a 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.

Return type:

int

Examples

>>> G = Graph([(0,1), (1,2)])
>>> G.max_degree()
2
max_rigid_dimension(prob=0.0001)[source]

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

For checking rigidity, the method uses a randomized algorithm, see is_rigid() for details.

Definitions

Generical rigidity

Parameters:

prob (float) –

A 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:

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

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.

min_degree()[source]

Return the minimum of the vertex degrees.

Return type:

int

Examples

>>> G = Graph([(0,1), (1,2)])
>>> G.min_degree()
1
number_of_realizations(dim=2, spherical=False, check_min_rigid=True, count_reflection=False)[source]

Count the number of complex realizations of a minimally dim-rigid graph.

Realizations in dim-dimensional sphere can be counted using spherical=True.

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 for details on installing.

Definitions

Parameters:
  • dim (int) – The dimension in which the realizations are counted. Currently, only dim=2 is supported.

  • check_min_rigid (bool) – If True, a ValueError is raised if the graph is not minimally 2-rigid If False, it is assumed that the user is inputting a minimally rigid graph.

  • spherical (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=True)
1
>>> G = graphs.ThreePrism()
>>> G.number_of_realizations() # number of planar realizations
12

Suggested Improvements

Implement the counting for dim=1.

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

Return a dim-dimensional 1-extension.

Definitions

1-extension

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

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

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

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

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

Return type:

Graph

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> H = G.one_extension([0, 1, 2], [0, 1])
>>> print(H)
Graph with vertices [0, 1, 2, 3] and edges [[0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
>>> print(G)
Graph with vertices [0, 1, 2] and edges [[0, 1], [0, 2], [1, 2]]
>>> G = graphs.ThreePrism()
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [1, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> H = G.one_extension([0, 1], [0, 1], dim=1)
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5, 6] and edges [[0, 2], [0, 3], [0, 6], [1, 2], [1, 4], [1, 6], [2, 5], [3, 4], [3, 5], [4, 5]]
>>> G = graphs.CompleteBipartite(3, 2)
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4] and edges [[0, 3], [0, 4], [1, 3], [1, 4], [2, 3], [2, 4]]
>>> H = G.one_extension([0, 1, 2, 3, 4], [0, 3], dim=4, inplace = True)
>>> print(H)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]]
>>> print(G)
Graph with vertices [0, 1, 2, 3, 4, 5] and edges [[0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]]
plot(plot_style=None, placement=None, layout='spring', **kwargs)[source]

Plot the graph.

See also PlotStyle, plot(), plot2D() and plot3D() for possible parameters for formatting. To distinguish Framework.plot() from this method, the vertex_color has a different default value.

Parameters:
  • plot_style (PlotStyle) – An instance of the PlotStyle class that defines the visual style for plotting. See PlotStyle for more information.

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

Return type:

None

Examples

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

Using keyword arguments for customizing the plot style, see PlotStyle and PlotStyle2D for all possible options.

>>> G.plot(vertex_color="#FF0000", edge_color="black", vertex_size=50)

Specifying a custom plot style

>>> from pyrigi import PlotStyle
>>> plot_style = PlotStyle(vertex_color="#FF0000")
>>> G.plot(plot_style)

Using different layout

>>> G.plot(layout="circular")

Using custom placement for vertices

>>> placement = {0: (1,2), 1: (2,3), 2: (3,4), 3: (4,5)}
>>> G.plot(placement=placement)

Combining different customizations

>>> G.plot(plot_style, layout="random", placement=placement)

The following is just to close all figures after running the example:

>>> import matplotlib.pyplot
>>> matplotlib.pyplot.close("all")
random_framework(dim=2, rand_range=None)[source]

Return a framework with random realization.

This method calls Framework.Random().

Parameters:
rigid_components(dim=2, algorithm='default', prob=0.0001)[source]

Return the list of the vertex sets of dim-rigid components.

Definitions

Rigid components

Parameters:
  • dim (int) – The dimension that is used for the rigidity check.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the connected components are returned.

    If "subgraphs-pebble" (only if dim=2), then all subgraphs are checked using is_rigid() with algorithm="pebble".

    If "pebble" (only if dim=2), then Rd_closure() with algorithm="pebble" is used.

    If "randomized", all subgraphs are checked using randomized is_rigid().

    If "default", then "graphic" is used for dim=1, "pebble" for dim=2, and "randomized" for dim>=3.

  • prob (float) –

    A bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

    Warning: this is not the probability of wrong results in this method, but is just passed on to rigidity testing.

Return type:

list[list[Vertex]]

Examples

>>> G = Graph([(0,1), (1,2), (2,3), (3,0)])
>>> G.rigid_components(algorithm="randomized")
[[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(algorithm="randomized")
[[0, 5], [2, 3], [0, 1, 2], [3, 4, 5]]

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.

For the pebble game algorithm we use the fact that the R2_closure consists of edge disjoint cliques, so we only have to determine them.

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

Definitions

(K, L)-sparsity

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

Examples

>>> from pyrigi import graphDB
>>> G = graphDB.Complete(4)
>>> H = G.spanning_kl_sparse_subgraph(2,3)
>>> print(H)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]
sum_t(other_graph, edge, t=2)[source]

Return the t-sum with other_graph along the given edge.

Return type:

Graph

Parameters:
  • other_graph (Graph)

  • edge (:type:`~pyrigi.data_type.Edge`)

  • t (int)

Definitions

t-sum

Examples

>>> G1 = Graph([[1,2],[2,3],[3,1],[3,4]])
>>> G2 = Graph([[0,1],[1,2],[2,3],[3,1]])
>>> H = G2.sum_t(G1, [1, 2], 3)
>>> print(H)
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 (Sequence[Vertex]) – 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

Suggested Improvements

Implement taking canonical before computing the integer representation.

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_type (str) – The possibilities are spring (default), circular, random or planar, see also layout().

  • vertex_style (str | list[slice(<class ‘str’>, collections.abc.Sequence[TypeAliasForwardRef(’Vertex’)], None)]) – 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 (str | dict[slice(<class ‘str’>, collections.abc.Sequence[TypeAliasForwardRef(’Edge’)], None)]) – 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.

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, 0], 1:[1, 1], 2:[2, 2], 3:[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.

Return type:

list[Vertex]

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']
zero_extension(vertices, new_vertex=None, dim=2, inplace=False)[source]

Return a dim-dimensional 0-extension.

Definitions

0-extension

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

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

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

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

Return type:

Graph

Examples

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