#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: | 6b81097bc80245f66a6d94f8596846d0e5a6df98
u/jaanos/add_is_partial_cube | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
Comment:
Hello,
Here is a first-pass review.
- Has a simpler expression:
{{{
- CG = DiGraph({v: {w: (v, w) for w in G[v]} for v in G})
+ CG = DiGraph(G)
}}}
- 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`
- `CG/UF/NL` I saw that they were the names from the original source code,
but
would you mind 'expanding' them?
- 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`.
- 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):
}}}
- 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}
}}}
- 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.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/19985#comment:20>
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.
