Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#7593 closed enhancement (fixed)

Matching 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: David Joyner
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

As the title says, this patch implements a function solving the maximum weight matching problem.

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_7593.patch (2.8 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (15)

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 Changed 10 years ago by wdj

  • Status changed from needs_review to needs_work

I could not get this to apply to sage 4.3.rc0 with glpk installed.

Do you need to rebase this?

comment:4 Changed 10 years ago by ncohen

Well, I need to rebase it each time there is a new version of Sage, and this until it finally gets reviewed... I'll rebase it just now !

Nathann

comment:5 follow-up: Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

here it is !!! This may well be the tenth version of this function which has been written 6 months ago :p

Nathann

comment:6 in reply to: ↑ 5 Changed 10 years ago by wdj

  • Status changed from needs_review to needs_info

Replying to ncohen:

here it is !!! This may well be the tenth version of this function which has been written 6 months ago :p

Nathann

Sorry for the long delay in refereeing.

It applies okay to 4.3.rc0 on ubuntu 9.04 32 bit, and passes sage -testall except for the failures that I got without the patch installed (in calculus and nf_introduction). The documentation also looks satisfactory to me. The optional test

sage -t -optional "devel/sage/sage/graphs/graph.py

gave rise to (in particular) the following failure

wdj@wdj-virtualbox:~/sagefiles/sage-4.3.rc0$ ./sage -t -optional "devel/sage/sage/graphs/graph.py"
sage -t -optional "devel/sage/sage/graphs/graph.py"         
sh: kpsewhich: not found
sh: kpsewhich: not found
sh: kpsewhich: not found
sh: kpsewhich: not found
**********************************************************************
File "/home/wdj/sagefiles/sage-4.3.rc0/devel/sage/sage/graphs/graph.py", line 3293:
    sage: g.matching(value_only=True) # optional - requires Glpk or COIN-OR/CBC
Exception raised:
    Traceback (most recent call last):
      File "/home/wdj/sagefiles/sage-4.3.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/wdj/sagefiles/sage-4.3.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/wdj/sagefiles/sage-4.3.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_59[3]>", line 1, in <module>
        g.matching(value_only=True) # optional - requires Glpk or COIN-OR/CBC###line 3293:
    sage: g.matching(value_only=True) # optional - requires Glpk or COIN-OR/CBC
      File "/home/wdj/sagefiles/sage-4.3.rc0/local/lib/python/site-packages/sage/graphs/graph.py", line 3316, in matching
        return p.solve(objective_only=True)
      File "mip.pyx", line 945, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:7177)
    ValueError: There does not seem to be any solver installed. Please visit http://www.sagemath.org/doc/tutorial/tour_LP.html for more informations.
**********************************************************************
1 items had failures:
   1 of   4 in __main__.example_59
***Test Failed*** 1 failures.
For whitespace errors, see the file /home/wdj/.sage//tmp/.doctest_graph.py
	 [74.3 s]
exit code: 1024
 
----------------------------------------------------------------------
The following tests failed:


	sage -t -optional "devel/sage/sage/graphs/graph.py"

Does this seem related to your patch? glpk is installed, to the error message ("solver not installed") seems wrong, or at least is unexpected by me.

comment:7 Changed 10 years ago by ncohen

This is indeed related to my patch, but I have a question : when you say that glpk is installed, do you mean that you installed it in the same branche where you applied the patch ? If you installed it when you were using a different branch, then switched to another one to test this patch, it will not be detected.. You need to install it in every branch where you need to use it :-)

This comes from the fact that during the installation of the procedure, the file mipGlpk.pyx is compiled and only accessible by the "current" branch. You the probably need to switch to the branch which uses matching, then to sage -f GLPK ( as it needs to be forced ) :-)

Hope this will solve it ! :-)

Nathann

comment:8 Changed 10 years ago by wdj

  • Status changed from needs_info to needs_review

Agreed. Thanks. Very useful patch.

comment:9 Changed 10 years ago by wdj

  • Status changed from needs_review to positive_review

Applies and tests fine on sage 4.3.rc0 and ubuntu 9.04 32 bit.

comment:10 Changed 10 years ago by ncohen

Yeppeeeeeeeeeee !! :-)

Thank you veeeeeeeeeeeeeeeeeeeeeeeeeeryyyyyyyyyyyyyyy much :-)

Nathann

comment:11 Changed 10 years ago by mhansen

The patch needs a little touching up.

It should be .. math:: instead of .. MATH::. Also, it would be good to follow PEP 8 rules http://www.python.org/dev/peps/pep-0008/ regarding spacing -- http://www.python.org/dev/peps/pep-0008/ .

Changed 10 years ago by ncohen

comment:12 Changed 10 years ago by ncohen

I just updated the path to replace MATH by math :-)

comment:13 Changed 10 years ago by mhansen

  • Authors set to Nathann Cohen
  • Merged in set to sage-4.3.rc1
  • Resolution set to fixed
  • Reviewers set to David Joyner
  • Status changed from positive_review to closed

comment:14 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.