#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 | b536ed4dbb5e44f705ddd12c429b9473ec24cc58
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18746 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
I'm so sorry that you spend so much time understanding this code. In fact
the `exists` method is almost a copy/paste of the method you did for
vertex separation/pathwidth, and I have omitted to extend the
documentation. Sorry.
> 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.
Are you sure that the `finally` part is executed even after the `return`
instruction in the `try` ? Shouldn't I add a `sage_free` before that
return ?
> - 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.
I have renamed `cost` -> `k` to be consistent with the `cutwidth_dyn`
method. It should be easier to follow.
> - 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.
OK. I wasn't sure of that.
> - 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".
Right. For vertex separation it was sufficient to initialize it with
`g.n`, but here the maximum value can reach `n^2/2` (luckily, since `n\leq
31`, the maximum possible value, `15*16=240`, can be stored in an
`uint8_t`.
> - 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`.
ok. This is admittedly easier that to create a one line ticket.
> 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".
I tried to improve both the module documentation and the computation
steps.
> Thanks,
Thanks to you.
David.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=b536ed4dbb5e44f705ddd12c429b9473ec24cc58
b536ed4]||{{{trac #18746: documentation improvements}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/18746#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.
