Opened 9 years ago

Closed 6 years ago

#10037 closed defect (fixed)

cddlib/Polyhedron bug

Reported by: mhampton Owned by: mhampton
Priority: major Milestone: sage-5.10
Component: geometry Keywords: cddlib, polyhedron, polyhedra
Cc: vbraun, dimpase, novoselt Merged in: sage-5.10.beta1
Authors: Volker Braun Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14479 Stopgaps:

Description (last modified by vbraun)

The following causes cddlib to crash; I'm not sure if this is fixable without patching the cddlib source:

p4 = polytopes.permutahedron(5,project=True)
pn4 = p4.projection()
p3  = pn4.schlegel()
verts = p3.transformed_coords
edges = p3.lines
topes = []
for q in p4.facial_incidences():
    topes.append([verts[i] for i in q[1]])
Polyhedron(vertices=topes[3], field=RDF, verbose=True)

output ends with:

Facet graph
*Error: Possibly an LP cycling occurs.  Use the Criss-Cross method.

Apply trac_10037_polyhedron_bug.patch to the sage library

Attachments (1)

trac_10037_polyhedron_bug.patch (1.1 KB) - added by vbraun 6 years ago.
Initial patch

Download all attachments as: .zip

Change History (8)

comment:1 Changed 9 years ago by vbraun

This one actually works for me (Fedora 13 x86_64):

sage: Polyhedron(vertices=topes[3], field=RDF, verbose=True)
[... vebose cdd interaction ...]
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 23 vertices.

Just out of curiosity, which arch is that failing on?

I think the way to go is to implement vertex/facet adjacencies ourselves with a modern LP solver, either cvxopt or PPL.

I've opened #10039 as a first step to switch to PPL.

comment:2 Changed 9 years ago by mhampton

It fails for me on an intel mac, OS X 10.6. It does work for me on linux (64 bit Ubuntu 9.10).

comment:3 Changed 6 years ago by vbraun

  • Authors set to Volker Braun
  • Dependencies set to #14479
  • Status changed from new to needs_review

#14479 adds raising a proper error, so I consider this fixed. Use rationals for exact arithmetic.

Patch is for a regression in calling schlegel() without specifying the direction.

Changed 6 years ago by vbraun

Initial patch

comment:4 Changed 6 years ago by vbraun

  • Description modified (diff)

comment:5 Changed 6 years ago by vbraun

  • Cc dimpase novoselt added

This trivial patch needs review...

comment:6 Changed 6 years ago by novoselt

  • Milestone set to sage-5.10
  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to positive_review

comment:7 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.