H(yperplane) and V(ertex) representation objects for polyhedra#

class sage.geometry.polyhedron.representation.Equation(polyhedron_parent)[source]#

Bases: Hrepresentation

A linear equation of the polyhedron. That is, the polyhedron is strictly smaller-dimensional than the ambient space, and contained in this hyperplane. Inherits from Hrepresentation.

contains(Vobj)[source]#

Tests whether the hyperplane defined by the equation contains the given vertex/ray/line.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,0],[1,1,0],[1,2,0]])
sage: v = next(p.vertex_generator())
sage: v
A vertex at (0, 0, 0)
sage: a = next(p.equation_generator())
sage: a
An equation (0, 0, 1) x + 0 == 0
sage: a.contains(v)
True

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]])
>>> v = next(p.vertex_generator())
>>> v
A vertex at (0, 0, 0)
>>> a = next(p.equation_generator())
>>> a
An equation (0, 0, 1) x + 0 == 0
>>> a.contains(v)
True
interior_contains(Vobj)[source]#

Tests whether the interior of the halfspace (excluding its boundary) defined by the inequality contains the given vertex/ray/line.

Note

Return False for any equation.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,0],[1,1,0],[1,2,0]])
sage: v = next(p.vertex_generator())
sage: v
A vertex at (0, 0, 0)
sage: a = next(p.equation_generator())
sage: a
An equation (0, 0, 1) x + 0 == 0
sage: a.interior_contains(v)
False

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]])
>>> v = next(p.vertex_generator())
>>> v
A vertex at (0, 0, 0)
>>> a = next(p.equation_generator())
>>> a
An equation (0, 0, 1) x + 0 == 0
>>> a.interior_contains(v)
False
is_equation()[source]#

Tests if this object is an equation. By construction, it must be.

type()[source]#

Return the type (equation/inequality/vertex/ray/line) as an integer.

OUTPUT:

Integer. One of PolyhedronRepresentation.INEQUALITY, .EQUATION, .VERTEX, .RAY, or .LINE.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,0],[1,1,0],[1,2,0]])
sage: repr_obj = next(p.equation_generator())
sage: repr_obj.type()
1
sage: repr_obj.type() == repr_obj.INEQUALITY
False
sage: repr_obj.type() == repr_obj.EQUATION
True
sage: repr_obj.type() == repr_obj.VERTEX
False
sage: repr_obj.type() == repr_obj.RAY
False
sage: repr_obj.type() == repr_obj.LINE
False

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]])
>>> repr_obj = next(p.equation_generator())
>>> repr_obj.type()
1
>>> repr_obj.type() == repr_obj.INEQUALITY
False
>>> repr_obj.type() == repr_obj.EQUATION
True
>>> repr_obj.type() == repr_obj.VERTEX
False
>>> repr_obj.type() == repr_obj.RAY
False
>>> repr_obj.type() == repr_obj.LINE
False
class sage.geometry.polyhedron.representation.Hrepresentation(polyhedron_parent)[source]#

Bases: PolyhedronRepresentation

The internal base class for H-representation objects of a polyhedron. Inherits from PolyhedronRepresentation.

A()[source]#

Return the coefficient vector \(A\) in \(A\vec{x}+b\).

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,1,0],[0,0,1],[1,-1,0,],[1,0,-1]])
sage: pH = p.Hrepresentation(2)
sage: pH.A()
(1, 0)

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(1),-Integer(1),Integer(0),],[Integer(1),Integer(0),-Integer(1)]])
>>> pH = p.Hrepresentation(Integer(2))
>>> pH.A()
(1, 0)
adjacent()[source]#

Alias for neighbors().

b()[source]#

Return the constant \(b\) in \(A\vec{x}+b\).

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,1,0],[0,0,1],[1,-1,0,],[1,0,-1]])
sage: pH = p.Hrepresentation(2)
sage: pH.b()
0

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(1),-Integer(1),Integer(0),],[Integer(1),Integer(0),-Integer(1)]])
>>> pH = p.Hrepresentation(Integer(2))
>>> pH.b()
0
eval(Vobj)[source]#

Evaluate the left hand side \(A\vec{x}+b\) on the given vertex/ray/line.

EXAMPLES:

sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[-1,-1]])
sage: ineq = next(triangle.inequality_generator())
sage: ineq
An inequality (2, -1) x + 1 >= 0
sage: [ ineq.eval(v) for v in triangle.vertex_generator() ]
[0, 0, 3]
sage: [ ineq * v for v in triangle.vertex_generator() ]
[0, 0, 3]

>>> from sage.all import *
>>> triangle = Polyhedron(vertices=[[Integer(1),Integer(0)],[Integer(0),Integer(1)],[-Integer(1),-Integer(1)]])
>>> ineq = next(triangle.inequality_generator())
>>> ineq
An inequality (2, -1) x + 1 >= 0
>>> [ ineq.eval(v) for v in triangle.vertex_generator() ]
[0, 0, 3]
>>> [ ineq * v for v in triangle.vertex_generator() ]
[0, 0, 3]

If you pass a vector, it is assumed to be the coordinate vector of a point:

sage: ineq.eval( vector(ZZ, [3,2]) )
5

>>> from sage.all import *
>>> ineq.eval( vector(ZZ, [Integer(3),Integer(2)]) )
5
incident()[source]#

Return a generator for the incident H-representation objects, that is, the vertices/rays/lines satisfying the (in)equality.

EXAMPLES:

sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[-1,-1]])
sage: ineq = next(triangle.inequality_generator())
sage: ineq
An inequality (2, -1) x + 1 >= 0
sage: [ v for v in ineq.incident()]
[A vertex at (-1, -1), A vertex at (0, 1)]
sage: p = Polyhedron(vertices=[[0,0,0],[0,1,0],[0,0,1]], rays=[[1,-1,-1]])
sage: ineq = p.Hrepresentation(2)
sage: ineq
An inequality (1, 0, 1) x + 0 >= 0
sage: [ x for x in ineq.incident() ]
[A vertex at (0, 0, 0),
 A vertex at (0, 1, 0),
 A ray in the direction (1, -1, -1)]

>>> from sage.all import *
>>> triangle = Polyhedron(vertices=[[Integer(1),Integer(0)],[Integer(0),Integer(1)],[-Integer(1),-Integer(1)]])
>>> ineq = next(triangle.inequality_generator())
>>> ineq
An inequality (2, -1) x + 1 >= 0
>>> [ v for v in ineq.incident()]
[A vertex at (-1, -1), A vertex at (0, 1)]
>>> p = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)]], rays=[[Integer(1),-Integer(1),-Integer(1)]])
>>> ineq = p.Hrepresentation(Integer(2))
>>> ineq
An inequality (1, 0, 1) x + 0 >= 0
>>> [ x for x in ineq.incident() ]
[A vertex at (0, 0, 0),
 A vertex at (0, 1, 0),
 A ray in the direction (1, -1, -1)]
is_H()[source]#

Return True if the object is part of a H-representation (inequality or equation).

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,1,0],[0,0,1],[1,-1,0,],[1,0,-1]])
sage: pH = p.Hrepresentation(0)
sage: pH.is_H()
True

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(1),-Integer(1),Integer(0),],[Integer(1),Integer(0),-Integer(1)]])
>>> pH = p.Hrepresentation(Integer(0))
>>> pH.is_H()
True
is_equation()[source]#

Return True if the object is an equation of the H-representation.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,1,0],[0,0,1],[1,-1,0,],[1,0,-1]], eqns = [[1,1,-1]])
sage: pH = p.Hrepresentation(0)
sage: pH.is_equation()
True

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(1),-Integer(1),Integer(0),],[Integer(1),Integer(0),-Integer(1)]], eqns = [[Integer(1),Integer(1),-Integer(1)]])
>>> pH = p.Hrepresentation(Integer(0))
>>> pH.is_equation()
True
is_incident(Vobj)[source]#

Return whether the incidence matrix element (Vobj,self) == 1

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,0,0,1],[0,0,1,0,],[0,1,0,0],
....:     [1,-1,0,0],[1,0,-1,0,],[1,0,0,-1]])
sage: pH = p.Hrepresentation(0)
sage: pH.is_incident(p.Vrepresentation(1))
True
sage: pH.is_incident(p.Vrepresentation(5))
False

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(0),Integer(0),Integer(1)],[Integer(0),Integer(0),Integer(1),Integer(0),],[Integer(0),Integer(1),Integer(0),Integer(0)],
...     [Integer(1),-Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),-Integer(1),Integer(0),],[Integer(1),Integer(0),Integer(0),-Integer(1)]])
>>> pH = p.Hrepresentation(Integer(0))
>>> pH.is_incident(p.Vrepresentation(Integer(1)))
True
>>> pH.is_incident(p.Vrepresentation(Integer(5)))
False
is_inequality()[source]#

Return True if the object is an inequality of the H-representation.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,1,0],[0,0,1],[1,-1,0,],[1,0,-1]])
sage: pH = p.Hrepresentation(0)
sage: pH.is_inequality()
True

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(1),-Integer(1),Integer(0),],[Integer(1),Integer(0),-Integer(1)]])
>>> pH = p.Hrepresentation(Integer(0))
>>> pH.is_inequality()
True
neighbors()[source]#

Iterate over the adjacent facets (i.e. inequalities).

Only defined for inequalities.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,0,0,1],[0,0,1,0,],[0,1,0,0],
....:                        [1,-1,0,0],[1,0,-1,0,],[1,0,0,-1]])
sage: pH = p.Hrepresentation(0)
sage: a = list(pH.neighbors())
sage: a[0]
An inequality (0, -1, 0) x + 1 >= 0
sage: list(a[0])
[1, 0, -1, 0]

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(0),Integer(0),Integer(1)],[Integer(0),Integer(0),Integer(1),Integer(0),],[Integer(0),Integer(1),Integer(0),Integer(0)],
...                        [Integer(1),-Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),-Integer(1),Integer(0),],[Integer(1),Integer(0),Integer(0),-Integer(1)]])
>>> pH = p.Hrepresentation(Integer(0))
>>> a = list(pH.neighbors())
>>> a[Integer(0)]
An inequality (0, -1, 0) x + 1 >= 0
>>> list(a[Integer(0)])
[1, 0, -1, 0]
repr_pretty(**kwds)[source]#

Return a pretty representation of this equality/inequality.

INPUT:

  • prefix – a string

  • indices – a tuple or other iterable

  • latex – a boolean

OUTPUT:

A string

EXAMPLES:

sage: P = Polyhedron(ieqs=[(0, 1, 0, 0), (1, 2, 1, 0)],
....:                eqns=[(1, -1, -1, 1)])
sage: for h in P.Hrepresentation():
....:     print(h.repr_pretty())
x0 + x1 - x2 == 1
x0 >= 0
2*x0 + x1 >= -1

>>> from sage.all import *
>>> P = Polyhedron(ieqs=[(Integer(0), Integer(1), Integer(0), Integer(0)), (Integer(1), Integer(2), Integer(1), Integer(0))],
...                eqns=[(Integer(1), -Integer(1), -Integer(1), Integer(1))])
>>> for h in P.Hrepresentation():
...     print(h.repr_pretty())
x0 + x1 - x2 == 1
x0 >= 0
2*x0 + x1 >= -1
class sage.geometry.polyhedron.representation.Inequality(polyhedron_parent)[source]#

Bases: Hrepresentation

A linear inequality (supporting hyperplane) of the polyhedron. Inherits from Hrepresentation.

contains(Vobj)[source]#

Tests whether the halfspace (including its boundary) defined by the inequality contains the given vertex/ray/line.

EXAMPLES:

sage: p = polytopes.cross_polytope(3)
sage: i1 = next(p.inequality_generator())
sage: [i1.contains(q) for q in p.vertex_generator()]
[True, True, True, True, True, True]
sage: p2 = 3*polytopes.hypercube(3)
sage: [i1.contains(q) for q in p2.vertex_generator()]
[True, True, False, True, False, True, False, False]

>>> from sage.all import *
>>> p = polytopes.cross_polytope(Integer(3))
>>> i1 = next(p.inequality_generator())
>>> [i1.contains(q) for q in p.vertex_generator()]
[True, True, True, True, True, True]
>>> p2 = Integer(3)*polytopes.hypercube(Integer(3))
>>> [i1.contains(q) for q in p2.vertex_generator()]
[True, True, False, True, False, True, False, False]
interior_contains(Vobj)[source]#

Tests whether the interior of the halfspace (excluding its boundary) defined by the inequality contains the given vertex/ray/line.

EXAMPLES:

sage: p = polytopes.cross_polytope(3)
sage: i1 = next(p.inequality_generator())
sage: [i1.interior_contains(q) for q in p.vertex_generator()]
[False, True, True, False, False, True]
sage: p2 = 3*polytopes.hypercube(3)
sage: [i1.interior_contains(q) for q in p2.vertex_generator()]
[True, True, False, True, False, True, False, False]

>>> from sage.all import *
>>> p = polytopes.cross_polytope(Integer(3))
>>> i1 = next(p.inequality_generator())
>>> [i1.interior_contains(q) for q in p.vertex_generator()]
[False, True, True, False, False, True]
>>> p2 = Integer(3)*polytopes.hypercube(Integer(3))
>>> [i1.interior_contains(q) for q in p2.vertex_generator()]
[True, True, False, True, False, True, False, False]

If you pass a vector, it is assumed to be the coordinate vector of a point:

sage: P = Polyhedron(vertices=[[1,1],[1,-1],[-1,1],[-1,-1]])
sage: p = vector(ZZ, [1,0] )
sage: [ ieq.interior_contains(p) for ieq in P.inequality_generator() ]
[True, True, False, True]

>>> from sage.all import *
>>> P = Polyhedron(vertices=[[Integer(1),Integer(1)],[Integer(1),-Integer(1)],[-Integer(1),Integer(1)],[-Integer(1),-Integer(1)]])
>>> p = vector(ZZ, [Integer(1),Integer(0)] )
>>> [ ieq.interior_contains(p) for ieq in P.inequality_generator() ]
[True, True, False, True]
is_facet_defining_inequality(other)[source]#

Check if self defines a facet of other.

INPUT:

  • other – a polyhedron

See also

slack_matrix() incidence_matrix()

EXAMPLES:

sage: P = Polyhedron(vertices=[[0,0,0],[0,1,0]], rays=[[1,0,0]])
sage: P.inequalities()
(An inequality (1, 0, 0) x + 0 >= 0,
 An inequality (0, 1, 0) x + 0 >= 0,
 An inequality (0, -1, 0) x + 1 >= 0)
sage: Q = Polyhedron(ieqs=[[0,1,0,0]])
sage: Q.inequalities()[0].is_facet_defining_inequality(P)
True
sage: Q = Polyhedron(ieqs=[[0,2,0,3]])
sage: Q.inequalities()[0].is_facet_defining_inequality(P)
True
sage: Q = Polyhedron(ieqs=[[0,AA(2).sqrt(),0,3]])                           # needs sage.rings.number_field
sage: Q.inequalities()[0].is_facet_defining_inequality(P)
True
sage: Q = Polyhedron(ieqs=[[1,1,0,0]])
sage: Q.inequalities()[0].is_facet_defining_inequality(P)
False

>>> from sage.all import *
>>> P = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)]], rays=[[Integer(1),Integer(0),Integer(0)]])
>>> P.inequalities()
(An inequality (1, 0, 0) x + 0 >= 0,
 An inequality (0, 1, 0) x + 0 >= 0,
 An inequality (0, -1, 0) x + 1 >= 0)
>>> Q = Polyhedron(ieqs=[[Integer(0),Integer(1),Integer(0),Integer(0)]])
>>> Q.inequalities()[Integer(0)].is_facet_defining_inequality(P)
True
>>> Q = Polyhedron(ieqs=[[Integer(0),Integer(2),Integer(0),Integer(3)]])
>>> Q.inequalities()[Integer(0)].is_facet_defining_inequality(P)
True
>>> Q = Polyhedron(ieqs=[[Integer(0),AA(Integer(2)).sqrt(),Integer(0),Integer(3)]])                           # needs sage.rings.number_field
>>> Q.inequalities()[Integer(0)].is_facet_defining_inequality(P)
True
>>> Q = Polyhedron(ieqs=[[Integer(1),Integer(1),Integer(0),Integer(0)]])
>>> Q.inequalities()[Integer(0)].is_facet_defining_inequality(P)
False

sage: P = Polyhedron(vertices=[[0,0,0],[0,1,0]], lines=[[1,0,0]])
sage: P.inequalities()
(An inequality (0, 1, 0) x + 0 >= 0, An inequality (0, -1, 0) x + 1 >= 0)
sage: Q = Polyhedron(ieqs=[[0,1,0,0]])
sage: Q.inequalities()[0].is_facet_defining_inequality(P)
False
sage: Q = Polyhedron(ieqs=[[0,-1,0,0]])
sage: Q.inequalities()[0].is_facet_defining_inequality(P)
False
sage: Q = Polyhedron(ieqs=[[0,0,1,3]])
sage: Q.inequalities()[0].is_facet_defining_inequality(P)
True

>>> from sage.all import *
>>> P = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)]], lines=[[Integer(1),Integer(0),Integer(0)]])
>>> P.inequalities()
(An inequality (0, 1, 0) x + 0 >= 0, An inequality (0, -1, 0) x + 1 >= 0)
>>> Q = Polyhedron(ieqs=[[Integer(0),Integer(1),Integer(0),Integer(0)]])
>>> Q.inequalities()[Integer(0)].is_facet_defining_inequality(P)
False
>>> Q = Polyhedron(ieqs=[[Integer(0),-Integer(1),Integer(0),Integer(0)]])
>>> Q.inequalities()[Integer(0)].is_facet_defining_inequality(P)
False
>>> Q = Polyhedron(ieqs=[[Integer(0),Integer(0),Integer(1),Integer(3)]])
>>> Q.inequalities()[Integer(0)].is_facet_defining_inequality(P)
True
is_inequality()[source]#

Return True since this is, by construction, an inequality.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,0],[1,1,0],[1,2,0]])
sage: a = next(p.inequality_generator())
sage: a.is_inequality()
True

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]])
>>> a = next(p.inequality_generator())
>>> a.is_inequality()
True
outer_normal()[source]#

Return the outer normal vector of self.

OUTPUT:

The normal vector directed away from the interior of the polyhedron.

EXAMPLES:

sage: p = Polyhedron(vertices=[[0,0,0],[1,1,0],[1,2,0]])
sage: a = next(p.inequality_generator())
sage: a.outer_normal()
(1, -1, 0)

>>> from sage.all import *
>>> p = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]])
>>> a = next(p.inequality_generator())
>>> a.outer_normal()
(1, -1, 0)
type()[source]#

Return the type (equation/inequality/vertex/ray/line) as an integer.

OUTPUT:

Integer. One of PolyhedronRepresentation.INEQUALITY, .EQUATION, .VERTEX, .RAY, or .LINE.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,0],[1,1,0],[1,2,0]])
sage: repr_obj = next(p.inequality_generator())
sage: repr_obj.type()
0
sage: repr_obj.type() == repr_obj.INEQUALITY
True
sage: repr_obj.type() == repr_obj.EQUATION
False
sage: repr_obj.type() == repr_obj.VERTEX
False
sage: repr_obj.type() == repr_obj.RAY
False
sage: repr_obj.type() == repr_obj.LINE
False

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]])
>>> repr_obj = next(p.inequality_generator())
>>> repr_obj.type()
0
>>> repr_obj.type() == repr_obj.INEQUALITY
True
>>> repr_obj.type() == repr_obj.EQUATION
False
>>> repr_obj.type() == repr_obj.VERTEX
False
>>> repr_obj.type() == repr_obj.RAY
False
>>> repr_obj.type() == repr_obj.LINE
False
class sage.geometry.polyhedron.representation.Line(polyhedron_parent)[source]#

Bases: Vrepresentation

A line (Minkowski summand \(\simeq\RR\)) of the polyhedron. Inherits from Vrepresentation.

evaluated_on(Hobj)[source]#

Return \(A\vec{\ell}\)

EXAMPLES:

sage: p = Polyhedron(ieqs = [[1, 0, 0, 1],[1,1,0,0]])
sage: a = next(p.line_generator())
sage: h = next(p.inequality_generator())
sage: a.evaluated_on(h)
0

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(1), Integer(0), Integer(0), Integer(1)],[Integer(1),Integer(1),Integer(0),Integer(0)]])
>>> a = next(p.line_generator())
>>> h = next(p.inequality_generator())
>>> a.evaluated_on(h)
0
homogeneous_vector(base_ring=None)[source]#

Return homogeneous coordinates for this line.

Since a line is given by a direction, this is the vector with a 0 appended.

INPUT:

  • base_ring – the base ring of the vector.

EXAMPLES:

sage: P = Polyhedron(vertices=[(2,0)], rays=[(1,0)], lines=[(3,2)])
sage: P.lines()[0].homogeneous_vector()
(3, 2, 0)
sage: P.lines()[0].homogeneous_vector(RDF)
(3.0, 2.0, 0.0)

>>> from sage.all import *
>>> P = Polyhedron(vertices=[(Integer(2),Integer(0))], rays=[(Integer(1),Integer(0))], lines=[(Integer(3),Integer(2))])
>>> P.lines()[Integer(0)].homogeneous_vector()
(3, 2, 0)
>>> P.lines()[Integer(0)].homogeneous_vector(RDF)
(3.0, 2.0, 0.0)
is_line()[source]#

Tests if the object is a line. By construction it must be.

type()[source]#

Return the type (equation/inequality/vertex/ray/line) as an integer.

OUTPUT:

Integer. One of PolyhedronRepresentation.INEQUALITY, .EQUATION, .VERTEX, .RAY, or .LINE.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[1, 0, 0, 1],[1,1,0,0]])
sage: repr_obj = next(p.line_generator())
sage: repr_obj.type()
4
sage: repr_obj.type() == repr_obj.INEQUALITY
False
sage: repr_obj.type() == repr_obj.EQUATION
False
sage: repr_obj.type() == repr_obj.VERTEX
False
sage: repr_obj.type() == repr_obj.RAY
False
sage: repr_obj.type() == repr_obj.LINE
True

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(1), Integer(0), Integer(0), Integer(1)],[Integer(1),Integer(1),Integer(0),Integer(0)]])
>>> repr_obj = next(p.line_generator())
>>> repr_obj.type()
4
>>> repr_obj.type() == repr_obj.INEQUALITY
False
>>> repr_obj.type() == repr_obj.EQUATION
False
>>> repr_obj.type() == repr_obj.VERTEX
False
>>> repr_obj.type() == repr_obj.RAY
False
>>> repr_obj.type() == repr_obj.LINE
True
class sage.geometry.polyhedron.representation.PolyhedronRepresentation[source]#

Bases: SageObject

The internal base class for all representation objects of Polyhedron (vertices/rays/lines and inequalities/equations)

Note

You should not (and cannot) instantiate it yourself. You can only obtain them from a Polyhedron() class.

EQUATION = 1#
INEQUALITY = 0#
LINE = 4#
RAY = 3#
VERTEX = 2#
count(i)[source]#

Count the number of occurrences of i in the coordinates.

INPUT:

  • i – Anything.

OUTPUT:

Integer. The number of occurrences of i in the coordinates.

EXAMPLES:

sage: p = Polyhedron(vertices=[(0,1,1,2,1)])
sage: v = p.Vrepresentation(0); v
A vertex at (0, 1, 1, 2, 1)
sage: v.count(1)
3

>>> from sage.all import *
>>> p = Polyhedron(vertices=[(Integer(0),Integer(1),Integer(1),Integer(2),Integer(1))])
>>> v = p.Vrepresentation(Integer(0)); v
A vertex at (0, 1, 1, 2, 1)
>>> v.count(Integer(1))
3
index()[source]#

Return an arbitrary but fixed number according to the internal storage order.

Note

H-representation and V-representation objects are enumerated independently. That is, amongst all vertices/rays/lines there will be one with index()==0, and amongst all inequalities/equations there will be one with index()==0, unless the polyhedron is empty or spans the whole space.

EXAMPLES:

sage: s = Polyhedron(vertices=[[1],[-1]])
sage: first_vertex = next(s.vertex_generator())
sage: first_vertex.index()
0
sage: first_vertex == s.Vrepresentation(0)
True

>>> from sage.all import *
>>> s = Polyhedron(vertices=[[Integer(1)],[-Integer(1)]])
>>> first_vertex = next(s.vertex_generator())
>>> first_vertex.index()
0
>>> first_vertex == s.Vrepresentation(Integer(0))
True
polyhedron()[source]#

Return the underlying polyhedron.

vector(base_ring=None)[source]#

Return the vector representation of the H/V-representation object.

INPUT:

  • base_ring – the base ring of the vector.

OUTPUT:

For a V-representation object, a vector of length ambient_dim(). For a H-representation object, a vector of length ambient_dim() + 1.

EXAMPLES:

sage: s = polytopes.cuboctahedron()
sage: v = next(s.vertex_generator())
sage: v
A vertex at (-1, -1, 0)
sage: v.vector()
(-1, -1, 0)
sage: v()
(-1, -1, 0)
sage: type(v())
<class 'sage.modules.vector_integer_dense.Vector_integer_dense'>

>>> from sage.all import *
>>> s = polytopes.cuboctahedron()
>>> v = next(s.vertex_generator())
>>> v
A vertex at (-1, -1, 0)
>>> v.vector()
(-1, -1, 0)
>>> v()
(-1, -1, 0)
>>> type(v())
<class 'sage.modules.vector_integer_dense.Vector_integer_dense'>

Conversion to a different base ring can be forced with the optional argument:

sage: v.vector(RDF)
(-1.0, -1.0, 0.0)
sage: vector(RDF, v)
(-1.0, -1.0, 0.0)

>>> from sage.all import *
>>> v.vector(RDF)
(-1.0, -1.0, 0.0)
>>> vector(RDF, v)
(-1.0, -1.0, 0.0)
class sage.geometry.polyhedron.representation.Ray(polyhedron_parent)[source]#

Bases: Vrepresentation

A ray of the polyhedron. Inherits from Vrepresentation.

evaluated_on(Hobj)[source]#

Return \(A\vec{r}\)

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,0,1],[0,1,0],[1,-1,0]])
sage: a = next(p.ray_generator())
sage: h = next(p.inequality_generator())
sage: a.evaluated_on(h)
0

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(0),Integer(1)],[Integer(0),Integer(1),Integer(0)],[Integer(1),-Integer(1),Integer(0)]])
>>> a = next(p.ray_generator())
>>> h = next(p.inequality_generator())
>>> a.evaluated_on(h)
0
homogeneous_vector(base_ring=None)[source]#

Return homogeneous coordinates for this ray.

Since a ray is given by a direction, this is the vector with a 0 appended.

INPUT:

  • base_ring – the base ring of the vector.

EXAMPLES:

sage: P = Polyhedron(vertices=[(2,0)], rays=[(1,0)], lines=[(3,2)])
sage: P.rays()[0].homogeneous_vector()
(1, 0, 0)
sage: P.rays()[0].homogeneous_vector(RDF)
(1.0, 0.0, 0.0)

>>> from sage.all import *
>>> P = Polyhedron(vertices=[(Integer(2),Integer(0))], rays=[(Integer(1),Integer(0))], lines=[(Integer(3),Integer(2))])
>>> P.rays()[Integer(0)].homogeneous_vector()
(1, 0, 0)
>>> P.rays()[Integer(0)].homogeneous_vector(RDF)
(1.0, 0.0, 0.0)
is_ray()[source]#

Tests if this object is a ray. Always True by construction.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,0,1],[0,1,0],[1,-1,0]])
sage: a = next(p.ray_generator())
sage: a.is_ray()
True

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(0),Integer(1)],[Integer(0),Integer(1),Integer(0)],[Integer(1),-Integer(1),Integer(0)]])
>>> a = next(p.ray_generator())
>>> a.is_ray()
True
type()[source]#

Return the type (equation/inequality/vertex/ray/line) as an integer.

OUTPUT:

Integer. One of PolyhedronRepresentation.INEQUALITY, .EQUATION, .VERTEX, .RAY, or .LINE.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,0,1],[0,1,0],[1,-1,0]])
sage: repr_obj = next(p.ray_generator())
sage: repr_obj.type()
3
sage: repr_obj.type() == repr_obj.INEQUALITY
False
sage: repr_obj.type() == repr_obj.EQUATION
False
sage: repr_obj.type() == repr_obj.VERTEX
False
sage: repr_obj.type() == repr_obj.RAY
True
sage: repr_obj.type() == repr_obj.LINE
False

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(0),Integer(1)],[Integer(0),Integer(1),Integer(0)],[Integer(1),-Integer(1),Integer(0)]])
>>> repr_obj = next(p.ray_generator())
>>> repr_obj.type()
3
>>> repr_obj.type() == repr_obj.INEQUALITY
False
>>> repr_obj.type() == repr_obj.EQUATION
False
>>> repr_obj.type() == repr_obj.VERTEX
False
>>> repr_obj.type() == repr_obj.RAY
True
>>> repr_obj.type() == repr_obj.LINE
False
class sage.geometry.polyhedron.representation.Vertex(polyhedron_parent)[source]#

Bases: Vrepresentation

A vertex of the polyhedron. Inherits from Vrepresentation.

evaluated_on(Hobj)[source]#

Return \(A\vec{x}+b\)

EXAMPLES:

sage: p = polytopes.hypercube(3)
sage: v = next(p.vertex_generator())
sage: h = next(p.inequality_generator())
sage: v
A vertex at (1, -1, -1)
sage: h
An inequality (-1, 0, 0) x + 1 >= 0
sage: v.evaluated_on(h)
0

>>> from sage.all import *
>>> p = polytopes.hypercube(Integer(3))
>>> v = next(p.vertex_generator())
>>> h = next(p.inequality_generator())
>>> v
A vertex at (1, -1, -1)
>>> h
An inequality (-1, 0, 0) x + 1 >= 0
>>> v.evaluated_on(h)
0
homogeneous_vector(base_ring=None)[source]#

Return homogeneous coordinates for this vertex.

Since a vertex is given by an affine point, this is the vector with a 1 appended.

INPUT:

  • base_ring – the base ring of the vector.

EXAMPLES:

sage: P = Polyhedron(vertices=[(2,0)], rays=[(1,0)], lines=[(3,2)])
sage: P.vertices()[0].homogeneous_vector()
(2, 0, 1)
sage: P.vertices()[0].homogeneous_vector(RDF)
(2.0, 0.0, 1.0)

>>> from sage.all import *
>>> P = Polyhedron(vertices=[(Integer(2),Integer(0))], rays=[(Integer(1),Integer(0))], lines=[(Integer(3),Integer(2))])
>>> P.vertices()[Integer(0)].homogeneous_vector()
(2, 0, 1)
>>> P.vertices()[Integer(0)].homogeneous_vector(RDF)
(2.0, 0.0, 1.0)
is_integral()[source]#

Return whether the coordinates of the vertex are all integral.

OUTPUT:

Boolean.

EXAMPLES:

sage: p = Polyhedron([(1/2,3,5), (0,0,0), (2,3,7)])
sage: [ v.is_integral() for v in p.vertex_generator() ]
[True, False, True]

>>> from sage.all import *
>>> p = Polyhedron([(Integer(1)/Integer(2),Integer(3),Integer(5)), (Integer(0),Integer(0),Integer(0)), (Integer(2),Integer(3),Integer(7))])
>>> [ v.is_integral() for v in p.vertex_generator() ]
[True, False, True]
is_vertex()[source]#

Tests if this object is a vertex. By construction it always is.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,0,1],[0,1,0],[1,-1,0]])
sage: a = next(p.vertex_generator())
sage: a.is_vertex()
True

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(0),Integer(0),Integer(1)],[Integer(0),Integer(1),Integer(0)],[Integer(1),-Integer(1),Integer(0)]])
>>> a = next(p.vertex_generator())
>>> a.is_vertex()
True
type()[source]#

Return the type (equation/inequality/vertex/ray/line) as an integer.

OUTPUT:

Integer. One of PolyhedronRepresentation.INEQUALITY, .EQUATION, .VERTEX, .RAY, or .LINE.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,0],[1,1,0],[1,2,0]])
sage: repr_obj = next(p.vertex_generator())
sage: repr_obj.type()
2
sage: repr_obj.type() == repr_obj.INEQUALITY
False
sage: repr_obj.type() == repr_obj.EQUATION
False
sage: repr_obj.type() == repr_obj.VERTEX
True
sage: repr_obj.type() == repr_obj.RAY
False
sage: repr_obj.type() == repr_obj.LINE
False

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]])
>>> repr_obj = next(p.vertex_generator())
>>> repr_obj.type()
2
>>> repr_obj.type() == repr_obj.INEQUALITY
False
>>> repr_obj.type() == repr_obj.EQUATION
False
>>> repr_obj.type() == repr_obj.VERTEX
True
>>> repr_obj.type() == repr_obj.RAY
False
>>> repr_obj.type() == repr_obj.LINE
False
class sage.geometry.polyhedron.representation.Vrepresentation(polyhedron_parent)[source]#

Bases: PolyhedronRepresentation

The base class for V-representation objects of a polyhedron. Inherits from PolyhedronRepresentation.

adjacent()[source]#

Alias for neighbors().

incident()[source]#

Return a generator for the equations/inequalities that are satisfied on the given vertex/ray/line.

EXAMPLES:

sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[-1,-1]])
sage: ineq = next(triangle.inequality_generator())
sage: ineq
An inequality (2, -1) x + 1 >= 0
sage: [ v for v in ineq.incident()]
[A vertex at (-1, -1), A vertex at (0, 1)]
sage: p = Polyhedron(vertices=[[0,0,0],[0,1,0],[0,0,1]], rays=[[1,-1,-1]])
sage: ineq = p.Hrepresentation(2)
sage: ineq
An inequality (1, 0, 1) x + 0 >= 0
sage: [ x for x in ineq.incident() ]
[A vertex at (0, 0, 0),
 A vertex at (0, 1, 0),
 A ray in the direction (1, -1, -1)]

>>> from sage.all import *
>>> triangle = Polyhedron(vertices=[[Integer(1),Integer(0)],[Integer(0),Integer(1)],[-Integer(1),-Integer(1)]])
>>> ineq = next(triangle.inequality_generator())
>>> ineq
An inequality (2, -1) x + 1 >= 0
>>> [ v for v in ineq.incident()]
[A vertex at (-1, -1), A vertex at (0, 1)]
>>> p = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)]], rays=[[Integer(1),-Integer(1),-Integer(1)]])
>>> ineq = p.Hrepresentation(Integer(2))
>>> ineq
An inequality (1, 0, 1) x + 0 >= 0
>>> [ x for x in ineq.incident() ]
[A vertex at (0, 0, 0),
 A vertex at (0, 1, 0),
 A ray in the direction (1, -1, -1)]
is_V()[source]#

Return True if the object is part of a V-representation (a vertex, ray, or line).

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0],[1,0],[0,3],[1,3]])
sage: v = next(p.vertex_generator())
sage: v.is_V()
True

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0)],[Integer(1),Integer(0)],[Integer(0),Integer(3)],[Integer(1),Integer(3)]])
>>> v = next(p.vertex_generator())
>>> v.is_V()
True
is_incident(Hobj)[source]#

Return whether the incidence matrix element (self,Hobj) == 1

EXAMPLES:

sage: p = polytopes.hypercube(3)
sage: h1 = next(p.inequality_generator())
sage: h1
An inequality (-1, 0, 0) x + 1 >= 0
sage: v1 = next(p.vertex_generator())
sage: v1
A vertex at (1, -1, -1)
sage: v1.is_incident(h1)
True

>>> from sage.all import *
>>> p = polytopes.hypercube(Integer(3))
>>> h1 = next(p.inequality_generator())
>>> h1
An inequality (-1, 0, 0) x + 1 >= 0
>>> v1 = next(p.vertex_generator())
>>> v1
A vertex at (1, -1, -1)
>>> v1.is_incident(h1)
True
is_line()[source]#

Return True if the object is a line of the V-representation. This method is over-ridden by the corresponding method in the derived class Line.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[1, 0, 0, 0, 1], [1, 1, 0, 0, 0], [1, 0, 1, 0, 0]])
sage: line1 = next(p.line_generator())
sage: line1.is_line()
True
sage: v1 = next(p.vertex_generator())
sage: v1.is_line()
False

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)], [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], [Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)]])
>>> line1 = next(p.line_generator())
>>> line1.is_line()
True
>>> v1 = next(p.vertex_generator())
>>> v1.is_line()
False
is_ray()[source]#

Return True if the object is a ray of the V-representation. This method is over-ridden by the corresponding method in the derived class Ray.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[1, 0, 0, 0, 1], [1, 1, 0, 0, 0], [1, 0, 1, 0, 0]])
sage: r1 = next(p.ray_generator())
sage: r1.is_ray()
True
sage: v1 = next(p.vertex_generator())
sage: v1
A vertex at (-1, -1, 0, -1)
sage: v1.is_ray()
False

>>> from sage.all import *
>>> p = Polyhedron(ieqs = [[Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)], [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], [Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)]])
>>> r1 = next(p.ray_generator())
>>> r1.is_ray()
True
>>> v1 = next(p.vertex_generator())
>>> v1
A vertex at (-1, -1, 0, -1)
>>> v1.is_ray()
False
is_vertex()[source]#

Return True if the object is a vertex of the V-representation. This method is over-ridden by the corresponding method in the derived class Vertex.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0],[1,0],[0,3],[1,3]])
sage: v = next(p.vertex_generator())
sage: v.is_vertex()
True
sage: p = Polyhedron(ieqs = [[1, 0, 0, 0, 1], [1, 1, 0, 0, 0], [1, 0, 1, 0, 0]])
sage: r1 = next(p.ray_generator())
sage: r1.is_vertex()
False

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0)],[Integer(1),Integer(0)],[Integer(0),Integer(3)],[Integer(1),Integer(3)]])
>>> v = next(p.vertex_generator())
>>> v.is_vertex()
True
>>> p = Polyhedron(ieqs = [[Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)], [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], [Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)]])
>>> r1 = next(p.ray_generator())
>>> r1.is_vertex()
False
neighbors()[source]#

Return a generator for the adjacent vertices/rays/lines.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0],[1,0],[0,3],[1,4]])
sage: v = next(p.vertex_generator())
sage: next(v.neighbors())
A vertex at (0, 3)

>>> from sage.all import *
>>> p = Polyhedron(vertices = [[Integer(0),Integer(0)],[Integer(1),Integer(0)],[Integer(0),Integer(3)],[Integer(1),Integer(4)]])
>>> v = next(p.vertex_generator())
>>> next(v.neighbors())
A vertex at (0, 3)
sage.geometry.polyhedron.representation.repr_pretty(coefficients, type, prefix='x', indices=None, latex=False, style='>=', split=False)[source]#

Return a pretty representation of equation/inequality represented by the coefficients.

INPUT:

  • coefficients – a tuple or other iterable

  • type – either 0 (PolyhedronRepresentation.INEQUALITY) or 1 (PolyhedronRepresentation.EQUATION)

  • prefix – a string (default: x)

  • indices – a tuple or other iterable

  • latex – a boolean

  • split – a boolean; (Default: False). If set to True,

    the output is split into a 3-tuple containing the left-hand side, the relation, and the right-hand side of the object.

  • style – either "positive" (making all coefficients positive), or

    "<=" or ">=".

OUTPUT:

A string or 3-tuple of strings (depending on split).

EXAMPLES:

sage: from sage.geometry.polyhedron.representation import repr_pretty
sage: from sage.geometry.polyhedron.representation import PolyhedronRepresentation
sage: print(repr_pretty((0, 1, 0, 0), PolyhedronRepresentation.INEQUALITY))
x0 >= 0
sage: print(repr_pretty((1, 2, 1, 0), PolyhedronRepresentation.INEQUALITY))
2*x0 + x1 >= -1
sage: print(repr_pretty((1, -1, -1, 1), PolyhedronRepresentation.EQUATION))
-x0 - x1 + x2 == -1

>>> from sage.all import *
>>> from sage.geometry.polyhedron.representation import repr_pretty
>>> from sage.geometry.polyhedron.representation import PolyhedronRepresentation
>>> print(repr_pretty((Integer(0), Integer(1), Integer(0), Integer(0)), PolyhedronRepresentation.INEQUALITY))
x0 >= 0
>>> print(repr_pretty((Integer(1), Integer(2), Integer(1), Integer(0)), PolyhedronRepresentation.INEQUALITY))
2*x0 + x1 >= -1
>>> print(repr_pretty((Integer(1), -Integer(1), -Integer(1), Integer(1)), PolyhedronRepresentation.EQUATION))
-x0 - x1 + x2 == -1