#17582: Bandwidth of a graph
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 19da4149e16a3a32bd68e354f01e0a50e1af3441
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17582 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Yo !
> - With the instruction `G = G.relabel(inplace=False) # int-labelled` you
loose the original labels of the vertices.
Fixed.
> - in the `if (d is NULL or distances is NULL or ...` you should add a
`return blah blah`.
Fixed.
> Are you aware of patch #13565
Yes I saw it while coding. Actually I wanted to add a "bandwidth" function
to the matrix code, just to make my "assert" cleaner at the end of this
branch, but I did not know in which of matrix0.pyx, matrix1.pyx or
matrix2.pyx it should be stored, and because it was a one-line function I
gave that up. By the way, the code at #13565 is not very good as it will
copy all cells of the matrix (calls to `.diagonal()`).
> Now I'm trying to figure out the worse case time complexity of your
algorithm, and of course if it is exact ;)
Well, at the bottom of it there is only this usual trick of enumerating
permutations in a non-recursive way. That parts uses current, i, and
left_to_continue. The rest is bandwidth-specific, and is there to cut
branches.
There may be some doc to add, tell me if it is lacking somewhere. This
kind of code is easier to write than to review.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17582#comment:7>
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.
