Face iterator for polyhedra#
This iterator in principle works on every graded lattice, where every interval of length two has exactly 4 elements (diamond property).
It also works on unbounded polyhedra, as those satisfy the diamond property, except for intervals including the empty face. A (slightly generalized) description of the algorithm can be found in [KS2019].
Terminology in this module:
Coatoms – the faces from which all others are constructed in the face iterator. This will be facets or Vrep. In non-dual mode, faces are constructed as intersections of the facets. In dual mode, they are constructed theoretically as joins of vertices. The coatoms are repsented as incidences with the atoms they contain.
Atoms – facets or Vrep depending on application of algorithm. Atoms are represented as incidences of coatoms they are contained in.
EXAMPLES:
Construct a face iterator:
sage: from sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator \
....: import FaceIterator
sage: P = polytopes.octahedron()
sage: C = CombinatorialPolyhedron(P)
sage: FaceIterator(C, False)
Iterator over the proper faces of a 3-dimensional combinatorial polyhedron
sage: FaceIterator(C, False, output_dimension=2)
Iterator over the 2-faces of a 3-dimensional combinatorial polyhedron
Iterator in the non-dual mode starts with facets:
sage: it = FaceIterator(C, False)
sage: [next(it) for _ in range(9)]
[A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
A 1-dimensional face of a 3-dimensional combinatorial polyhedron]
Iterator in the dual-mode starts with vertices:
sage: it = FaceIterator(C, True)
sage: [next(it) for _ in range(7)]
[A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
A 1-dimensional face of a 3-dimensional combinatorial polyhedron]
Obtain the Vrepresentation:
sage: it = FaceIterator(C, False)
sage: face = next(it)
sage: face.ambient_Vrepresentation()
(A vertex at (0, -1, 0), A vertex at (0, 0, -1), A vertex at (1, 0, 0))
sage: face.n_ambient_Vrepresentation()
3
Obtain the facet-representation:
sage: it = FaceIterator(C, True)
sage: face = next(it)
sage: face.ambient_Hrepresentation()
(An inequality (-1, -1, 1) x + 1 >= 0,
An inequality (-1, -1, -1) x + 1 >= 0,
An inequality (-1, 1, -1) x + 1 >= 0,
An inequality (-1, 1, 1) x + 1 >= 0)
sage: face.ambient_H_indices()
(4, 5, 6, 7)
sage: face.n_ambient_Hrepresentation()
4
In non-dual mode one can ignore all faces contained in the current face:
sage: it = FaceIterator(C, False)
sage: face = next(it)
sage: face.ambient_H_indices()
(7,)
sage: it.ignore_subfaces()
sage: [face.ambient_H_indices() for face in it]
[(6,),
(5,),
(4,),
(3,),
(2,),
(1,),
(0,),
(5, 6),
(1, 6),
(0, 1, 5, 6),
(4, 5),
(0, 5),
(0, 3, 4, 5),
(3, 4),
(2, 3),
(0, 3),
(0, 1, 2, 3),
(1, 2),
(0, 1)]
In dual mode one can ignore all faces that contain the current face:
sage: it = FaceIterator(C, True)
sage: face = next(it)
sage: face.ambient_V_indices()
(5,)
sage: it.ignore_supfaces()
sage: [face.ambient_V_indices() for face in it]
[(4,),
(3,),
(2,),
(1,),
(0,),
(3, 4),
(2, 4),
(0, 4),
(0, 3, 4),
(0, 2, 4),
(1, 3),
(0, 3),
(0, 1, 3),
(1, 2),
(0, 2),
(0, 1, 2),
(0, 1)]
There is a special face iterator class for geometric polyhedra. It yields (geometric) polyhedral faces and it also yields trivial faces. Otherwise, it works exactly the same:
sage: from sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator \
....: import FaceIterator_geom
sage: P = polytopes.cube()
sage: it = FaceIterator_geom(P)
sage: [next(it) for _ in range(5)]
[A 3-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 8 vertices,
A -1-dimensional face of a Polyhedron in ZZ^3,
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices]
sage: it
Iterator over the faces of a 3-dimensional polyhedron in ZZ^3
AUTHOR:
Jonathan Kliem (2019-04)
- class sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator#
Bases:
sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator_base
A class to iterate over all combinatorial faces of a polyhedron.
Construct all proper faces from the facets. In dual mode, construct all proper faces from the vertices. Dual will be faster for less vertices than facets.
INPUT:
C
– aCombinatorialPolyhedron
dual
– ifTrue
, then dual polyhedron is used for iteration (only possible for bounded Polyhedra)output_dimension
– if notNone
, then the face iterator will only yield faces of this dimension
See also
EXAMPLES:
Construct a face iterator:
sage: P = polytopes.cuboctahedron() sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator() sage: next(it) A 0-dimensional face of a 3-dimensional combinatorial polyhedron
Construct faces by the dual or not:
sage: it = C.face_generator(algorithm='primal') sage: next(it).dimension() 2 sage: it = C.face_generator(algorithm='dual') sage: next(it).dimension() 0
For unbounded polyhedra only non-dual iteration is possible:
sage: P = Polyhedron(rays=[[0,0,1], [0,1,0], [1,0,0]]) sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator() sage: [face.ambient_Vrepresentation() for face in it] [(A vertex at (0, 0, 0), A ray in the direction (0, 1, 0), A ray in the direction (1, 0, 0)), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (1, 0, 0)), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 0)), (A vertex at (0, 0, 0), A ray in the direction (1, 0, 0)), (A vertex at (0, 0, 0), A ray in the direction (0, 1, 0)), (A vertex at (0, 0, 0),), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1))] sage: it = C.face_generator(algorithm='dual') Traceback (most recent call last): ... ValueError: dual algorithm only available for bounded polyhedra
Construct a face iterator only yielding dimension \(2\) faces:
sage: P = polytopes.permutahedron(5) sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(dimension=2) sage: counter = 0 sage: for _ in it: counter += 1 sage: print ('permutahedron(5) has', counter, ....: 'faces of dimension 2') permutahedron(5) has 150 faces of dimension 2 sage: C.f_vector() (1, 120, 240, 150, 30, 1)
In non-dual mode one can ignore all faces contained in the current face:
sage: P = polytopes.cube() sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(algorithm='primal') sage: face = next(it) sage: face.ambient_H_indices() (5,) sage: it.ignore_subfaces() sage: [face.ambient_H_indices() for face in it] [(4,), (3,), (2,), (1,), (0,), (3, 4), (1, 4), (0, 4), (1, 3, 4), (0, 1, 4), (2, 3), (1, 3), (1, 2, 3), (1, 2), (0, 2), (0, 1, 2), (0, 1)] sage: it = C.face_generator(algorithm='dual') sage: next(it) A 0-dimensional face of a 3-dimensional combinatorial polyhedron sage: it.ignore_subfaces() Traceback (most recent call last): ... ValueError: only possible when not in dual mode
In dual mode one can ignore all faces that contain the current face:
sage: it = C.face_generator(algorithm='dual') sage: next(it) A 0-dimensional face of a 3-dimensional combinatorial polyhedron sage: face = next(it) sage: face.ambient_V_indices() (6,) sage: [face.ambient_V_indices() for face in it] [(5,), (4,), (3,), (2,), (1,), (0,), (6, 7), (4, 7), (2, 7), (4, 5, 6, 7), (1, 2, 6, 7), (2, 3, 4, 7), (5, 6), (1, 6), (0, 1, 5, 6), (4, 5), (0, 5), (0, 3, 4, 5), (3, 4), (2, 3), (0, 3), (0, 1, 2, 3), (1, 2), (0, 1)] sage: it = C.face_generator(algorithm='primal') sage: next(it) A 2-dimensional face of a 3-dimensional combinatorial polyhedron sage: it.ignore_supfaces() Traceback (most recent call last): ... ValueError: only possible when in dual mode
ALGORITHM:
The algorithm to visit all proper faces exactly once is roughly equivalent to the following. A (slightly generalized) description of the algorithm can be found in [KS2019].
Initialization:
faces = [set(facet) for facet in P.facets()] face_iterator(faces, [])
The function
face_iterator
is defined recursively. It visits all faces of the polyhedron \(P\), except those contained in any ofvisited_all
. It assumesfaces
to be exactly those facets of \(P\) that are not contained in any of thevisited_all
. It assumesvisited_all
to be some list of faces of a polyhedron \(P_2\), which contains \(P\) as one of its faces:def face_iterator(faces, visited_all): while facets: one_face = faces.pop() maybe_new_faces = [one_face.intersection(face) for face in faces] ...
At this point we claim that
maybe_new_faces
contains all facets ofone_face
, which we have not visited before.Proof: Let \(F\) be a facet of
one_face
. We have a chain: \(P \supset{}\)one_face
\({}\supset F\). By the diamond property, there exists asecond_face
with \(P \supset{}\)second_face
\({}\supset F\).Now either
second_face
is not an element offaces
: Hencesecond_face
is contained in one ofvisited_all
. In particular, \(F\) is contained invisited_all
.Or
second_face
is an element offaces
: Then, intersectingone_face
withsecond_face
givesF
.This concludes the proof.
Moreover, if an element in
maybe_new_faces
is inclusion-maximal and not contained in any of thevisited_all
, it is a facet ofone_face
. Any facet inmaybe_new_faces
ofone_face
is inclusion-maximal.Hence, in the following loop, an element
face1
inmaybe_new_faces
is a facet ofone_face
if and only if it is not contained in another facet:... maybe_new_faces2 = [] for i, face1 in enumerate(maybe_new_faces): if (all(not face1 < face2 for face2 in maybe_new_faces[:i]) and all(not face1 <= face2 for face2 in maybe_new_faces[i+1:])): maybe_new_faces2.append(face1) ...
Now
maybe_new_faces2
contains only facets ofone_face
and some faces contained in any ofvisited_all
. It also contains all the facets not contained in any ofvisited_all
.We construct
new_faces
as the list of all facets ofone_face
not contained in any ofvisited_all
:... new_faces = [] for face1 in maybe_new_faces2: if all(not face1 < face2 for face2 in visited_all): new_faces.append(face1) ...
By induction we can apply the algorithm, to visit all faces of
one_face
not contained invisited_all
:... face_iterator(new_faces, visited_all) ...
Finally we visit
one_face
and add it tovisited_all
:... visit(one_face) visited_all.append(one_face)
Note: At this point, we have visited exactly those faces, contained in any of the
visited_all
. The function ends here.ALGORITHM for the special case that all intervals of the lattice not containing zero are boolean (e.g. when the polyhedron is simple):
We do not assume any other properties of our lattice in this case. Note that intervals of length 2 not containing zero, have exactly 2 elements now. But the atom-representation of faces might not be unique.
We do the following modifications:
To check whether an intersection of faces is zero, we check whether the atom-representation is zero. Although not unique, it works to distinct from zero.
The intersection of two (relative) facets has always codimension \(1\) unless empty.
To intersect we now additionally unite the coatom representation. This gives the correct representation of the new face unless the intersection is zero.
To mark a face as visited, we save its coatom representation.
To check whether we have seen a face already, we check containment of the coatom representation.
- class sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator_base#
Bases:
sage.structure.sage_object.SageObject
A base class to iterate over all faces of a polyhedron.
Construct all proper faces from the facets. In dual mode, construct all proper faces from the vertices. Dual will be faster for less vertices than facets.
See
FaceIterator
.- current()#
Retrieve the last value of
next()
.EXAMPLES:
sage: P = polytopes.octahedron() sage: it = P.combinatorial_polyhedron().face_generator() sage: next(it) A 0-dimensional face of a 3-dimensional combinatorial polyhedron sage: it.current() A 0-dimensional face of a 3-dimensional combinatorial polyhedron sage: next(it).ambient_V_indices() == it.current().ambient_V_indices() True
- dual#
- ignore_subfaces()#
The iterator will not visit any faces of the current face.
Only possible when not in dual mode.
EXAMPLES:
sage: P = polytopes.Gosset_3_21() sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(algorithm='primal') sage: n_non_simplex_faces = 1 sage: for face in it: ....: if face.n_ambient_Vrepresentation() > face.dimension() + 1: ....: n_non_simplex_faces += 1 ....: else: ....: it.ignore_subfaces() ....: sage: n_non_simplex_faces 127
Face iterator must not be in dual mode:
sage: it = C.face_generator(algorithm='dual') sage: _ = next(it) sage: it.ignore_subfaces() Traceback (most recent call last): ... ValueError: only possible when not in dual mode
Ignoring the same face as was requested to visit only consumes the iterator:
sage: it = C.face_generator(algorithm='primal') sage: _ = next(it) sage: it.only_subfaces() sage: it.ignore_subfaces() sage: list(it) []
Face iterator must be set to a face first:
sage: it = C.face_generator(algorithm='primal') sage: it.ignore_subfaces() Traceback (most recent call last): ... ValueError: iterator not set to a face yet
- ignore_supfaces()#
The iterator will not visit any faces containing the current face.
Only possible when in dual mode.
EXAMPLES:
sage: P = polytopes.Gosset_3_21() sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(algorithm='dual') sage: n_faces_with_non_simplex_quotient = 1 sage: for face in it: ....: n_facets = face.n_ambient_Hrepresentation(add_equations=False) ....: if n_facets > C.dimension() - face.dimension() + 1: ....: n_faces_with_non_simplex_quotient += 1 ....: else: ....: it.ignore_supfaces() ....: sage: n_faces_with_non_simplex_quotient 4845
Face iterator must be in dual mode:
sage: it = C.face_generator(algorithm='primal') sage: _ = next(it) sage: it.ignore_supfaces() Traceback (most recent call last): ... ValueError: only possible when in dual mode
- join_of_Vrep(*indices)#
Construct the join of the Vrepresentatives indicated by the indices.
This is the smallest face containing all Vrepresentatives with the given indices.
The iterator must be reset if not newly initialized.
Note
In the case of unbounded polyhedra, the smallest face containing given Vrepresentatives may not be well defined.
EXAMPLES:
sage: P = polytopes.cube() sage: it = P.face_generator() sage: it.join_of_Vrep(1) A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex sage: it.join_of_Vrep(1,2).ambient_V_indices() (1, 2) sage: it.join_of_Vrep(1,3).ambient_V_indices() (0, 1, 2, 3) sage: it.join_of_Vrep(1,5).ambient_V_indices() (0, 1, 5, 6) sage: P = polytopes.cross_polytope(4) sage: it = P.face_generator() sage: it.join_of_Vrep().ambient_V_indices() () sage: it.join_of_Vrep(1,3).ambient_V_indices() (1, 3) sage: it.join_of_Vrep(1,2).ambient_V_indices() (1, 2) sage: it.join_of_Vrep(1,6).ambient_V_indices() (0, 1, 2, 3, 4, 5, 6, 7) sage: it.join_of_Vrep(8) Traceback (most recent call last): ... IndexError: coatoms out of range
If the iterator has already been used, it must be reset before:
sage: P = polytopes.dodecahedron() # optional - sage.rings.number_field sage: it = P.face_generator() # optional - sage.rings.number_field sage: _ = next(it), next(it) # optional - sage.rings.number_field sage: next(it).ambient_V_indices() # optional - sage.rings.number_field (15, 16, 17, 18, 19) sage: it.join_of_Vrep(1,10) # optional - sage.rings.number_field Traceback (most recent call last): ... ValueError: please reset the face iterator sage: it.reset() # optional - sage.rings.number_field sage: it.join_of_Vrep(1,10).ambient_V_indices() # optional - sage.rings.number_field (1, 10)
In the case of an unbounded polyhedron, we try to make sense of the input:
sage: P = polytopes.cube()*Polyhedron(lines=[[1]]) sage: it = P.face_generator() sage: it.join_of_Vrep(1) A 1-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 1 vertex and 1 line sage: it.join_of_Vrep(0, 1) A 1-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 1 vertex and 1 line sage: it.join_of_Vrep(0) Traceback (most recent call last): ... ValueError: the join is not well-defined sage: P = Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,1]]) sage: it = P.face_generator() sage: it.join_of_Vrep(0) A 0-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex sage: it.join_of_Vrep(1) A 0-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex sage: it.join_of_Vrep(2) Traceback (most recent call last): ... ValueError: the join is not well-defined sage: it.join_of_Vrep(0,2) A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray sage: P = Polyhedron(rays=[[1,0], [0,1]]) sage: it = P.face_generator() sage: it.join_of_Vrep(0) A 0-dimensional face of a Polyhedron in ZZ^2 defined as the convex hull of 1 vertex sage: it.join_of_Vrep(1,2) A 2-dimensional face of a Polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 rays
- meet_of_Hrep(*indices)#
Construct the meet of the facets indicated by the indices.
This is the largest face contained in all facets with the given indices.
The iterator must be reset if not newly initialized.
EXAMPLES:
sage: P = polytopes.cube() sage: it = P.face_generator() sage: it.meet_of_Hrep(1,2) A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices sage: it.meet_of_Hrep(1,2).ambient_H_indices() (1, 2) sage: it.meet_of_Hrep(1,3).ambient_H_indices() (1, 3) sage: it.meet_of_Hrep(1,5).ambient_H_indices() (0, 1, 2, 3, 4, 5) sage: P = polytopes.cross_polytope(4) sage: it = P.face_generator() sage: it.meet_of_Hrep().ambient_H_indices() () sage: it.meet_of_Hrep(1,3).ambient_H_indices() (1, 2, 3, 4) sage: it.meet_of_Hrep(1,2).ambient_H_indices() (1, 2) sage: it.meet_of_Hrep(1,6).ambient_H_indices() (1, 6) sage: it.meet_of_Hrep(1,2,6).ambient_H_indices() (1, 2, 6, 7) sage: it.meet_of_Hrep(1,2,5,6).ambient_H_indices() (0, 1, 2, 3, 4, 5, 6, 7) sage: s = cones.schur(4) sage: C = CombinatorialPolyhedron(s) sage: it = C.face_generator() sage: it.meet_of_Hrep(1,2).ambient_H_indices() (1, 2) sage: it.meet_of_Hrep(1,2,3).ambient_H_indices() Traceback (most recent call last): ... IndexError: coatoms out of range
If the iterator has already been used, it must be reset before:
sage: P = polytopes.dodecahedron() # optional - sage.rings.number_field sage: it = P.face_generator() # optional - sage.rings.number_field sage: _ = next(it), next(it) # optional - sage.rings.number_field sage: next(it).ambient_V_indices() # optional - sage.rings.number_field (15, 16, 17, 18, 19) sage: it.meet_of_Hrep(9,11) # optional - sage.rings.number_field Traceback (most recent call last): ... ValueError: please reset the face iterator sage: it.reset() # optional - sage.rings.number_field sage: it.meet_of_Hrep(9,11).ambient_H_indices() # optional - sage.rings.number_field (9, 11)
- next()#
Must be implemented by a derived class.
- only_subfaces()#
The iterator will visit all (remaining) subfaces of the current face and then terminate.
EXAMPLES:
sage: P = polytopes.cube() sage: it = P.face_generator() sage: next(it).ambient_H_indices() () sage: next(it).ambient_H_indices() (0, 1, 2, 3, 4, 5) sage: next(it).ambient_H_indices() (5,) sage: next(it).ambient_H_indices() (4,) sage: it.only_subfaces() sage: list(f.ambient_H_indices() for f in it) [(4, 5), (3, 4), (1, 4), (0, 4), (3, 4, 5), (0, 4, 5), (1, 3, 4), (0, 1, 4)]
sage: P = polytopes.Birkhoff_polytope(4) sage: C = P.combinatorial_polyhedron() sage: it = C.face_generator() sage: next(it).ambient_H_indices(add_equations=False) (15,) sage: next(it).ambient_H_indices(add_equations=False) (14,) sage: it.only_subfaces() sage: all(14 in f.ambient_H_indices() for f in it) True
Face iterator needs to be set to a face first:
sage: it = C.face_generator() sage: it.only_subfaces() Traceback (most recent call last): ... ValueError: iterator not set to a face yet
Face iterator must not be in dual mode:
sage: it = C.face_generator(algorithm='dual') sage: _ = next(it) sage: it.only_subfaces() Traceback (most recent call last): ... ValueError: only possible when not in dual mode
Cannot run
only_subfaces
afterignore_subfaces
:sage: it = C.face_generator() sage: _ = next(it) sage: it.ignore_subfaces() sage: it.only_subfaces() Traceback (most recent call last): ... ValueError: cannot only visit subsets after ignoring a face
- only_supfaces()#
The iterator will visit all (remaining) faces containing the current face and then terminate.
EXAMPLES:
sage: P = polytopes.cross_polytope(3) sage: it = P.face_generator() sage: next(it).ambient_V_indices() (0, 1, 2, 3, 4, 5) sage: next(it).ambient_V_indices() () sage: next(it).ambient_V_indices() (5,) sage: next(it).ambient_V_indices() (4,) sage: it.only_supfaces() sage: list(f.ambient_V_indices() for f in it) [(4, 5), (3, 4), (2, 4), (0, 4), (3, 4, 5), (2, 4, 5), (0, 3, 4), (0, 2, 4)]
sage: P = polytopes.Birkhoff_polytope(4) sage: C = P.combinatorial_polyhedron() sage: it = C.face_generator(algorithm='dual') sage: next(it).ambient_V_indices() (23,) sage: next(it).ambient_V_indices() (22,) sage: it.only_supfaces() sage: all(22 in f.ambient_V_indices() for f in it) True
- reset()#
Reset the iterator.
The iterator will start with the first face again.
EXAMPLES:
sage: P = polytopes.cube() sage: C = P.combinatorial_polyhedron() sage: it = C.face_generator() sage: next(it).ambient_V_indices() (0, 3, 4, 5) sage: it.reset() sage: next(it).ambient_V_indices() (0, 3, 4, 5)
- class sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator_geom#
Bases:
sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator_base
A class to iterate over all geometric faces of a polyhedron.
Construct all faces from the facets. In dual mode, construct all faces from the vertices. Dual will be faster for less vertices than facets.
INPUT:
P
– an instance ofPolyhedron_base
dual
– ifTrue
, then dual polyhedron is used for iteration (only possible for bounded Polyhedra)output_dimension
– if notNone
, then the FaceIterator will only yield faces of this dimension
EXAMPLES:
Construct a geometric face iterator:
sage: P = polytopes.cuboctahedron() sage: it = P.face_generator() sage: next(it) A 3-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 12 vertices
Construct faces by the dual or not:
sage: it = P.face_generator(algorithm='primal') sage: _ = next(it), next(it) sage: next(it).dim() 2 sage: it = P.face_generator(algorithm='dual') sage: _ = next(it), next(it) sage: next(it).dim() 0
For unbounded polyhedra only non-dual iteration is possible:
sage: P = Polyhedron(rays=[[0,0,1], [0,1,0], [1,0,0]]) sage: it = P.face_generator() sage: [face.ambient_Vrepresentation() for face in it] [(A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 0), A ray in the direction (1, 0, 0)), (), (A vertex at (0, 0, 0), A ray in the direction (0, 1, 0), A ray in the direction (1, 0, 0)), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (1, 0, 0)), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 0)), (A vertex at (0, 0, 0), A ray in the direction (1, 0, 0)), (A vertex at (0, 0, 0), A ray in the direction (0, 1, 0)), (A vertex at (0, 0, 0),), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1))] sage: it = P.face_generator(algorithm='dual') Traceback (most recent call last): ... ValueError: cannot iterate over dual of unbounded Polyedron
Construct a FaceIterator only yielding dimension \(2\) faces:
sage: P = polytopes.permutahedron(5) sage: it = P.face_generator(face_dimension=2) sage: counter = 0 sage: for _ in it: counter += 1 sage: print ('permutahedron(5) has', counter, ....: 'faces of dimension 2') permutahedron(5) has 150 faces of dimension 2 sage: P.f_vector() (1, 120, 240, 150, 30, 1)
In non-dual mode one can ignore all faces contained in the current face:
sage: P = polytopes.cube() sage: it = P.face_generator(algorithm='primal') sage: _ = next(it), next(it) sage: face = next(it) sage: face.ambient_H_indices() (5,) sage: it.ignore_subfaces() sage: [face.ambient_H_indices() for face in it] [(4,), (3,), (2,), (1,), (0,), (3, 4), (1, 4), (0, 4), (1, 3, 4), (0, 1, 4), (2, 3), (1, 3), (1, 2, 3), (1, 2), (0, 2), (0, 1, 2), (0, 1)] sage: it = P.face_generator(algorithm='dual') sage: _ = next(it), next(it) sage: next(it) A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex sage: it.ignore_subfaces() Traceback (most recent call last): ... ValueError: only possible when not in dual mode
In dual mode one can ignore all faces that contain the current face:
sage: P = polytopes.cube() sage: it = P.face_generator(algorithm='dual') sage: _ = next(it), next(it) sage: next(it) A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex sage: face = next(it) sage: face.ambient_V_indices() (6,) sage: [face.ambient_V_indices() for face in it] [(5,), (4,), (3,), (2,), (1,), (0,), (6, 7), (4, 7), (2, 7), (4, 5, 6, 7), (1, 2, 6, 7), (2, 3, 4, 7), (5, 6), (1, 6), (0, 1, 5, 6), (4, 5), (0, 5), (0, 3, 4, 5), (3, 4), (2, 3), (0, 3), (0, 1, 2, 3), (1, 2), (0, 1)] sage: it = P.face_generator(algorithm='primal') sage: _ = next(it), next(it) sage: next(it) A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices sage: it.ignore_supfaces() Traceback (most recent call last): ... ValueError: only possible when in dual mode
See also
- P#
- current()#
Retrieve the last value of
__next__()
.EXAMPLES:
sage: P = polytopes.octahedron() sage: it = P.face_generator() sage: _ = next(it), next(it) sage: next(it) A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex sage: it.current() A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex sage: next(it).ambient_V_indices() == it.current().ambient_V_indices() True
- reset()#
Reset the iterator.
The iterator will start with the first face again.
EXAMPLES:
sage: P = polytopes.cube() sage: it = P.face_generator() sage: next(it).ambient_V_indices() (0, 1, 2, 3, 4, 5, 6, 7) sage: next(it).ambient_V_indices() () sage: next(it).ambient_V_indices() (0, 3, 4, 5) sage: it.reset() sage: next(it).ambient_V_indices() (0, 1, 2, 3, 4, 5, 6, 7) sage: next(it).ambient_V_indices() () sage: next(it).ambient_V_indices() (0, 3, 4, 5)