Opened 10 years ago
Closed 9 years ago
#9546 closed enhancement (fixed)
bounded outdegree orientation
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | graph theory | Keywords: | |
Cc: | jthurber | Merged in: | sage-4.6.2.alpha1 |
Authors: | Nathann Cohen, Geoffrey Ehrman | Reviewers: | Robert Miller |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Given a Graph and a value associating an integer b(v) to each vertex v, this method computes an orientation of G such that each vertex has out_degree at most v, if it exists.
The method is to use a max flow, which is explained in the patch in several lines.
Nathann
Attachments (3)
Change History (10)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Milestone changed from sage-4.6.1 to sage-4.6.2
- Reviewers set to Robert Miller
- Status changed from needs_review to needs_work
comment:3 Changed 9 years ago by
- Status changed from needs_work to needs_review
Right O_o
The error comes from the ford_fulkerson algorithm. I replaced "floor(x)" by "x 1".
I know I wrote this code myself, but when I looked at it I could only think : why on earth is our implementation of flows in Python and not Cython ? O_o
Updated ! Sorry for the trouble !
Nathann
Changed 9 years ago by
comment:4 Changed 9 years ago by
Using floor division here might be nice, but I'm concerned about the coercion model:
sage: 1215.151//1 --------------------------------------------------------------------------- TypeError Traceback (most recent call last) /home/gbe/sage/dev/devel/sage-main/sage/<ipython console> in <module>() /usr/local/sage/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__floordiv__ (sage/rings/integer.c:11983)() /usr/local/sage/local/lib/python2.6/site-packages/sage/structure/element.so in sage.structure.element.bin_op (sage/structure/element.c:17928)() /usr/local/sage/local/lib/python2.6/site-packages/sage/structure/element.so in sage.structure.element.bin_op (sage/structure/element.c:17841)() /usr/local/sage/local/lib/python2.6/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6213)() /usr/local/sage/local/lib/python2.6/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6152)() TypeError: unsupported operand type(s) for //: 'sage.rings.real_mpfr.RealLiteral' and 'sage.rings.real_mpfr.RealNumber'
Also, floor division doesn't seem to buy you any speedup:
sage: tests = [float(random()*10**randint(0,10)) for i in range(10)] sage: for i in tests: ....: timeit('floor(test)') 625 loops, best of 3: 5.14 µs per loop 625 loops, best of 3: 5.12 µs per loop 625 loops, best of 3: 5.21 µs per loop 625 loops, best of 3: 5.12 µs per loop 625 loops, best of 3: 5.12 µs per loop 625 loops, best of 3: 5.1 µs per loop 625 loops, best of 3: 5.07 µs per loop 625 loops, best of 3: 5.2 µs per loop 625 loops, best of 3: 5.11 µs per loop 625 loops, best of 3: 5.13 µs per loop sage: for i in tests: ....: timeit('test // 1') 625 loops, best of 3: 9.33 µs per loop 625 loops, best of 3: 9.47 µs per loop 625 loops, best of 3: 9.4 µs per loop 625 loops, best of 3: 9.44 µs per loop 625 loops, best of 3: 9.4 µs per loop 625 loops, best of 3: 9.4 µs per loop 625 loops, best of 3: 9.35 µs per loop 625 loops, best of 3: 9.31 µs per loop 625 loops, best of 3: 9.3 µs per loop 625 loops, best of 3: 9.4 µs per loop
All in all I think the better solution is to just bring floor(x) into scope from functions/other.py, as I've done in the attached patch.
Changed 9 years ago by
comment:5 Changed 9 years ago by
- Cc jthurber added
Changed 9 years ago by
comment:6 Changed 9 years ago by
- Status changed from needs_review to positive_review
apply all three patches
comment:7 Changed 9 years ago by
- Merged in set to sage-4.6.2.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
These all seem to be: