Pebble Digraph

Auxiliary class for directed graph used in pebble game style algorithms.

class pyrigi.graph._sparsity._pebble_digraph.PebbleDiGraph(K=None, L=None, *args, **kwargs)[source]

Bases: MultiDiGraph

Class representing a directed graph for pebble game algorithm.

It must hold that 0 < K and L < 2K.

Notes

All networkx methods in use need a wrapper - to make future developments easier.

Parameters:
property K: int

Get the value of K.

property L: int

Get the value of L.

_input_check_vertex_member(to_check)[source]

Check whether a given element is indeed a vertex and raise an error otherwise.

Return type:

None

Parameters:

to_check (:type:`~pyrigi.data_type.Vertex`)

add_edge_maintaining_digraph(u, v)[source]

Add the given edge to the pebble digraph, if possible.

Add an edge to the pebble digraph if it is possible and choose the correct orientation. This also checks the possibility of adding the edge and return True or False depending on it.

Return type:

bool

Parameters:

  • u (:type:`~pyrigi.data_type.Vertex`)

  • v (:type:`~pyrigi.data_type.Vertex`)

add_edges_maintaining_digraph(edges)[source]

Run add_edge_maintaining_digraph for each edge in the list.

Note that this might not add all the edges, only the edges that take part of the maximal sparse subgraph.

Return type:

None

Parameters:

edges (list[TypeAliasForwardRef(':type:`~pyrigi.data_type.DirectedEdge`')])

can_add_edge_between_vertices(u, v)[source]

Check whether the edge (u, v) can be added to the pebble digraph.

Return type:

bool

Parameters:

  • u (:type:`~pyrigi.data_type.Vertex`)

  • v (:type:`~pyrigi.data_type.Vertex`)

fundamental_circuit(u, v)[source]

Return the fundamental \((k, l)\)-matroid circuit of the edge uv.

If the edge uv is independent, None is returned.

Return type:

{set[MyTypeAliasForwardRef(’Vertex’)]}

Parameters:

  • u (:type:`~pyrigi.data_type.Vertex`)

  • v (:type:`~pyrigi.data_type.Vertex`)

in_degree(vertex)[source]

Return the number of edges leading to vertex.

Return type:

int

Parameters:

vertex (:type:`~pyrigi.data_type.Vertex`)

number_of_edges()[source]

Return the number of directed edges.

Return type:

int

out_degree(vertex)[source]

Return the number of edges leading out from vertex.

Return type:

int

Parameters:

vertex (:type:`~pyrigi.data_type.Vertex`)

redirect_edge_to_head(edge, vertex_to)[source]

Redirect given edge to the given head.

Parameters:

  • edge (DirectedEdge) – A directed edge to redirect.

  • vertex_to (Vertex) – A vertex to which the edge should point to. The vertex must be part of the edge.

Return type:

None

set_K_and_L(K, L)[source]

Set K and L.

After doing so, the directions of the edges may have to be recomputed.

Parameters:

  • K (int) – K is integer and 0 < K.

  • L (int) – L is integer and 0 <= L. Also, L < 2K.

Return type:

None