Partial cubes#

The code in this module that recognizes partial cubes is originally from the PADS library by David Eppstein, which is available at http://www.ics.uci.edu/~eppstein/PADS/ under the MIT license. It has a quadratic runtime and has been described in [Epp2008].

For more information on partial cubes, see the Wikipedia article Partial cube.

Recognition algorithm#

Definitions#

A partial cube is an isometric subgraph \(G\) of a CubeGraph() (of possibly high dimension). Consequently, the vertices of \(G\) can be labelled with binary sequences in such a way that the distance between two vertices \(u,v\in G\) is the Hamming distance between their labels.

Tokens and their action: in the terminology of [Epp2008], a token represents a transition of the form:

switch the k-th bit of the binary string from 0 to 1

Each token can be matched with a ‘reversed’ token that performs the same switch in the opposite direction. Alternatively, a token can be seen as a set of disjoint (directed) edges of \(G\), corresponding to the transitions. When a vertex \(v\in G\) is the source of such an edge, it is said that the token acts on \(v\).

Observations#

Shortest paths: in a hypercube, a shortest path between two vertices uses each token at most once. Furthermore, it cannot use both a token and it reverse.

Cycles: a cycle in a partial cube is necessarily even, as hypercubes are bipartite. If an edge \(e\) of a cycle \(C\) belongs to a token \(T\), then the edge opposite to \(e\) in \(C\) belongs to the reverse of \(T\).

Incident edges: all \(2d_G(v)\) arcs incident to a given vertex belong to as many different tokens.

Algorithm#

Labeling: Iteratively, the algorithm selects a vertex \(v\in G\), which is naturally associated to \(2d(v)\) tokens. It then performs a breadth-first search from \(v\), applying the previous observation on cycles to attribute a token to some of the edges it meets. None of the edges whose token remains undecided after this step can belong to one of those \(2d(v)\) tokens, by virtue of the observation on shortest paths.

The labeled edges can then be simplified (contracted) if the previous step did not lead to a contradiction, and the procedure is applied again until the graph is contracted to a single vertex and all edges are labeled.

A partial cube is correctly labeled at this step, but some other graphs can also satisfy the procedure.

Checking the labeling: once all tokens are defined and the vertices are labeled with a binary string, we check that they define an isometric subgraph of the hypercube. To ensure that the distance \(d(v_0,u)\) is what we expect for any vertex \(u\), it is sufficient to find, for any vertex \(u\), a neighbor \(n_u\) of \(u\) whose Hamming distance with \(v_0\) is strictly less than the Hamming distance between \(u\) and \(v_0\). Here is the algorithm used to check the labeling:

  • For an initial vertex \(v\), run a BFS starting from \(v\), and associate to every other vertex \(u\) a token that brings \(u\) closer to \(v\). This yields shortest paths from every vertex to \(v\).

  • Assuming that the information is computed (and correct) for \(v\), it is easy to update it for a neighbor \(v'\) of \(v\). Indeed, if we write \(T\) the token that turns \(v\) into \(v'\), only the vertices which were associated with the reverse of \(T\) need to select a new neighbour. All others can remain as they were previously.

    With this second observation, one can efficiently check that the distance between all pairs of vertices are what they should be. In the implementation, the sequence of the sources \((v, v', ...)\) is given by a depth-first search.

Functions#

Generate a sequence of dictionaries, each mapping the vertices at distance i from start to the set of their neighbours at distance i+1.

Originally written by D. Eppstein for the PADS library (http://www.ics.uci.edu/~eppstein/PADS/).

INPUT:

  • G – a graph to perform the search on.

  • start – vertex or list of vertices from which to start the traversal.

EXAMPLES:

sage: H = digraphs.DeBruijn(3,2)                                                # needs sage.combinat
sage: list(sage.graphs.partial_cube.breadth_first_level_search(H, '00'))        # needs sage.combinat
[{'00': {'01', '02'}},
 {'01': {'10', '11', '12'}, '02': {'20', '21', '22'}},
 {'10': set(),
  '11': set(),
  '12': set(),
  '20': set(),
  '21': set(),
  '22': set()}]

>>> from sage.all import *
>>> H = digraphs.DeBruijn(Integer(3),Integer(2))                                                # needs sage.combinat
>>> list(sage.graphs.partial_cube.breadth_first_level_search(H, '00'))        # needs sage.combinat
[{'00': {'01', '02'}},
 {'01': {'10', '11', '12'}, '02': {'20', '21', '22'}},
 {'10': set(),
  '11': set(),
  '12': set(),
  '20': set(),
  '21': set(),
  '22': set()}]
sage.graphs.partial_cube.depth_first_traversal(G, start)[source]#

Generate a sequence of triples (v,w,edgetype) for DFS of graph G.

Originally written by D. Eppstein for the PADS library (http://www.ics.uci.edu/~eppstein/PADS/).

INPUT:

  • G – a graph to perform the search on.

  • start – vertex or list of vertices from which to start the traversal.

OUTPUT:

  • a generator of triples (v,w,edgetype), where edgetype is True if the algorithm is progressing via the edge vw, or False if the algorithm is backtracking via the edge wv.

EXAMPLES:

sage: H = digraphs.DeBruijn(3,2)                                                # needs sage.combinat
sage: t = list(sage.graphs.partial_cube.depth_first_traversal(H, '00'))         # needs sage.combinat
sage: len(t)                                                                    # needs sage.combinat
16

>>> from sage.all import *
>>> H = digraphs.DeBruijn(Integer(3),Integer(2))                                                # needs sage.combinat
>>> t = list(sage.graphs.partial_cube.depth_first_traversal(H, '00'))         # needs sage.combinat
>>> len(t)                                                                    # needs sage.combinat
16
sage.graphs.partial_cube.is_partial_cube(G, certificate=False)[source]#

Test whether the given graph is a partial cube.

A partial cube is a graph that can be isometrically embedded into a hypercube, i.e., its vertices can be labelled with (0,1)-vectors of some fixed length such that the distance between any two vertices in the graph equals the Hamming distance of their labels.

Originally written by D. Eppstein for the PADS library (http://www.ics.uci.edu/~eppstein/PADS/), see also [Epp2008]. The algorithm runs in \(O(n^2)\) time, where \(n\) is the number of vertices. See the documentation of partial_cube for an overview of the algorithm.

INPUT:

  • certificate – boolean (default: False); this function returns True or False according to the graph, when certificate = False. When certificate = True and the graph is a partial cube, the function returns (True, mapping), where mapping is an isometric mapping of the vertices of the graph to the vertices of a hypercube ((0, 1)-strings of a fixed length). When certificate = True and the graph is not a partial cube, (False, None) is returned.

EXAMPLES:

The Petersen graph is not a partial cube:

sage: g = graphs.PetersenGraph()
sage: g.is_partial_cube()
False

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> g.is_partial_cube()
False

All prisms are partial cubes:

sage: g = graphs.CycleGraph(10).cartesian_product(graphs.CompleteGraph(2))
sage: g.is_partial_cube()
True

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(10)).cartesian_product(graphs.CompleteGraph(Integer(2)))
>>> g.is_partial_cube()
True