#6085: [with patch, not ready] Finish full implementation of c_graphs
--------------------------+-------------------------------------------------
Reporter: rlm | Owner: rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.0.1
Component: graph theory | Keywords:
--------------------------+-------------------------------------------------
Comment(by rlm):
After patch 7, the only test failures in `graphs` I can find are related
to the planarity code Emily Kirkman and John Bober wrote. I can imagine
that the problem is that CGraphs used to require to have vertices in a
consecutive range, and now, e.g. you can have the vertex set = {1, 7, 9}:
{{{
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/graph.py",
line 2246:
sage: g.set_planar_positions(test=True)
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_45[3]>", line 1, in <module>
g.set_planar_positions(test=True)###line 2246:
sage: g.set_planar_positions(test=True)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph.py", line 2324, in set_planar_positions
raise Exception('BUG: Triangulation returned face: %s'%face)
Exception: BUG: Triangulation returned face: [(0, 1), (1, 2), (2, 3),
(3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 1), (1, 0)]
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/graph.py",
line 2249:
sage: g.set_planar_positions(test=True)
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_45[5]>", line 1, in <module>
g.set_planar_positions(test=True)###line 2249:
sage: g.set_planar_positions(test=True)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph.py", line 2324, in set_planar_positions
raise Exception('BUG: Triangulation returned face: %s'%face)
Exception: BUG: Triangulation returned face: [(11, 103), (103, 104),
(104, 95), (95, 11)]
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/graph.py",
line 2252:
sage: g.set_planar_positions(test=True)
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_45[7]>", line 1, in <module>
g.set_planar_positions(test=True)###line 2252:
sage: g.set_planar_positions(test=True)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph.py", line 2332, in set_planar_positions
tree_nodes = _realizer( G, label)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 397, in _realizer
_compute_coordinates(realizer, (tree_nodes, (v1, v2, v3)))
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 467, in _compute_coordinates
p = tree_nodes[v][(i + 1) % 3]
KeyError: None
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/graph.py",
line 2366:
sage: D.set_planar_positions()
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_46[3]>", line 1, in <module>
D.set_planar_positions()###line 2366:
sage: D.set_planar_positions()
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph.py", line 2332, in set_planar_positions
tree_nodes = _realizer( G, label)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 397, in _realizer
_compute_coordinates(realizer, (tree_nodes, (v1, v2, v3)))
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 467, in _compute_coordinates
p = tree_nodes[v][(i + 1) % 3]
KeyError: None
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/graph.py",
line 2367:
sage: D.is_drawn_free_of_edge_crossings()
Expected:
True
Got:
False
**********************************************************************
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/schnyder.py",
line 153:
sage: _realizer(g, tn)
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_2[8]>", line 1, in <module>
_realizer(g, tn)###line 153:
sage: _realizer(g, tn)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 397, in _realizer
_compute_coordinates(realizer, (tree_nodes, (v1, v2, v3)))
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 467, in _compute_coordinates
p = tree_nodes[v][(i + 1) % 3]
KeyError: None
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/schnyder.py",
line 350:
sage: _realizer(g, tn)
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_3[8]>", line 1, in <module>
_realizer(g, tn)###line 350:
sage: _realizer(g, tn)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 397, in _realizer
_compute_coordinates(realizer, (tree_nodes, (v1, v2, v3)))
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 467, in _compute_coordinates
p = tree_nodes[v][(i + 1) % 3]
KeyError: None
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/schnyder.py",
line 430:
sage: r = _realizer(g, tn)
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_4[8]>", line 1, in <module>
r = _realizer(g, tn)###line 430:
sage: r = _realizer(g, tn)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 397, in _realizer
_compute_coordinates(realizer, (tree_nodes, (v1, v2, v3)))
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 467, in _compute_coordinates
p = tree_nodes[v][(i + 1) % 3]
KeyError: None
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/schnyder.py",
line 431:
sage: _compute_coordinates(g,r)
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_4[9]>", line 1, in <module>
_compute_coordinates(g,r)###line 431:
sage: _compute_coordinates(g,r)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/schnyder.py", line 437, in _compute_coordinates
tree_nodes, (v1, v2, v3) = x
ValueError: too many values to unpack
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-main/sage/graphs/schnyder.py",
line 432:
sage: g.get_pos()
Expected:
{0: [5, 1], 1: [0, 5], 2: [1, 0], 3: [1, 4], 4: [2, 1], 5: [2, 3], 6:
[3, 2]}
Got nothing
**********************************************************************
}}}
This one probably results from ordering being different:
{{{
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/posets/posets.py", line 924:
sage: [(v,P.rank(v)) for v in P]
Expected:
[(1234, 0),
(2134, 1),
...
(4231, 5),
(4321, 6)]
Got:
[(1234, 0), (1243, 1), (1324, 1), (2134, 1), (2314, 2), (1423, 2),
(3124, 2), (3214, 3), (1342, 2), (1432, 3), (2143, 2), (2341, 3), (4123,
3), (3142, 3), (4132, 4), (3241, 4), (2413, 3), (3412, 4), (2431, 4),
(3421, 5), (4213, 4), (4231, 5), (4312, 5), (4321, 6)]
**********************************************************************
}}}
Not sure about these ones:
{{{
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/species/species.py", line 667:
sage: list(sorted(labels.items()))
Expected:
[(Combinatorial species, 0),
(Product of (Combinatorial species) and (Combinatorial species), 2),
(Singleton species, 1),
(Sum of (Singleton species) and (Product of (Combinatorial species)
and (Combinatorial species)), 3)]
Got:
[(('o', Combinatorial species), 0), (('o', Product of (Combinatorial
species) and (Combinatorial species)), 2), (('o', Singleton species), 1),
(('o', Sum of (Singleton species) and (Product of (Combinatorial species)
and (Combinatorial species))), 3), (('x', 0), 4), (('x', 1), 5),
(Combinatorial species, Combinatorial species), (Product of (Combinatorial
species) and (Combinatorial species), Product of (Combinatorial species)
and (Combinatorial species)), (Singleton species, Singleton species), (Sum
of (Singleton species) and (Product of (Combinatorial species) and
(Combinatorial species)), Sum of (Singleton species) and (Product of
(Combinatorial species) and (Combinatorial species)))]
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/species/species.py", line 672:
sage: g.edges()
Expected:
[(0, 3, None), (2, 0, None), (2, 0, None), (3, 1, None), (3, 2, None)]
Got:
[(Combinatorial species, Sum of (Singleton species) and (Product of
(Combinatorial species) and (Combinatorial species)), None), (Product of
(Combinatorial species) and (Combinatorial species), Combinatorial
species, None), (Product of (Combinatorial species) and (Combinatorial
species), Combinatorial species, None), (Sum of (Singleton species) and
(Product of (Combinatorial species) and (Combinatorial species)), Product
of (Combinatorial species) and (Combinatorial species), None), (Sum of
(Singleton species) and (Product of (Combinatorial species) and
(Combinatorial species)), Singleton species, None)]
**********************************************************************
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1337:
sage: s.edges()
Expected:
[(0, 3, word: ca), (0, 5, word: a), (0, 7, word: o), (3, 1, word:
cao), (3, 4, word: o), (5, 2, word: cao), (5, 6, word: o)]
Got:
[(0, 1, word: cacao), (0, 2, word: acao), (0, 3, word: ca), (0, 5,
word: a), (0, 7, word: o), (3, 1, word: cao), (3, 4, word: o), (5, 2,
word: cao), (5, 6, word: o)]
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1345:
sage: s.edges()
Expected:
[(0, 3, word: 01), (0, 5, word: 1), (3, 1, word: 011), (3, 4, word:
1), (5, 2, word: 011), (5, 6, word: 1)]
Got:
[(0, 1, word: 01011), (0, 2, word: 1011), (0, 3, word: 01), (0, 5,
word: 1), (0, 7, word: 1), (3, 1, word: 011), (3, 4, word: 1), (5, 2,
word: 011), (5, 6, word: 1), (7, 2, word: 011)]
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1389:
sage: NST.word_to_node(0, W("ca"))
Expected:
('node', 17, word: )
Got:
('implicit', ((0, 5, word: cabaabaca), 2), word: )
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1391:
sage: NST.word_to_node(0, W("cab"))
Expected:
('implicit', ((17, 5, word: baabaca), 1), word: )
Got:
('implicit', ((0, 5, word: cabaabaca), 3), word: )
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1393:
sage: NST.word_to_node(17, W("b"))
Expected:
('implicit', ((17, 5, word: baabaca), 1), word: )
Got:
('node', 17, word: b)
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1395:
sage: NST.word_to_node(15, W("baabacabca"))
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_41[8]>", line 1, in <module>
NST.word_to_node(Integer(15), W("baabacabca"))###line 1395:
sage: NST.word_to_node(15, W("baabacabca"))
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/combinat/words/suffix_trees.py", line 1400, in word_to_node
for v in self.successor_iterator(node):
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph.py", line 10434, in successor_iterator
return iter(set(self._backend.iterator_out_nbrs(vertex)))
File "c_graph.pyx", line 615, in
sage.graphs.base.c_graph.CGraphBackend.iterator_out_nbrs
(sage/graphs/base/c_graph.c:7952)
KeyError: 15
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1464:
sage: NaiveSuffixTree(Word("abacabaabaca")).plot()
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_43[3]>", line 1, in <module>
NaiveSuffixTree(Word("abacabaabaca")).plot()###line 1464:
sage: NaiveSuffixTree(Word("abacabaabaca")).plot()
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/combinat/words/suffix_trees.py", line 1477, in plot
*args, **kwds)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/plot/misc.py", line 325, in wrapper
return func(*args, **options)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph.py", line 6513, in plot
return GraphPlot(graph=self, options=options).plot()
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph_plot.py", line 84, in __init__
self.set_pos()
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph_plot.py", line 148, in set_pos
raise RuntimeError("Cannot use tree layout on this graph:
self.is_tree() returns False.")
RuntimeError: Cannot use tree layout on this graph: self.is_tree()
returns False.
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1469:
sage: type(NaiveSuffixTree(Word("abacabaabaca")).plot())
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/sagedoctest.py", line 38,
in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File "/Users/rlmill/sage-4.0.rc0/local/bin/ncadoctest.py", line
1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_43[5]>", line 1, in <module>
type(NaiveSuffixTree(Word("abacabaabaca")).plot())###line 1469:
sage: type(NaiveSuffixTree(Word("abacabaabaca")).plot())
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/combinat/words/suffix_trees.py", line 1477, in plot
*args, **kwds)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/plot/misc.py", line 325, in wrapper
return func(*args, **options)
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph.py", line 6513, in plot
return GraphPlot(graph=self, options=options).plot()
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph_plot.py", line 84, in __init__
self.set_pos()
File "/Users/rlmill/sage-4.0.rc0/local/lib/python2.5/site-
packages/sage/graphs/graph_plot.py", line 148, in set_pos
raise RuntimeError("Cannot use tree layout on this graph:
self.is_tree() returns False.")
RuntimeError: Cannot use tree layout on this graph: self.is_tree()
returns False.
**********************************************************************
File "/Users/rlmill/sage-4.0.rc0/devel/sage-
main/sage/combinat/words/suffix_trees.py", line 1487:
sage: NaiveSuffixTree(Word("abacabaabaca")).node_to_word(17)
Expected:
word: ca
Got:
word: aca
**********************************************************************
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6085#comment:9>
Sage <http://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
-~----------~----~----~----~------~----~------~--~---
