#17647: Branch and Bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
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 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'.
> 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.
> Now I have removed the for loop and I only have the while without break.
Great! I'll resume the review.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:35>
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.
