Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#7592 closed enhancement (fixed)

Flow method using LP

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

As the title says, this patch implements the flow function for Graphs ( weighted or not, directed or not )

You could be in need of #7270 and GLPK from http://sagemath.org/packages/optional/glpk-4.38.p4.spkg depending on the version of Sage you are using !!!

Attachments (1)

trac_7592.patch (7.3 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 10 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 10 years ago by ncohen

  • Description modified (diff)

comment:3 follow-up: Changed 10 years ago by wdj

This does not apply to 4.3.a1 on an imac running 10.6.1:

jeeves:sage-4.3.alpha1 wdj$ ./sage
----------------------------------------------------------------------
| Sage Version 4.3.alpha1, Release Date: 2009-12-03                  |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
**********************************************************************
*                                                                    *
* Warning: this is a prerelease version, and it may be unstable.     *
*                                                                    *
**********************************************************************
WARNING: There is one major unsolved bug in some versions of
Sage on OS X 10.6 that causes an 'Abort trap' crash when
doing certain symbolic computations.
See http://trac.sagemath.org/sage_trac/ticket/7095/.
Loading Sage library. Current Mercurial branch is: 7592-flow
sage: hg_sage.apply("/Users/wdj/sagefiles/trac_7592.patch")
cd "/Users/wdj/sagefiles/sage-4.3.alpha1/devel/sage" && hg status
/Users/wdj/sagefiles/sage-4.3.alpha1/local/lib/python2.6/site-packages/sage/misc/hg.py:240: DeprecationWarning: os.popen3 is deprecated.  Use the subprocess module.
  x = os.popen3(s)
cd "/Users/wdj/sagefiles/sage-4.3.alpha1/devel/sage" && hg status
cd "/Users/wdj/sagefiles/sage-4.3.alpha1/devel/sage" && hg import   "/Users/wdj/sagefiles/trac_7592.patch"
applying /Users/wdj/sagefiles/trac_7592.patch
patching file sage/graphs/graph.py
Hunk #2 FAILED at 3019
1 out of 2 hunks FAILED -- saving rejects to file sage/graphs/graph.py.rej
abort: patch failed to apply
sage: 

comment:4 in reply to: ↑ 3 Changed 10 years ago by wdj

Replying to wdj:

This does not apply to 4.3.a1 on an imac running 10.6.1:

...

I should add though that this version of sage has the latest networkx package installed. Would that screw things up?

comment:5 Changed 10 years ago by ncohen

It could have, but in this case it was mainly my fault. I have no idea why, but the patch did not even apply on my version, perhaps they were not based on alpha... Here is a new version based on alpha, with my excuses :-)

comment:6 Changed 10 years ago by ncohen

There was a small mistake in the

if vertex_bound:            
        CORRECTED LINE

Some variable had no assigned value.... And the patch I just updated takes this into account :-)

comment:7 Changed 10 years ago by rlm

  • Status changed from needs_review to needs_work

You need more examples in the doctest section. Some of the options return something different than what the docs say, such as:

sage: g.flow(1,2, value_only=False)
[3.0, Pappus Graph: Graph on 18 vertices]

Changed 10 years ago by ncohen

comment:8 Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

I corrected the documentation as I finally thought returning a graph would be much more useful :-)

I also added a more interesting example of what one can do with flows :-)

Nathann

comment:9 Changed 10 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:10 Changed 10 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:11 Changed 10 years ago by mhansen

  • Milestone changed from sage-4.3.1 to sage-4.3
Note: See TracTickets for help on using tickets.