Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" 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 [Eppstein2008]_.
For more information on partial cubes, see the :wikipedia:`Partial cube`.
REFERENCE:
.. [Eppstein2008] David Eppstein, "Recognizing partial cubes in quadratic time", J. Graph Algorithms and Applications 15 (2): 269-293, 2011. :arxiv:`0705.1025`
Recognition algorithm ---------------------
Definitions ^^^^^^^^^^^
A **partial cube** is an isometric subgraph `G` of a :meth:`~sage.graphs.graph_generators.GraphGenerators.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 [Eppstein2008]_, 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 --------- """
def breadth_first_level_search(G, start): r""" 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) sage: list(sage.graphs.partial_cube.breadth_first_level_search(H, '00')) [{'00': {'01', '02'}}, {'01': {'10', '11', '12'}, '02': {'20', '21', '22'}}, {'10': set(), '11': set(), '12': set(), '20': set(), '21': set(), '22': set()}]
""" currentLevel = start else:
def depth_first_traversal(G, start): r""" 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) sage: t = list(sage.graphs.partial_cube.depth_first_traversal(H, '00')) sage: len(t) 16
"""
continue
def is_partial_cube(G, certificate=False): r""" 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 [Eppstein2008]_. The algorithm runs in `O(n^2)` time, where `n` is the number of vertices. See the documentation of :mod:`~sage.graphs.partial_cube` for an overview of the algorithm.
INPUT:
- ``certificate`` (boolean; ``False``) -- The 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
All prisms are partial cubes::
sage: g = graphs.CycleGraph(10).cartesian_product(graphs.CompleteGraph(2)) sage: g.is_partial_cube() True
TESTS:
The returned mapping is an isometric embedding into a hypercube::
sage: g = graphs.DesarguesGraph() sage: _, m = g.is_partial_cube(certificate = True) sage: m # random {0: '00000', 1: '00001', 2: '00011', 3: '01011', 4: '11011', 5: '11111', 6: '11110', 7: '11100', 8: '10100', 9: '00100', 10: '01000', 11: '10001', 12: '00111', 13: '01010', 14: '11001', 15: '10111', 16: '01110', 17: '11000', 18: '10101', 19: '00110'} sage: all(all(g.distance(u, v) == len([i for i in range(len(m[u])) if m[u][i] != m[v][i]]) for v in m) for u in m) True
A graph without vertices is trivially a partial cube::
sage: Graph().is_partial_cube(certificate = True) (True, {})
"""
else: return True
else:
return fail
# Initial sanity check: are there few enough edges? # Needed so that we don't try to use union-find on a dense # graph and incur superquadratic runtimes. return fail
# Check for bipartiteness. # This ensures also that each contraction will be bipartite.
# Set up data structures for algorithm: # - contracted: contracted graph at current stage of algorithm # - unionfind: union find data structure representing known edge equivalences # - available: limit on number of remaining available labels
# Main contraction loop in place of the original algorithm's recursion # Find max degree vertex in contracted, and update label limit return fail
# Set up bitvectors on vertices
# Breadth first search to propagate bitvectors to the rest of the graph
# Make graph of labeled edges and union them together return fail contracted.edge_label(root, neighbor)) contracted.edge_label(neighbor, root))
# Map vertices to components of labeled-edge graph
# generate new compressed subgraph return fail else:
# Make a digraph with edges labeled by the equivalence classes in unionfind
# Associates to a vertex the token that acts on it, an check that # no two edges on a single vertex have the same label return fail
# Associate every token to its reverse
# A token T is said to be 'active' for a vertex u if it takes u # one step closer to the source in terms of distance. The 'source' # is initially 'initialState'. See the module's documentation for # more explanations.
# Find list of tokens that lead to the initial state return fail
# Rest of data structure: point from states to list and list to states
"""Find the next token that is effective for v.""" if activeTokens[i] is not None and activeTokens[i] in action[v])
# Initialize isometric embedding into a hypercube
# Set initial active states except StopIteration: return fail
# Traverse the graph, maintaining active tokens
# Add token to end of list, point to it from old state
# Inactivate reverse token, find new token for its states # # (the 'active' token of 'current' is necessarily the label of # (current, previous)) except StopIteration: return fail
# All checks passed, return the result else: |