#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: |
-------------------------------------+-------------------------------------
Comment (by ncohen):
Hello,
> * Should I mention in the doc that the code has originally been made
available under the MIT license?
I do not think that you *must* mention the original license. You can say
somewhere that this implementation is an adaptation of his code, however.
Though you can ask on sage-devel if you prefer.
> * 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.
This method is very specific to you use, and cannot be a public function
of GenericGraph with a name like that. You can turn it into a private
function if you prefer.
I have not looked at the code inside, but depending on your performance
needs, you could prefer an implementation that does not require you to
rewrite the BFS. Something like that:
{{{
sage: bfs = list(g.breadth_first_search(0,report_distance=True))
sage: layers = [set() for _ in range(bfs[-1][1]+2)]
sage: for x,d in bfs:
....: layers[d].add(x)
sage: next_level_neighbors = {v:layers[d+1].intersection(g.neighbors(v))
for d,L in enumerate(layers) for v in L}
}}}
> * 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.
Same remark here for the name. We can't have `.depth_first_search` and
`.depth_first_traversal` simultaneously, and doing different things.
> * 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.
`EmptySetError`? Isn't the certificate usually set to `None` or to the
empty dictionary when it goes wrong? Your code at #19586 raises no
exception.
> Is this OK, or should I change to returning pairs, as with other methods
returning a certificate?
You don't have to return a list of pairs, a certificate can be whatever
you like.
> Should I use some exception other than `EmptySetError`? I chose this as
it is also used in `traveling_salesman_problem`.
Oh. Well, this `EmptySetError` is a recent trend to mean that "a search
occured, and found nothing". Which 'can' make sense for a hamiltonian
cycle. Here, an `EmptySetError` would make me thing that the algorithm is
doing something enumerative like trying all labellings.
About the implementation: this code looks long, and perhaps tricky: if you
prefer you can also move it to an independent file (like it's done for
'graphs/graph_decompositions/graph_products.pyx'). The other advantage of
that is that it give you more room to write doc, if you need it.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/19985#comment:3>
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.
