#8922: induced subgraph search
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: critical | Milestone: sage-4.4.3
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Changes (by mvngu):
* status: needs_review => needs_work
Comment:
I applied patches in the order suggested in the ticket description.
Running doctests on the whole graph theory module resulted in these
failures. This failure results from ncohen's updated patch, which does not
update the doctests:
{{{
sage -t -long "devel/sage-main/sage/graphs/generic_graph_pyx.pyx"
**********************************************************************
File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-
main/sage/graphs/generic_graph_pyx.pyx", line 491:
sage: from sage.graphs.induced_subgraphs.induced_subgraphs import
find_induced
Exception raised:
Traceback (most recent call last):
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py",
line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_10[2]>", line 1, in <module>
from sage.graphs.induced_subgraphs.induced_subgraphs import
find_induced###line 491:
sage: from sage.graphs.induced_subgraphs.induced_subgraphs import
find_induced
ImportError: No module named induced_subgraphs.induced_subgraphs
**********************************************************************
File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-
main/sage/graphs/generic_graph_pyx.pyx", line 492:
sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(5))
Exception raised:
Traceback (most recent call last):
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py",
line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_10[3]>", line 1, in <module>
find_induced(graphs.PetersenGraph(),
graphs.PathGraph(Integer(5)))###line 492:
sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(5))
NameError: name 'find_induced' is not defined
**********************************************************************
File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-
main/sage/graphs/generic_graph_pyx.pyx", line 497:
sage: find_induced(graphs.PetersenGraph(), graphs.ClawGraph())
Exception raised:
Traceback (most recent call last):
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py",
line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_10[4]>", line 1, in <module>
find_induced(graphs.PetersenGraph(), graphs.ClawGraph())###line
497:
sage: find_induced(graphs.PetersenGraph(), graphs.ClawGraph())
NameError: name 'find_induced' is not defined
**********************************************************************
File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-
main/sage/graphs/generic_graph_pyx.pyx", line 502:
sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(6))
Exception raised:
Traceback (most recent call last):
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py",
line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_10[5]>", line 1, in <module>
find_induced(graphs.PetersenGraph(),
graphs.PathGraph(Integer(6)))###line 502:
sage: find_induced(graphs.PetersenGraph(), graphs.PathGraph(6))
NameError: name 'find_induced' is not defined
}}}
This is a known failure:
{{{
sage -t -long "devel/sage-main/sage/graphs/generic_graph.py"
**********************************************************************
File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-
main/sage/graphs/generic_graph.py", line 10754:
sage: print G.graphviz_string(labels="latex",edge_labels=True)
Expected:
digraph {
node [shape="plaintext"];
"2/3" [label=" ", texlbl="$\frac{2}{3}$"];
"1/3" [label=" ", texlbl="$\frac{1}{3}$"];
"1/2" [label=" ", texlbl="$\frac{1}{2}$"];
"1" [label=" ", texlbl="$1$"];
"1/4" [label=" ", texlbl="$\frac{1}{4}$"];
"4/5" [label=" ", texlbl="$\frac{4}{5}$"];
"-4" [label=" ", texlbl="$-4$"];
"2" [label=" ", texlbl="$2$"];
"-2" [label=" ", texlbl="$-2$"];
"-1/2" [label=" ", texlbl="$-\frac{1}{2}$"];
"-1" [label=" ", texlbl="$-1$"];
<BLANKLINE>
"1/2" -> "-2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"];
"1/2" -> "2/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x +
1}$"];
"1" -> "-1" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"];
"1" -> "1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"];
"1/4" -> "-4" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"];
"1/4" -> "4/5" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x +
1}$"];
"2" -> "-1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{-1}{x}$"];
"2" -> "1/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"];
}
Got:
digraph {
node [shape="plaintext"];
"2/3" [label=" ", texlbl="$\frac{2}{3}$"];
"1/3" [label=" ", texlbl="$\frac{1}{3}$"];
"1/2" [label=" ", texlbl="$\frac{1}{2}$"];
"1" [label=" ", texlbl="$1$"];
"1/4" [label=" ", texlbl="$\frac{1}{4}$"];
"4/5" [label=" ", texlbl="$\frac{4}{5}$"];
"-4" [label=" ", texlbl="$-4$"];
"2" [label=" ", texlbl="$2$"];
"-2" [label=" ", texlbl="$-2$"];
"-1/2" [label=" ", texlbl="$-\frac{1}{2}$"];
"-1" [label=" ", texlbl="$-1$"];
<BLANKLINE>
"1/2" -> "-2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"];
"1/2" -> "2/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x +
1}$"];
"1" -> "-1" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"];
"1" -> "1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"];
"1/4" -> "-4" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"];
"1/4" -> "4/5" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x +
1}$"];
"2" -> "-1/2" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"];
"2" -> "1/3" [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"];
}
}}}
This one should be optional, I think, and results from #8166:
{{{
File "/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/devel/sage-
main/sage/graphs/generic_graph.py", line 4213:
sage: g.matching(algorithm="LP", value_only=True)
Exception raised:
Traceback (most recent call last):
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/sagedoctest.py",
line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/bin/ncadoctest.py",
line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_70[5]>", line 1, in <module>
g.matching(algorithm="LP", value_only=True)###line 4213:
sage: g.matching(algorithm="LP", value_only=True)
File
"/dev/shm/mvngu/sandbox/sage-4.4.3.alpha0.sandbox0/local/lib/python/site-
packages/sage/graphs/generic_graph.py", line 4264, in matching
return p.solve(objective_only=True, solver=solver, log=verbose)
File "mip.pyx", line 1051, in
sage.numerical.mip.MixedIntegerLinearProgram.solve
(sage/numerical/mip.c:7884)
ValueError: There does not seem to be any (Mixed) Integer Linear
Program solver installed. Please visit
http://www.sagemath.org/doc/constructions/linear_programming.html to learn
more about the solvers available.
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8922#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
