#15514: adding option for computing a total dominating set
-------------------------------------+-------------------------------------
Reporter: azi | Owner:
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-6.4
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/azi/adding_option_for_computing_a_total_dominating_set|
0659b10bdb7e08638936cd419963ce40aab8317b
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by azi):
Replying to [comment:23 ncohen]:
> Excellent ! Well, it all looks good except your optimization for the
objective function.
>
> 1) Really, you are solving a NP-Hard problem and you are saving on a
list ? `:-P`
I think its still fair to do such optimisations. They may come handy for
say graphs of order ~100 and high degree. But if its not an actually
improvement then ofc you're right and and my bad for not checking it!
>
> 2) Actually, this code is slower than the previous one:
>
> {{{
> sage: p = MixedIntegerLinearProgram()
> sage: b = p.new_variable(binary=True)
> sage: %timeit sum(b[x] for x in range(1000))
> 10 loops, best of 3: 77.1 ms per loop
> sage: %timeit p.sum(b[x] for x in range(1000))
> 1000 loops, best of 3: 1.09 ms per loop
> }}}
>
> This is because a "sum of LP variables" is a "linearfunction" object,
and that adding to it another LP variable creates a second linearfunction
object, which is mostly a copy of the previous one. Thus,
`b[0]+b[1]+....+b[n]` creates `n` linearfunction objects and has a
quadratic complexity.
>
> That's why `p.sum` was created: as p.sum is dedicated to
linearfunctions, it handles the, in the best way, without creating useless
intermediate objects.
Oooh, I was really wondering why we're using p.sum...
>
> Nathann
>
> P.S. : If you fix this in a third commit, you will haev commits which
undo what the previous commits do. It is actually possibly, using git, to
merge them all into one (called "squash" in git slang).
>
> Two ways:
>
> 1) Look at "git rebase -i"
>
> 2) If you run "git reset HEAD~1", the last commit is "destroyed" and the
changes it contains become "unstaged" chages. This, together with "git
commit --amend" is another way to merge the commits.
Thanks for that remark. Let's see how the things I now pushed go..
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=0659b10bdb7e08638936cd419963ce40aab8317b
0659b10]||{{{trac: #15514: Added option for computing the total dominating
set}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/15514#comment:25>
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.
