Opened 9 years ago

Closed 8 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)

trac_9546.patch (6.2 KB) - added by ncohen 9 years ago.
9546_scope_fix.patch (741 bytes) - added by gbe 9 years ago.
trac_9546-ref-edit.patch (755 bytes) - added by rlm 9 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • 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
----------------------------------------------------------------------

The following tests failed:

        sage -t -long devel/sage-main/sage/graphs/graph.py # 7 doctests failed
----------------------------------------------------------------------

These all seem to be:

NameError: global name 'floor' is not defined

comment:3 Changed 9 years ago by ncohen

  • 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 ncohen

comment:4 Changed 9 years ago by gbe

  • Authors changed from Nathann Cohen to Nathann Cohen, Geoffrey Ehrman

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 gbe

comment:5 Changed 9 years ago by jthurber

  • Cc jthurber added

Changed 9 years ago by rlm

comment:6 Changed 9 years ago by rlm

  • Status changed from needs_review to positive_review

apply all three patches

comment:7 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.