#17647: Branch and Bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_work
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | fdf3c001ccf9deb6fba3653532f762f4c7c39788
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17647b |
Dependencies: |
#17665 |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hello!
A first pass:
- Some modifications that you did to the header of `fast_digraph.pyx`
should be
undone now that you use `binary_matrix`.
- I do not know whether `positions` is actually needed in this code, but I
still
do not understand it totally. It seems that you enumerate all
permutations,
cutting branches from time to time: the code is in its principle very
similar
from the bandwidth code that was recently included. That code does not
need
such an array: do you think that it could also be removed from here?
- in `_my_invert_positions`: you cannot in C, but in Cython you can do
`a,b=b,a`.
- ``best_seq`` has no reason to be a C array. If you turn it into a Python
list,
you will remove several lines of alloc/dealloc code.
- Not worth changing it now, but try to use {{{:class:`class_name`}}}
instead of
{{{``class_name``}}} in the doc.
- Can you document the parameters taken by `vertex_separation_BAB_C` ?
`bm_pool`
is not that self-explaining (what are its dimensions? its role?)
- Do you really need both `current_prefix` and `current_other`? They seem
to be
the complement of each other at all times.
- What about removing "current" from
`loc_b_current_prefix,loc_b_current_neighborhood,loc_b_current_other,b_current_prefix,b_current_neighborhood,b_current_other,current_prefix`?
It seems to me that `b_prefix, b_prefix_neighborhood`, `b_nonprefix`
would be
equally meaningful and 'lighter' to read?
- It seems that `current_cost` is the cost of `best_seq`. What about
`best_cost`?
- `order = [int_to_vertex[best_seq[i]] for i in range(n)]` is better than
{{{
cdef list order = list()
for 0 <= i < n:
order.append(int_to_vertex[best_seq[i]])
}}}
- Instead of `somemore`, use a `break` if `select_it is False`.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:31>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
