Sparsity

This module provides algorithms related to graph sparsity.

pyrigi.graph._sparsity.sparsity.is_kl_sparse(graph, K, L, algorithm='default', use_precomputed_pebble_digraph=False)[source]

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

Definitions

(K, L)-sparsity

Parameters:

  • graph (Graph)

  • K (int)

  • L (int)

  • algorithm (str) – If "pebble", the function uses the pebble game algorithm to check for sparseness (see Algorithm 2). 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()
>>> is_kl_sparse(G, 3,6)
True
>>> G.add_edge(0,1)
>>> is_kl_sparse(G, 3,6)
False
pyrigi.graph._sparsity.sparsity.is_kl_tight(graph, K, L, algorithm='default', use_precomputed_pebble_digraph=False)[source]

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

Definitions

(K, L)-tightness

Parameters:

  • graph (Graph)

  • 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)
>>> is_kl_tight(G, 2,2)
True
>>> G1 = graphs.CompleteBipartite(4,4)
>>> is_kl_tight(G1, 3,6)
False
pyrigi.graph._sparsity.sparsity.spanning_kl_sparse_subgraph(graph, 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:

  • graph (Graph)

  • 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 = spanning_kl_sparse_subgraph(G, 2,3)
>>> print(H)
Graph with vertices [0, 1, 2, 3] and edges [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]