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. Seenetworkx.Graph
for the other input formats or use class methodsfrom_vertices_and_edges()
orfrom_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.
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
-dimensionalk
-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()
.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
-dimensionalk
-extension.one_extension
(vertices, edge[, new_vertex, ...])Return a
dim
-dimensional 1-extension.sum_t
(other_graph, edge[, t])Return the
t
-sum withother_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.
Return whether the graph is critically edge apex.
Return whether the graph is critically
k
-edge apex.Return whether the graph is critically
k
-vertex apex.Return whether the graph is critically vertex apex.
Return whether the graph is edge apex.
is_isomorphic
(graph)Return whether two graphs are isomorphic.
Return whether the graph is
k
-edge apex.Return whether the graph is
k
-vertex apex.Return whether the graph is vertex apex.
Return the maximum of the vertex degrees.
Return the minimum of the vertex degrees.
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
-redundantlydim
-rigid.is_k_vertex_redundantly_rigid
(k[, dim, ...])Return whether the graph is
k
-vertex redundantlydim
-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
-redundantlydim
-rigid.is_min_k_vertex_redundantly_rigid
(k[, dim, ...])Return whether the graph is minimally
k
-vertex redundantlydim
-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
andv
are weakly globallydim
-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.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 ifdim=1
), then the closure is computed using connected components.If
"pebble"
(only ifdim=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 fordim=1
,"pebble"
fordim=2
and"randomized"
fordim>=3
.
- Return type:
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
andother
.Definitions
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.
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.
- add_edges(edges)[source]¶
Alias for
networkx.Graph.add_edges_from()
.
- add_vertex(vertex)[source]¶
Alias for
networkx.Graph.add_node()
.
- add_vertices(vertices)[source]¶
Alias for
networkx.Graph.add_nodes_from()
.
- 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:
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()
requiresscipy
. 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 fork
such thatk_min <= k <= k_max
are considered.Definitions
- Parameters:
- Return type:
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
-dimensionalk
-extensions.Definitions
- Parameters:
- Return type:
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
- Parameters:
- Return type:
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:
Examples
>>> G = Graph([(0,1), (1,2)]) >>> G.degree_sequence() [1, 2, 1]
- delete_edge(edge)[source]¶
Alias for
networkx.Graph.remove_edge()
- delete_edges(edges)[source]¶
Alias for
networkx.Graph.remove_edges_from()
.
- delete_vertex(vertex)[source]¶
Alias for
networkx.Graph.remove_node()
.
- delete_vertices(vertices)[source]¶
Alias for
networkx.Graph.remove_nodes_from()
.
- 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
) – IfTrue
, all edges are returned as tuples instead of lists.- Return type:
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 fork
from 0 to2 * dim - 1
are considered. The sequence then starts from a complete graph ondim
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
- 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 ofk_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:
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:
- 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.
- classmethod from_vertices(vertices)[source]¶
Create a graph with no edges from a list of vertices.
Examples
>>> from pyrigi import Graph >>> G = Graph.from_vertices([3, 1, 7, 2, 12, 3, 0]) >>> 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:
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
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
.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 ifdim=1
), it is checked whether the graph is a union of cycles.If
"sparsity"
(only ifdim=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 randomizedis_Rd_independent()
whether removing every single edge from the graph results in an Rd-independent graph.If
"default"
, then"graphic"
is used fordim=1
,"sparsity"
fordim=2
, and"randomized"
fordim>=3
.use_precomputed_pebble_digraph (
bool
) – Only relevant ifalgorithm="sparsity"
. IfTrue
, the pebble digraph present in the cache is used. IfFalse
, recompute the pebble digraph. UseTrue
only if you are certain that the pebble game digraph is consistent with the graph.
- Return type:
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
) – SeeRd_closure()
for the options.
- Return type:
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.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 ifdim=1
), then the (non-)presence of cycles is checked.If
"sparsity"
(only ifdim=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 fordim=1
,"sparsity"
fordim=2
, and"randomized"
fordim>=3
.use_precomputed_pebble_digraph (
bool
) – Only relevant ifalgorithm="sparsity"
. IfTrue
, the pebble digraph present in the cache is used. IfFalse
, recompute the pebble digraph. UseTrue
only if you are certain that the pebble game digraph is consistent with the graph.
- Return type:
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()
withk=1
.- Return type:
Definitions
- is_critically_k_edge_apex(k)[source]¶
Return whether the graph is critically
k
-edge apex.Definitions
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.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()
withk=1
.- Return type:
Definitions
- is_edge_apex()[source]¶
Return whether the graph is edge apex.
Alias for
is_k_edge_apex()
withk=1
- Return type:
Definitions
- is_globally_rigid(dim=2, algorithm='default', prob=0.0001)[source]¶
Return whether the graph is globally
dim
-rigid.Definitions
- Parameters:
dim (
int
) – Dimension.algorithm (
str
) –If
"graphic"
(only ifdim=1
), then 2-connectivity is checked.If
"redundancy"
(only ifdim=2
), then Theorem 5 is used.If
"randomized"
, a probabilistic check is performed. It may give false negatives (with probability at mostprob
), but no false positives. See Theorem 9.If
"default"
, then"graphic"
is used fordim=1
,"redundancy"
fordim=2
, and"randomized"
fordim>=3
.prob (
float
) – Only relevant ifalgorithm="randomized"
. It determines the bound on the probability of the randomized algorithm to yield false negatives.
- Return type:
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()
.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.Definitions
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
-redundantlydim
-rigid.Preliminary checks from Theorem 6, Theorem 5, Theorem 14, Theorem 15, Theorem 16 and Theorem 17 are used.
Definitions
- Parameters:
k (
int
) – Level of redundancy.dim (
int
) – Dimension.algorithm (
str
) – Seeis_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:
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.Definitions
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 redundantlydim
-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 redundancydim (
int
) – dimensionalgorithm (
str
) – Seeis_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:
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
- 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"
wheneverK>0
and0<=L<2K
, otherwise to"subgraph"
.use_precomputed_pebble_digraph (
bool
) – IfTrue
, the pebble digraph present in the cache is used. IfFalse
, recompute the pebble digraph. UseTrue
only if you are certain that the pebble game digraph is consistent with the graph.
- Return type:
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
- Parameters:
K (
int
)L (
int
)algorithm (
str
) – Seeis_kl_sparse()
.use_precomputed_pebble_digraph (
bool
) – IfTrue
, the pebble digraph present in the cache is used. IfFalse
, recompute the pebble digraph. UseTrue
only if you are certain that the pebble game digraph is consistent with the graph.
- Return type:
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
- Parameters:
- Return type:
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
-redundantlydim
-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
) – Seeis_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:
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 redundantlydim
-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
) – Seeis_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:
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()
(usingk=1
) for details.Definitions
- 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
- Parameters:
dim (
int
) – Dimension.algorithm (
str
) –If
"graphic"
(only ifdim=1
), then the graphic matroid is used, namely, it is checked whether the graph is a tree.If
"sparsity"
(only ifdim=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 mostprob
), but no false positives. See Theorem 4.If
"extension_sequence"
(only ifdim=2
), then the existence of a sequence of rigidity preserving extensions is checked, seehas_extension_sequence()
.If
"default"
, then"graphic"
is used fordim=1
and"sparsity"
fordim=2
and"randomized"
fordim>=3
.use_precomputed_pebble_digraph (
bool
) – Only relevant ifalgorithm="sparsity"
. IfTrue
, the pebble digraph present in the cache is used. IfFalse
, recompute the pebble digraph. UseTrue
only if you are certain that the pebble game digraph is consistent with the graph.prob (
float
) – Only relevant ifalgorithm="randomized"
. It determines the bound on the probability of the randomized algorithm to yield false negatives.
- Return type:
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()
(usingk=1
) for details.Definitions
- is_redundantly_rigid(dim=2, algorithm='default', prob=0.0001)[source]¶
Return whether the graph is redundantly
dim
-rigid.See
is_k_redundantly_rigid()
(usingk=1
) for details.Definitions
- is_rigid(dim=2, algorithm='default', prob=0.0001)[source]¶
Return whether the graph is
dim
-rigid.Definitions
- Parameters:
dim (
int
) – Dimension.algorithm (
str
) –If
"graphic"
(only ifdim=1
), then the graphic matroid is used, namely, it is checked whether the graph is connected.If
"sparsity"
(only ifdim=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 mostprob
), but no false positives. See Theorem 4.If
"default"
, then"graphic"
is used fordim=1
and"sparsity"
fordim=2
and"randomized"
fordim>=3
.prob (
float
) – Only relevant ifalgorithm="randomized"
. It determines the bound on the probability of the randomized algorithm to yield false negatives.
- Return type:
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:
- Parameters:
vertices (list[TypeAliasForwardRef(':type:`~pyrigi.data_type.Vertex`')] | set[TypeAliasForwardRef(':type:`~pyrigi.data_type.Vertex`')])
Definitions
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:
Definitions
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:
Definitions
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()
withk=1
.- Return type:
Definitions
- 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()
(usingk=1
) for details.Definitions
- is_weakly_globally_linked(u, v, dim=2)[source]¶
Return whether the vertices
u
andv
are weakly globallydim
-linked.Theorem 11 is used for the check.
Definitions
- Parameters:
- Return type:
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
-dimensionalk
-extension.See also
zero_extension()
andone_extension()
.Definitions
- 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 bedim + k
of them.edges (
Sequence
[Edge
]) – A list of edges that are deleted. The endvertices of all the edges must be contained in the listvertices
. The edges must be contained in the graph and there must bek
of them.new_vertex (
Vertex
) – Newly added vertex is named according to this parameter. IfNone
, the name is set as the lowest possible integer value greater or equal than the number of nodes.dim (
int
) – The dimension in which thek
-extension is created.inplace (
bool
) – IfTrue
, the graph is modified, otherwise a new modified graph is created, while the original graph remains unchanged (default).
- Return type:
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()
andplanar_layout()
.
- max_degree()[source]¶
Return the maximum of the vertex degrees.
- Return type:
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
- 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 typeInf
.
- min_degree()[source]¶
Return the minimum of the vertex degrees.
- Return type:
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 usingspherical=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, onlydim=2
is supported.check_min_rigid (
bool
) – IfTrue
, aValueError
is raised if the graph is not minimally 2-rigid IfFalse
, it is assumed that the user is inputting a minimally rigid graph.spherical (
bool
) – IfTrue
, the number of spherical realizations of the graph is returned. IfFalse
(default), the number of planar realizations is returned.count_reflection (
bool
) – IfTrue
, the number of realizations is computed modulo direct isometries. But reflection is counted to be non-congruent as used in [CGG+18] and [GGS20]. IfFalse
(default), reflection is not counted.
- Return type:
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
- Parameters:
vertices (
Sequence
[Vertex
]) – A new vertex is connected to these vertices. All the vertices must be contained in the graph and there must bedim + 1
of them.edge (
Edge
) – An edge with endvertices from the listvertices
that is deleted. The edge must be contained in the graph.new_vertex (
Vertex
) – Newly added vertex is named according to this parameter. IfNone
, 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
) – IfTrue
, the graph is modified, otherwise a new modified graph is created, while the original graph remains unchanged (default).
- Return type:
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()
andplot3D()
for possible parameters for formatting. To distinguishFramework.plot()
from this method, thevertex_color
has a different default value.- Parameters:
plot_style (
PlotStyle
) – An instance of thePlotStyle
class that defines the visual style for plotting. SeePlotStyle
for more information.placement (
dict
[Vertex
,Point
]) – Ifplacement
is not specified, then it is generated depending on parameterlayout
.layout (
str
) – The possibilities arespring
(default),circular
,random
orplanar
, see alsolayout()
.
- Return type:
Examples
>>> G = Graph([(0,1), (1,2), (2,3), (0,3)]) >>> G.plot()
Using keyword arguments for customizing the plot style, see
PlotStyle
andPlotStyle2D
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()
.
- rigid_components(dim=2, algorithm='default', prob=0.0001)[source]¶
Return the list of the vertex sets of
dim
-rigid components.Definitions
- Parameters:
dim (
int
) – The dimension that is used for the rigidity check.algorithm (
str
) –If
"graphic"
(only ifdim=1
), then the connected components are returned.If
"subgraphs-pebble"
(only ifdim=2
), then all subgraphs are checked usingis_rigid()
withalgorithm="pebble"
.If
"pebble"
(only ifdim=2
), thenRd_closure()
withalgorithm="pebble"
is used.If
"randomized"
, all subgraphs are checked using randomizedis_rigid()
.If
"default"
, then"graphic"
is used fordim=1
,"pebble"
fordim=2
, and"randomized"
fordim>=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:
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
- Parameters:
- Return type:
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 withother_graph
along the given edge.Definitions
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:
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 thetikz
package.- Parameters:
placement (
dict
[Vertex
,Point
]) – Ifplacement
is not specified, then it is generated depending on parameterlayout
.layout_type (
str
) – The possibilities arespring
(default),circular
,random
orplanar
, see alsolayout()
.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:
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:
- vertex_list()[source]¶
Return the list of vertices.
The output is sorted if possible, otherwise, the internal order is used instead.
Examples
>>> G = Graph.from_vertices_and_edges([2, 0, 3, 1], [[0, 1], [0, 2], [0, 3]]) >>> G.vertex_list() [0, 1, 2, 3]
>>> G = Graph.from_vertices(['c', 'a', 'b']) >>> G.vertex_list() ['a', 'b', 'c']
>>> G = Graph.from_vertices(['b', 1, 'a']) # incomparable vertices >>> G.vertex_list() ['b', 1, 'a']
- zero_extension(vertices, new_vertex=None, dim=2, inplace=False)[source]¶
Return a
dim
-dimensional 0-extension.Definitions
- Parameters:
vertices (
Sequence
[Vertex
]) – A new vertex is connected to these vertices. All the vertices must be contained in the graph and there must bedim
of them.new_vertex (
Vertex
) – Newly added vertex is named according to this parameter. IfNone
, 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
) – IfTrue
, the graph is modified, otherwise a new modified graph is created, while the original graph remains unchanged (default).
- Return type:
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]]