#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 jaanos):
Hi!
> - Has a simpler expression:
> {{{
> - CG = DiGraph({v: {w: (v, w) for w in G[v]} for v in G})
> + CG = DiGraph(G)
> }}}
The point here is to set edge labels. Simply constructing a `DiGraph` from
`G` will keep the old edge labels (if any).
> - That's a full graph copy, right? `O_o`
> {{{
> + if not Graph(CG).is_bipartite():
> }}}
>
> Wouldn't it be better to maintain the undirected graph too? At this
level, I
> would almost be tempted by `GenericGraph.is_bipartite(CG)` `O_o`
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.
> - `CG/UF/NL` I saw that they were the names from the original source
code, but
> would you mind 'expanding' them?
OK, they are now `contracted`, `unionfind` and `available` now, and `LG`
and `NG` have been changed to `level` and `newgraph`, respectively.
> - Don't know if that interests you, but by relabelling the graph on
`0,...,n`
> you could use lists instead of dictionaries, e.g. for `bitvec`.
I could, but since we might be building a dictionary as a certificate
anyway, I don't think there's much gain here.
> - Computing the number of connected components is not necessary to
initialize
> the graphs, and has a linear-time cost.
> {{{
> - NG = DiGraph(labeled.connected_components_number())
> + NG = DiGraph()
> }}}
>
> - What about `NG.has_edge(vi,wi)`?
> {{{
> + if wi in NG.neighbors_out(vi):
> }}}
OK, both changed.
> - As you do not seem to do anything with the dictionaries stored in
`action`,
> could you turn them into sets instead?
> {{{
> - action = {v: {} for v in g}
> + action = {v: set() for v in g}
> }}}
The original algorithm used the values in the dictionaries to reconstruct
the graph. Indeed, here we don't use them, so I changed the dictionaries
to sets.
> - What is the purpose of all the code that appears after this line?
> {{{
> + g = DiGraph({v: {w: UF.find((v, w)) for w in G[v]} for v in G})
> }}}
> It does not appear in `partial_cube.py` but in `medium.py`, and I do
not see
> what you need it for.
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.
Janoš
--
Ticket URL: <http://trac.sagemath.org/ticket/19985#comment:22>
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.
