Your code, after the patch, seems to work (I tested it on all graphs with 8 vertices, and it doesn't fail), but I think it differs from what the paper does. The first difference is that, after LexBFS, the current code processes the vertices in the PEO order, and chooses the first violating vertex. In the paper, they choose the _last_. Also, their way of choosing the two neighbours is different.
The above code I posted is wrong (new try is below). My new implementation passes all graphs with 8 vertices, too. This seems hard to test ... ========== 9488c9488 < --- > pos_in_peo = dict(zip(peo, range(self.order()))) 9490,9492c9490 < for v in peo: < < if t_peo.out_degree(v)>0 and g.neighbors(v) not in neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]: --- > for v in reversed(peo): 9494c9492 < x = t_peo.neighbor_out_iterator(v).next() --- > if t_peo.out_degree(v)>0 and [v1 for v1 in g.neighbors(v) if > pos_in_peo[v1] > pos_in_peo[v]] not in > neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]: 9503,9509c9501,9510 < < S = neighbors_subsets[x] < < for y in g.neighbors(v): < if [y] not in S: < break < --- > max_tup = (-1, 0) > nb1 = [u for u in g.neighbors(v) if pos_in_peo[u] > > pos_in_peo[v]] > for xi in nb1: > for yi in nb1: > if not [yi] in neighbors_subsets[xi]: > new_tup = (pos_in_peo[xi], pos_in_peo[yi]) > if max_tup < new_tup: > max_tup = new_tup > x, y = xi, yi > g.delete_vertices([vv for vv in g.vertices() if > pos_in_peo[vv] < pos_in_peo[v]]) 9528,9529d9528 < g.delete_vertex(v) < ========== -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
