#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: | 618ab7378d84a24d2c572f58e4d7df23586ba80a
u/jaanos/add_is_partial_cube | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ncohen):
Hellooooo,
> The point here is to set edge labels. Simply constructing a `DiGraph`
from `G` will keep the old edge labels (if any).
Dead right, my mistake.
> I *think* it may be actually enough to check that the original graph is
bipartite, and then also all contractions must be bipartite. I will ask
the author, just to be sure.
Okay !
> OK, they are now `contracted`, `unionfind` and `available` now, and `LG`
and `NG` have been changed to `level` and `newgraph`, respectively.
Thanks,
> I could, but since we might be building a dictionary as a certificate
anyway, I don't think there's much gain here.
Okayokay. I thought a bit about it, and it would be much more troublesome
than I first expected indeed.
> In the case the graph is not a partial cube, the first part of the
algorithm may still produce a labelling, which then needs to be checked
(see for example Lemma 11 in the paper). An example would be a graph with
graph6 string `Fs_Wo` - this fails the check that no two edges on the same
vertex should have the same label.
I thought a bit about this, and it does not seem very hard to check that a
vertex labelling is correct (a sample of code that does it follows) but
perhaps this code is 'theoretically' `n^2log(n)` instead of `n^2`.
Considering the efficiency of Python (the `n^2` part) and the efficiency
of the `log(n)` part (bitwise operations), however, I wonder if it could
not be faster than another Python `n^2` implementation. What do you think?
This code assumes what I believe we can assume: that after the labelling
is picked, two adjacent vertices differ by one 'bit' and that this bit is
the edge's label. This amounts to being sure that the graph is indeed a
*subgraph* of a high-dimension cube, but not that it is isometric. In
order to check that it is isometric, I believe that it is sufficient to
run the following code.
{{{
#!python
def check_labelling(G):
# Assumptions:
#
# - We assume that the vertices are integers, whose base-2
representation
# represents the coordinates
#
# - We also assume that every edge corresponds to the switching of one
bit
# in that base-2 representation or a vertex' name
# This dictionary associates to each vertex the set of bits whose
switching
# yields one of its neighbors:
action = {v: set() for v in G}
for u,v in G.edge_iterator(labels=False):
diff = u^v
action[u].add(diff)
action[v].add(diff)
action_bitset = {v: sum(action[v]) for v in G}
# We now check that, for every pair u,v of vertices, there is a
neighbor u'
# of u such that:
# hamming_distance(u,v) = hammin_distance(u',v) + 1
for u in G:
for v in G:
diff = u^v
if (action_bitset[u] & diff == 0 and
u != v):
return False
return True
}}}
Example in Sage:
{{{
sage: g = graphs.CubeGraph(5).relabel(lambda
x:Integer(x,base=2),inplace=False)
sage: check_labelling(g)
True
sage: g.delete_edge(8,24)
sage: check_labelling(g)
False
}}}
Please tell me what you think,
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/19985#comment:23>
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.
