Opened 11 years ago

Closed 9 years ago

#8148 closed defect (duplicate)

looking at the dual of a poset: IndexError

Reported by: jhpalmieri Owned by: sage-combinat
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords:
Cc: sage-combinat, brunellus, mjo Merged in:
Authors: Reviewers: Lukáš Lánský
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

In Sage 4.3.2.alpha0:

sage: Q = Poset({1: [], 3: [], 2: [1, 3]})
sage:  # works fine
sage: Q.dual().show()
IndexError: list index out of range

Note that the following works, and is what I'm using in my code right now:

sage: Poset(Q.hasse_diagram().reverse()).show()

Actually, though, this fails if Q is defined instead to be

sage: Q = Poset({1: [], 2: [1]})
sage:  # works fine, although the picture looks a little funny
sage: Poset(Q.hasse_diagram().reverse()).show()
RuntimeError: Error building image

See #10998 instead.

Attachments (2)

trac_8148_dual_uses_poset_constructor.patch (975 bytes) - added by brunellus 9 years ago.
trac_8148_dual_correctly_constructs_FinitePoset.patch (1.6 KB) - added by brunellus 9 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 9 years ago by brunellus

  • Cc brunellus added

comment:2 Changed 9 years ago by brunellus

sage:Poset({1: [], 3: [], 2: [1, 3]}).dual().relations()
RuntimeError                              Traceback (most recent call last)

/root/<ipython console> in <module>()

/root/Sage/sage/local/lib/python2.6/site-packages/sage/combinat/posets/posets.pyc in relations(self)
    717         - Rob Beezer (2011-05-04)
    718         """
--> 719         return list(self.relations_iterator())
    721     def relations_iterator(self):

/root/Sage/sage/local/lib/python2.6/site-packages/sage/combinat/posets/posets.pyc in relations_iterator(self)
    745         # Relies on vertices the fact that _elements correspond to the rows and
    746         # columns of the lequal matrix
--> 747         leq_mat = self.lequal_matrix()
    748         n = leq_mat.nrows()
    749         elements = self._elements

/root/Sage/sage/local/lib/python2.6/site-packages/sage/combinat/posets/posets.pyc in lequal_matrix(self, **kwds)
   1282             False
   1283         """
-> 1284         return self._hasse_diagram.lequal_matrix(**kwds)
   1286     def meet_matrix(self):

/root/Sage/sage/local/lib/python2.6/site-packages/sage/combinat/posets/hasse_diagram.pyc in lequal_matrix(self, ring, sparse)
    867         D = {}
    868         for i in range(n):
--> 869             for v in self.breadth_first_search(i):
    870                 D[(i,v)] = 1
    871         self._leq_matrix = matrix(ring, n, n, D, sparse=sparse)

/root/Sage/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in breadth_first_search(self, start, ignore_direction, distance, neighbors)
  11565         # Preferably use the Cython implementation 
  11566         if neighbors is None and not isinstance(start,list) and distance is None and hasattr(self._backend,"breadth_first_search"): 
> 11567             for v in self._backend.breadth_first_search(start, ignore_direction = ignore_direction): 
  11568                 yield v 
  11569         else: 

/root/Sage/sage/local/lib/python2.6/site-packages/sage/graphs/base/ in sage.graphs.base.c_graph.Search_iterator.__next__ (sage/graphs/base/c_graph.c:19732)()

/root/Sage/sage/local/lib/python2.6/site-packages/sage/graphs/base/ in sage.graphs.base.sparse_graph.SparseGraph.out_neighbors (sage/graphs/base/sparse_graph.c:8007)()

/root/Sage/sage/local/lib/python2.6/site-packages/sage/graphs/base/ in sage.graphs.base.sparse_graph.SparseGraph.out_neighbors (sage/graphs/base/sparse_graph.c:7841)()

/root/Sage/sage/local/lib/python2.6/site-packages/sage/graphs/base/ in sage.graphs.base.c_graph.CGraph.check_vertex (sage/graphs/base/c_graph.c:5697)()

RuntimeError: Vertex (0) is not a vertex of the graph.

Changed 9 years ago by brunellus

comment:3 Changed 9 years ago by brunellus

  • Status changed from new to needs_review

I guess this fix should help -- dual() created new Poset using FinitePoset? constructor that requires a DiGraph? in its argument to be rather refined one. Especially that the range(n) should be a linear extension of poset defined by a DiGraph?. That wasn't true, because dual() reversed the orientation of edges. Poset constructor is much more liberal.

comment:4 Changed 9 years ago by mjo

  • Cc mjo added

This is probably the best fix at the moment (although it would be nice if FinitePoset?() could be used by itself).

For the patch, can you add the ticket number to the doctest somewhere?

I would also create a "TESTS:" section under examples, since this isn't really a useful example independent of the fact that it demonstrates this bug.

You can give the doctest a little introduction, too. For example,


We should get a valid FinitePoset back if we call dual() on a finite poset (trac #8148)::

    sage: ...

It's the double-colon that says "here comes a doctest."

comment:5 Changed 9 years ago by brunellus

Thanks! I tried to rewrite this to use FinitePoset? immediately. Does it make sense? I tried to run it to few examples, but maybe there is something I overlooked.

comment:6 Changed 9 years ago by nthiery


Sorry, I should have been more reactive to spare you this patch. In principle, this is fixed by #10998 which is almost finished, and I hope to get in soon. Could you double check this?



comment:7 Changed 9 years ago by brunellus

  • Milestone changed from sage-4.8 to sage-duplicate/invalid/wontfix

Hi, I guess such situations are inevitable in distributed projects. :-) Your patch really solves this issue.

comment:8 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

(the procedure for closing tickets... positive review + milestone to wontfix)

comment:9 Changed 9 years ago by jdemeyer

  • Description modified (diff)
  • Resolution set to duplicate
  • Reviewers set to Lukáš Lánský
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.