#8922: induced subgraph search
-------------------------------+--------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: critical | Milestone: sage-4.4.4
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: Minh Van Nguyen | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Comment(by ncohen):
Hello !!
First, I want to thank you for the amount of time your must have spent on
this :-)
> * Move the method `adjacency_sequence()` to the class `CGraph`, as I
think that method is useful for both dense and sparse graphs.
It can be, though systematically testing adjacencies (and most importantly
-- non-adjacencies) in sparse graph can be a problem... Perhaps we will
have to split this function in two copies, one for each class, one day or
another. I have been talking with Alexandre Blondin Masse who could need
such a feature for Sparse graphs :-)
> * In describing the algorithm used in `subgraph_search()` of the module
`generic_graph_pyx.pyx`, you have the formula:
> {{{
> `\binom k!{|V(G)|}{k}`
> }}}
> That won't typeset in LaTeX as you expected. Do you mean this?
> {{{
> `k! \binom{|V(G)|}{k}`
> }}}
Indeed
> I have used the latter formula in my reviewer patch. Please correct me
if I'm wrong.
You almost never are :-)
> * Unit tests for the `cdef` functions `vectors_equal()` and
`vectors_inferior()`, and the method `adjacency_sequence()`. These
functions/methods are defined using `cdef` and the doctest coverage script
don't pick them up in its analysis. However, I still think it's important
to provide unit tests for such functions/methods.
Well, if there is anything wrong in these functions your tests will show
it, though given their length I wouldn't have thought necessary to add
such tests.... Are you doubting Cython itself ? :-)
> * Amalgamate the methods `induced_subgraph_search()` and
`subgraph_search()`. Their definitions are almost identical, except for
the keyword `induced`. The combined method is defined to take the boolean
keyword `induced` and pass it on to the relevant method.
I was thinking of someone working on induced subgraphs, and not seeing any
occurence of this word among the functions.... But he will get interested
in subgraph search sooner or later ;-)
> Another pair of eyes is needed to look over my reviewer patch.
I already spent some time over it, and agreed with what I saw....
Considering its length, I may do this once or twice again before setting
it to "positive review". and... Thank you again :-)
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8922#comment:13>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
