#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 | fdfe120bc438b041a7ff480a288f29d6c73b17e5
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17647b |
Dependencies: |
#17665 |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
Replying to [comment:35 ncohen]:
> Hello,
>
> > > - 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.
> {{{
> source_pos = positions[i]
> j = prefix[target_pos]
> prefix[target_pos],prefix[source_pos] = prefix[source_pos],
prefix[target_pos]
> positions[i],positions[j] = positions[j],positions[i]
> }}}
>
> It could be made simpler if the code of `_my_invert_positions` was
taking two positions (or two vertices) as argument instead of 'one of each
type'.
I have change the method and updated calls to it.
> > But if it is a Python list, method `vertex_separation_BAB_C` has to
return both the value and that list.
>
> {{{
> e = [1,2,3]
> def invert_two_entries(l):
> l[0],l[1] = l[1],l[0]
> invert_two_entries(e)
> print e # prints [2, 1, 3]
> }}}
>
> > How would that be more efficient than passing a pointer and updating
the content of the array when needed ?
>
> It is not about efficiency, it is about not allocating/deallocating
something if it can be avoided. This table is updated very rarely, so it
does not have to be a C array.
Apparently your care a lot about reducing mallocs.
I changed it.
Replying to [comment:36 ncohen]:
> Helloooooo again,
>
> - What is the purpose of `lower_bound`? The documentation says that the
code is
> trying to find an ordering whose cost is *lower* than `lower_bound`?
On what
> exactly is it a lower bound?
>
> Do you mean that the code will "return any ordering whose cost is
lower than
> `lower_bound`, even if it has no proof that it is optimal?
Exactly.
With parameter `upper_bound`, you ask for a solution with width less than
`upper_bound` if such a solution exists.
With parameter `lower_bound`, you say that you are satisfied with any
solution with width less than this bound. This is useful in particular
when you split the input digraph into strongly connected components and
solve the problem on each of them. If one component has width `k`, you
don't care if another component has width `k-1` since you know that the
vertex separation of the entire digraph is at least `k`.
This will be useful when we will start adding pre-processing.
> - Do you think that you actually need `loc_b_neighborhood`? It feels
like all
> you need is what you store in `bits_tmp`, i.e. the union of the prefix
and the
> neighborhood. And you could drop one of your two tmp bitets.
I succeed to remove it. I have changed the name of some variables and
updated the size of `bm_pool`accordingly.
> - Are those two lines needed?
>
> {{{
> delta_i = max(current_cost, delta_i)
> if delta_i < upper_bound:
> }}}
>
> It seems that you can already suppose that `current_cost<upper_bound`,
and you
> checked several lines above that `delta_i < upper_bound`.
If we reduce the upper bound during the recursive call of the kth element
of the list, we want to prune (cut) branches that are no longer useful.
So yes, these lines are needed.
> - I do not agree with this comment
>
> {{{
> if upper_bound <= lower_bound:
> # Either we have optimal solution, or we are satisfied with
> # current solution.
> }}}
>
> it seems that this code only deals with the case when 'we are
satisfied with
> the current solution'.
I changed the sentence to `We are satisfied with current solution`
> - Is there any reason why you did not expose your function in the main
> `vertex_separation` function? If you do, is there any reason why it
should not
> be the default one? (if it is faster?..). Finally, note that if you do
make it
> the default some doctests of your functions will have to be updated,
as you
> would be comparing the BAB function with `vertex_separation` (which
would also
> call the BAB).
Yep, I have many reasons for not exposing the BAB in the main
`vertex_separation` function yet.
1. this patch is already quite long and technical. Since you often
complain about patch bombs, I did my best to decompose the work
2. I plan to add pre-processing rules. The first one is to decompose the
input digraph into strongly connected components, but I have others, more
complex. I will work on this part only when the BAB will be finalized
(including memoization of prefixes). I believe its better to wok this way.
> With those comments and those from my previous message, I would say that
my
> review is finished. We only have to settle those last remarks.
>
> Thanks for your work!
>
> Nathann
I hope I have answered all your comments ;)
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:37>
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.
