#19985: Add is_partial_cube
-------------------------------------+-------------------------------------
Reporter: jaanos | Owner:
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-7.1
Component: graph theory | Resolution:
Keywords: graphs partial | Merged in:
cubes | Reviewers:
Authors: Janoš Vidali | Work issues:
Report Upstream: N/A | Commit:
Branch: | 35072c3f3cf7d8394fbf634375110a501b084a64
u/jaanos/add_is_partial_cube | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Jano\u0161 Vidali', 'oldvalue': ''}):
* status: new => needs_info
* author: => Janoš Vidali
* cc: ncohen (added)
* component: PLEASE CHANGE => graph theory
* keywords: => graphs partial cubes
* commit: => 35072c3f3cf7d8394fbf634375110a501b084a64
* type: PLEASE CHANGE => enhancement
Old description:
New description:
This ticket adds a method `is_partial_cube` to the `Graph` class, which
checks whether a 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. If requested, this labelling can also be returned by the method.
The code for this method comes from the PADS library by David Eppstein,
which is available at http://www.ics.uci.edu/~eppstein/PADS/. The library
is available under the MIT license, and I have also obtained permission
from the author via email. The algorithm in question has been described in
a paper available at http://arxiv.org/pdf/0705.1025.pdf.
The code has been changed to utilize Sage's structures (namely graphs,
digraphs and disjoint sets). However, specialized breadth-first and depth-
first search methods for graphs from the PADS library have also been
added.
--
Comment:
Before this goes into review, here are some notes and questions:
* Currently, there are no docstrings for the new methods - of course I
will add them, but the current commit was intended just for testing
whether the method works as expected.
* Should I mention in the doc that the code has originally been made
available under the MIT license?
* The new BFS method is named `breadth_first_level_search`. It generates
dictionaries whose keys are vertices at each level of the search, and
values are sets of neighbours on the next level for each key vertex. This
way, a vertex may appear in multiple sets on the same level - this is
needed to correctly produce the labellings.
* The new DFS method is named `depth_first_traversal`. It generates the
edges followed on both ways of the depth-first search, together with the
information on the direction taken (`True` for forward, `False` for
backward). The method is used in the final verification step of the
algorithm. Although the existing DFS could be adapted to work this way if
requested, I chose to keep this a separate method to avoid needlessly
degrading the performance of algorithms utilizing the generic DFS.
* If a `certificate` is requested, the method raises an `EmptySetError`
describing what went wrong in case the graph is not a partial cube, and
returns a dictionary mapping vertices to (0,1)-strings otherwise. Is this
OK, or should I change to returning pairs, as with other methods returning
a certificate? Should I use some exception other than `EmptySetError`? I
chose this as it is also used in `traveling_salesman_problem`.
Janoš
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=9b381059a534e3eb17ef7ec3cd2e43cf9063cff5
9b38105]||{{{Add D. Eppstein's algorithm for recognizing partial
cubes}}}||
||[http://git.sagemath.org/sage.git/commit/?id=35072c3f3cf7d8394fbf634375110a501b084a64
35072c3]||{{{Merge branch 'develop' into is_partial_cube}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19985#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
