#11736: Linear time implementation of lex_BFS()
----------------------------+-----------------------------------------------
Reporter: ddestrada | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.7.2
Component: graph theory | Keywords: lexbfs
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
> Thank you! Here I fixed the "build/" thing, but I'm having trouble
running the tests (in OSX 10.7 and Ubuntu 11.04), so expect it to break
some of them. I'm sorry.
Perhaps I can help you with this test problem ? The thing is that right
now the patch does not seem to work :
{{{
sage: graphs.RandomInterval(30).is_interval()
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/home/ncohen/sage/devel/sage-3/sage/graphs/<ipython console> in <module>()
/home/ncohen/sage/local/lib/python2.6/site-
packages/sage/graphs/generic_graph.pyc in is_interval(self, certificate)
9606 # by the way :-)
9607
-> 9608 if not self.is_chordal():
9609 return False
9610
/home/ncohen/sage/local/lib/python2.6/site-
packages/sage/graphs/generic_graph.pyc in is_chordal(self, certificate)
9492 for v in peo:
9493
-> 9494 if t_peo.out_degree(v)>0:
9495
9496 x = t_peo.neighbor_out_iterator(v).next()
/home/ncohen/sage/local/lib/python2.6/site-
packages/sage/graphs/digraph.pyc in out_degree(self, vertices, labels)
1176 return di
1177 else:
-> 1178 return list(self.out_degree_iterator(vertices,
labels=labels))
1179
1180 def out_degree_iterator(self, vertices=None, labels=False):
/home/ncohen/sage/local/lib/python2.6/site-
packages/sage/graphs/digraph.pyc in out_degree_iterator(self, vertices,
labels)
1221 yield (v, d)
1222 else:
-> 1223 for v in vertices:
1224 d = 0
1225 for e in self.outgoing_edge_iterator(v):
TypeError: 'int' object is not iterable
sage: graphs.RandomInterval(30).is_interval()
---------------------------------------------------------------------------
IndexError Traceback (most recent call
last)
/home/ncohen/sage/devel/sage-3/sage/graphs/<ipython console> in <module>()
/home/ncohen/sage/local/lib/python2.6/site-
packages/sage/graphs/generic_graph.pyc in is_interval(self, certificate)
9606 # by the way :-)
9607
-> 9608 if not self.is_chordal():
9609 return False
9610
/home/ncohen/sage/local/lib/python2.6/site-
packages/sage/graphs/generic_graph.pyc in is_chordal(self, certificate)
9484 return all( gg.is_chordal() for gg in
self.connected_components_subgraphs() )
9485
-> 9486 peo,t_peo = self.lex_BFS(tree=True)
9487
9488 g = self.copy()
/home/ncohen/sage/local/lib/python2.6/site-
packages/sage/graphs/generic_graph.pyc in lex_BFS(self, reverse, tree,
initial_vertex)
11617 if subslice[a] < old_k:
11618 subslice[a] = k
> 11619 slice_head[k] = l
11620 k += 1
11621 slice_of[l] = subslice[a]
IndexError: list assignment index out of range
}}}
On random interval graphs sometimes the is_interval function works,
sometimes it does not... `^^;`
I tested you patch after having applied #11738 and #11735 but I do not
think this is where the bug comes from. Could you also add some comments
to your code, along with a reference to the paper you are following for
this implementation ? `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11736#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.
