Polytope.h

Go to the documentation of this file.

#pragma once
 
#include <boost/optional.hpp>
#include <memory>
#include <vector>
 
#include "storm/storage/BitVector.h"
#include "storm/storage/expressions/Expressions.h"
#include "storm/storage/geometry/Halfspace.h"
 
namespace storm {
namespace storage {
namespace geometry {
 
template<typename ValueType>
class Polytope {
   public:
    typedef std::vector<ValueType> Point;
 
    virtual ~Polytope();

    static std::shared_ptr<Polytope<ValueType>> create(std::vector<Halfspace<ValueType>> const& halfspaces);

    static std::shared_ptr<Polytope<ValueType>> create(std::vector<Point> const& points);

    static std::shared_ptr<Polytope<ValueType>> createUniversalPolytope();

    static std::shared_ptr<Polytope<ValueType>> createEmptyPolytope();

    static std::shared_ptr<Polytope<ValueType>> createDownwardClosure(std::vector<Point> const& points);

    static std::shared_ptr<Polytope<ValueType>> createSelectiveDownwardClosure(std::vector<Point> const& points,
                                                                               storm::storage::BitVector const& selectedDimensions);

    virtual std::vector<Point> getVertices() const = 0;

    virtual std::vector<Point> getVerticesInClockwiseOrder() const;

    virtual std::vector<Halfspace<ValueType>> getHalfspaces() const = 0;

    virtual bool isEmpty() const = 0;

    virtual bool isUniversal() const = 0;

    virtual bool contains(Point const& point) const = 0;

    virtual bool contains(std::shared_ptr<Polytope<ValueType>> const& other) const = 0;

    virtual std::shared_ptr<Polytope<ValueType>> intersection(std::shared_ptr<Polytope<ValueType>> const& rhs) const = 0;
    virtual std::shared_ptr<Polytope<ValueType>> intersection(Halfspace<ValueType> const& halfspace) const = 0;

    virtual std::shared_ptr<Polytope<ValueType>> convexUnion(std::shared_ptr<Polytope<ValueType>> const& rhs) const = 0;

    virtual std::shared_ptr<Polytope<ValueType>> minkowskiSum(std::shared_ptr<Polytope<ValueType>> const& rhs) const = 0;

    virtual std::shared_ptr<Polytope<ValueType>> affineTransformation(std::vector<Point> const& matrix, Point const& vector) const = 0;

    std::shared_ptr<Polytope<ValueType>> shift(Point const& b) const;

    virtual std::shared_ptr<Polytope<ValueType>> downwardClosure() const;

    std::vector<std::shared_ptr<Polytope<ValueType>>> setMinus(std::shared_ptr<Polytope<ValueType>> const& rhs) const;

    virtual std::pair<Point, bool> optimize(Point const& direction) const = 0;

    virtual std::vector<storm::expressions::Variable> declareVariables(storm::expressions::ExpressionManager& manager, std::string const& namePrefix) const;

    virtual std::vector<storm::expressions::Expression> getConstraints(storm::expressions::ExpressionManager const& manager,
                                                                       std::vector<storm::expressions::Variable> const& variables) const;

    template<typename TargetType>
    std::shared_ptr<Polytope<TargetType>> convertNumberRepresentation() const;

    virtual std::shared_ptr<Polytope<ValueType>> clean();
 
    /*
     * Returns a string representation of this polytope.
     * @param numbersAsDouble If true, the occurring numbers are converted to double before printing to increase readability.
     */
    virtual std::string toString(bool numbersAsDouble = false) const;
 
    virtual bool isNativePolytope() const;
 
   protected:
    Polytope();
 
   private:
    static std::shared_ptr<Polytope<ValueType>> create(boost::optional<std::vector<Halfspace<ValueType>>> const& halfspaces,
                                                       boost::optional<std::vector<Point>> const& points);
};
 
}  // namespace geometry
}  // namespace storage
}  // namespace storm