1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

/**************************************************************************
* *
* Regina  A Normal Surface Theory Calculator *
* Computational Engine *
* *
* Copyright (c) 19992016, Ben Burton *
* For further details contact Ben Burton (bab@debian.org). *
* *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation; either version 2 of the *
* License, or (at your option) any later version. *
* *
* As an exception, when this program is distributed through (i) the *
* App Store by Apple Inc.; (ii) the Mac App Store by Apple Inc.; or *
* (iii) Google Play by Google Inc., then that store may impose any *
* digital rights management, device limits and/or redistribution *
* restrictions that are required by its terms of service. *
* *
* This program is distributed in the hope that it will be useful, but *
* WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
* General Public License for more details. *
* *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, *
* MA 021101301, USA. *
* *
**************************************************************************/
/*! \file enumerate/maxadmissible.h
* \brief Provides an algorithm for enumerating maximal faces of a
* polyhedral cone that satisfy a set of admissibility constraints.
*/
#ifndef __MAXADMISSIBLE_H
#ifndef __DOXYGEN
#define __MAXADMISSIBLE_H
#endif
#include "reginacore.h"
#include "utilities/bitmask.h"
#include <vector>
namespace regina {
class EnumConstraints;
/**
* \weakgroup enumerate
* @{
*/
/**
* Used to enumerate all maximal admissible faces of a polyhedral cone
* under a given set of admissibility constraints. See the routine
* enumerate() for details.
*
* All routines of interest within this class are static; no object of
* this class should ever be created.
*
* \ifacespython Not present.
*/
class MaxAdmissible {
public:
/**
* Enumerates all maximal admissible faces of the given polyhedral cone.
* The cone must be the intersection of the nonnegative orthant in some
* Euclidean space R^n with a linear subspace.
*
* Admissibility is defined by the given set of constraints. Each
* constraint requires that at most one of a given set of coordinates
* can be nonzero; see the EnumConstraints class for details.
* In particular, the quadrilateral constraints from normal surface
* theory are of this type.
*
* It is simple to show that the admissible region of the cone is a
* union of faces, which we call "admissible faces". Those admissible
* faces that do not appear as a strict subface of some other
* admissible face are called "maximal admissible faces".
* The admissible region can therefore be expressed as the union of
* all maximal admissible faces.
*
* The input for this routine is the set of all admissible extremal rays
* of the cone. These should be computed beforehand; for instance,
* using the routine DoubleDescription::enumerateExtremalRays().
*
* The return value is the set of all maximal admissible faces, stored
* in a newly allocated vector. Each face \a F is described by a
* bitmask. Specifically: if we are working in R^n, then each face is
* described by a bitmask \a b of length n, where <tt>b[i]</tt>
* is \c false if every point \a x in \a F has <tt>x[i]=0</tt>,
* and <tt>b[i]</tt> is \c true if every point \a x in the relative
* interior of \a F has <tt>x[i] > 0</tt>.
*
* \pre The template argument RayIterator should be an iterator
* type that, when dereferenced, can be cast to (const Ray&).
*
* \pre The template argument BitmaskType is one of the bitmask
* types Bitmask, Bitmask1 or Bitmask2.
*
* \pre Bitmasks of type BitmaskType can hold \a n bits, where
* \a n is the dimension of the underlying space (i.e., the size
* of the input vectors described by \a beginExtremalRays and
* \a endExtremalRays). This is always true of Bitmask, but
* you must be careful when using one of the fast but sizelimited
* types Bitmask1 or Bitmask2.
*
* @param beginExtremalRays an iterator that begins the set of
* admissible extremal rays, as described above. Typically this would
* be rays.begin() if \a rays is a standard container type.
* @param endExtremalRays an iterator that is pasttheend of the set
* of admissible extremal rays. Typically this would be rays.end()
* if \a rays is a standard container type.
* @param constraints a set of validity constraints as described
* above. This may be 0 to indicate no constraints (in which
* case there will be just one maximal admissible face).
* @return a newly allocated list containing one bitmask
* representing each maximal admissible face, as described above.
*/
template <class BitmaskType, class RayIterator>
static std::vector<BitmaskType>* enumerate(
RayIterator beginExtremalRays, RayIterator endExtremalRays,
const EnumConstraints* constraints);
};
/*@}*/
} // namespace regina
// Template definitions
#include "enumerate/maxadmissibleimpl.h"
#endif
