#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 |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
Replying to [comment:31 ncohen]:
> 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`.
done
> - 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?
I don't see how.
This code is different from the `bandwidth` one because I have the greedy
steps.
Using the `positions` array, I know exactly where are the vertices in the
array `current_prefix` (now `prefix`). This way I don't have to undo the
permutations when I track back or after a recursive call.
So yes it is possible to get rid of this array, but the price is to undo
all permutations which is particularly painful with the greedy steps.
I definitively prefer my solution.
> - in `_my_invert_positions`: you cannot in C, but in Cython you can do
> `a,b=b,a`.
I don't see how to use it here.
> - ``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.
But if it is a Python list, method `vertex_separation_BAB_C` has to return
both the value and that list. How would that be more efficient than
passing a pointer and updating the content of the array when needed ?
> - 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?)
I added some documentation. Let me know if it is enough.
> - Do you really need both `current_prefix` and `current_other`? They
seem to be
> the complement of each other at all times.
Right, `current_other` is not used at all. Removed.
> - 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?
I have remove `current_` from many variables.
> - It seems that `current_cost` is the cost of `best_seq`. What about
> `best_cost`?
`current_cost`is the cost of the current prefix. Therefore, I think the
name is appropriate.
> - `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]])
> }}}
Changed
> - Instead of `somemore`, use a `break` if `select_it is False`.
I had to find another way since I had a for loop inside a while loop.
Furthermore, the condition `if select_it is False then break` is incorrect
in this case.
Now I have removed the for loop and I only have the while without break.
Thanks,
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:32>
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.
