Matching using LP

[nathanncohen]

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 !!!

Component: graph theory

Author: Nathann Cohen

Reviewer: David Joyner

Merged: sage-4.3.rc1

Issue created by migration from https://trac.sagemath.org/ticket/7593

[nathanncohen]

Description changed:

--- 
+++ 
@@ -1 +1,4 @@
 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 !!!

[wdjoyner]

comment:3

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

Do you need to rebase this?

[nathanncohen]

comment:4

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

[nathanncohen]

comment:5

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

Nathann

[wdjoyner]

comment:6

Replying to @nathanncohen:

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.