#18746: Cutwidth of a graph
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.8
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | d1e49ecf1085fc3c407cef28b0457713b349ad9c
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18746 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Hello David,
I added a commit on top on top of your public branch (hoping that you will
nto
mind). It does the following things:
- Unimportant things
- remove a 'verbose' flag that you do not use
- Simplify the test for connectivity (rather unimportant too)
- use `cw` in the recursive call to `cutwidth`
- use `cut_off` in the call to `cutwidth_dyn`
- You could not guess how much time I spent over your "fake simple loop",
only
to figure out that you wanted to be able to use 'break'. It really takes
a lot
of time. I swear. When you use tricks like that, *please* say it
explicitly in
a comment.
More technically: I first added a comment above the loop to make it
clearer,
then thought that it was making things very very complicated to avoid a
copy/paste of the three lines needed before the 'return'. Besides, your
code
did not free the memory when it was interrupted with a CTRL+C.
I rewrote it with a try/except and with two nested loops. Three lines
are
copy/pasted, but I find this a much better deal in terms of readability
than a
fake nested loop. Plus it frees the memory.
- In 'exists', I renamed `count_S` to `cost_S`. Same here. You have no
idea how
many questions can be raised in the head of somebody reading the code
and not
understanding what you do with this variable called 'count_S' which,
which
turns out to not count S at all. My interpretation of this variable is
that it
stores the cost of `S`. Please check.
- When you want to multiply something by two, please use `*2` and not
`<<1`. It
makes your meaning much clearer. Gcc generates the same code anyway.
- About:
{{{
- cdef int mini = (1<<g.n)-1
+ cdef int mini = (<uint8_t> -1)
}}}
I also wondered for a moment why you defined this specific value for
`mini`. I
ended up convincing myself that you just wanted "a big constant".
- I made a slightly unrelated modification to a distant 'doctest' file.
Here is
why: this code 'injects' in any Sage file, when you run the tests, a
check
that there are as many `sig_on` as `sig_off`. You will see it if you run
the
tests on `cutwidth.pyx` after removing one of the `sig_off` (for
instance the
one that appears inside of the return, in the nested loop).
It indicates that a doctest is broken, at some line in `cutwidth.pyx`.
Of
course, this doctest is not really there so you are looking for a line
that
does not really exists. I added a comment to it, so that its meaning is
clearer when you get an error in a `sage -t`.
Could you also document the parameters of the 'exists' function, and the
expected behavior? I was surprised that a variable named 'cost' was
actually
used as "max_admissible_cost".
Thanks,
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18746#comment:10>
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.
