#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 | 0504e8f1946309d9784c4837275c919b047f9829
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17647 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
> Nice. I have just fixed a small typo.
Thanks
> > I am not done with the review, but I worry a bit about the fact that
you allocate memory in a recursive function. They can cost a lot, these
things. Do you see a clean way to avoid that ?
> I already though about it and I don't have a "clean" method to propose.
I could for instance allocate one for all 5 arrays of n bitsets each and
access to the bitsets of level *level* since the BAB has depth at most n.
This way we avoid multiple allocations.
> If you think it is OK, I can implement it.
Using bitsets that would mean dozens of allocations lines again. What is
it that you use in those fast digraphs of yours that are not in the
'binary matrix' type ? Possibly the best is to implement it there and use
the binary matrices?
> What's the magic commande to profile this code? %prun is not working
here.
Run a long command, then type 'perf top' in a console. You'll love it.
> The speed of the {{{bitset_len}}} method depends on the system. Since
patch #13352, we use the mpn methods for popcount which is expected to use
{{{__builtin_popcount}}}. I don't know how fast it is on my laptop. I'll
check as soon as you give me the magic command ;)
I will probably write a "profiling tutorial" soon. It would be cool if you
were willing to review it. That will be helpful, along with the "interface
C code with Sage" tutorial.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#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 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.
