#  Copyright (c) 1997-2006
#  Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
#  http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de
#
#  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, or (at your option) any
#  later version: http://www.gnu.org/licenses/gpl.txt.
#
#  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.
#-----------------------------------------------------------------------------
#  $Project: polymake $$Id: polytope_properties.rules 7556 2007-01-12 17:36:36Z gawrilow $

object Polytope;

# category: Basic properties
# Points such that the polyhedron is their convex hull.
# Redundancies are allowed.
# Vector `(x_0 x_1 .. x_d)` represents a point in `(d+1)`-space (<a href="../model.html">homogeneous coordinates</a>.)
# Affine points are identified by `x_0 > 0`.
# Points with `x_0 = 0` can be interpreted as rays.
#
# polymake automatically normalizes each coordinate vector, dividing them by the first non-zero element.
# The clients and rule subroutines can always assume that `x_0` is either `0` or `1`.
# Dual to @see INEQUALITIES.
#
# Input section only.  Ask for @see VERTICES if you want to compute a V-representation from an H-representation.

property POINTS
$type="matrix";
$accept="canonicalize";


# category: Basic properties
# Vertices of the polyhedron. No redundancies are allowed.
# The coordinates are normalized the same way as @see POINTS. Dual to @see FACETS.

property VERTICES
$type="matrix";
$accept="canonicalize";
$diff=sub : method {
   my $this=shift;
   my @perm;
   client("vertex_permutation", $this, "-primal", \@perm, @_);
   [ $perm[0] =~ /\d+/g ]
};

method canonicalize {
   my ($this, $data)=@_;
   my $matrix=ref($data) ? $data : [ $data ];
   foreach my $line (@$matrix) {
      if ($line !~ /^ (?: 1\s | (?: 0\s+)+ -?1\s)/x) {
	 my $converted=[ ];
	 client("canonical_coord", $this, $matrix, $converted);
	 return $converted;
      }
   }
   return $data;
}

method dehomogenize {
   no integer;
   shift;	# get rid of the object
   map {
      my ($first, @rest)=split;
      join(" ", map { $_/$first } @rest)."\n";
   } &convert_to_float;
}

method project_down {
   my $self=shift;
   map {
     s/\s+\S+$//;
     $_;
   } $self->dehomogenize(@_);
}


# category: Basic properties
# Inequalities that describe half-spaces such that the polyhedron is their intersection.
# Redundancies are allowed.  Dual to @see POINTS.
#
# A vector `(A_0 A_1 .. A_d)` defines the
# (closed affine) half-space of points `(1,x_1,..,x_d)` such that
# `A_0 + A_1 x_1 + .. + A_d x_d >= 0`.
#
# Input section only.  Ask for @see FACETS and @see AFFINE_HULL if you want to compute an H-representation
# from a V-representation.

property INEQUALITIES
$type="matrix";


# category: Basic properties
# Facets of the polyhedron, encoded as @see INEQUALITIES. Dual to @see VERTICES.

property FACETS
$type="matrix";
$diff=sub : method {
   my $this=shift;
   my @perm;
   client("vertex_permutation", $this, "-dual", \@perm, @_);
   [ $perm[0] =~ /\d+/g ]
};


# category: Basic properties
# Equations that hold for all points of the polyhedron.
#
# A vector `(A_0 A_1 .. A_d)` describes the hyperplane
# of all points `(1,x_1,..,x_d)` such that `A_0 + A_1 x_1 + .. + A_d x_d = 0`.
#
# Input section only.  Ask for @see AFFINE_HULL if you want to see an irredundant description of the affine span.

property EQUATIONS
$type="matrix";


# category: Basic properties
# Dual basis of the affine hull of the polyhedron.

property AFFINE_HULL
$type="matrix";
$diff=sub : method {
   compare_via_client("basis_compare", @_);
};


# category: Basic properties
# The i-th row is the normal vector of a hyperplane separating the i-th vertex from the rest ones.
# This property is a by-product of redundant point elimination algorithm.

property VERTEX_NORMALS
$type="matrix";
$apply_diff{VERTICES}=\&permute_rows;
$diff=sub { undef };	# this property has no canonical representation, we accept simply anything.


# category: Basic properties
# Some point belonging to the polyhedron.

property VALID_POINT
$type="vector";
$temporary=1;
$accept="canonicalize";


# category: Basic properties
# Dimension of the affine hull of the polyhedron = dimension of the polyhedron.
# If the polytope is given purely combinatorically, it's the dimension of a minimal embedding space
# deduced from the combinatorial structure.

property DIM
$type="cardinal";


# category: Basic properties
# Dimension of the space where the polyhedron lives in.

property AMBIENT_DIM
$type="cardinal";


# category: Basic properties
# True if the polyhedron is not empty.

property FEASIBLE
$type="boolean";


# category: Basic properties
# True if the polyhedron does not contain an affine line.

property POINTED
$type="boolean";


# category: Basic properties
# A vertex of a pointed polyhedron.

property ONE_VERTEX
$type="vector";


# category: Basic properties
# Indices of vertices that are rays.

property FAR_FACE
$type="set";
$apply_diff{VERTICES}=\&permute_cols;


# category: Basic properties
# Indices of facets that are unbounded.

property UNBOUNDED_FACETS
$type="set";
$apply_diff{FACETS}=\&permute_cols;


# category: Basic properties
# True if the polyhedron is a bounded polytope.

property BOUNDED
$type="boolean";


# category: Basic properties
# Graph of the bounded subcomplex.

property BOUNDED_GRAPH
$type="graph";


# category: Basic properties
# A @see LINEAR_OBJECTIVE function for which each unbounded edge is increasing;
# only defined for unbounded polyhedra.

property TOWARDS_FAR_FACE
$type="vector";


# category: Basic properties
# True if each bounded vertex of a (possibly unbounded) d-polyhedron has vertex degree d in the @see GRAPH.
# The vertex degrees of the vertices on the @see FAR_FACE do not matter.

property SIMPLE_POLYHEDRON
$type="boolean";


# category: Basic properties
# Graph of the bounded subcomplex.  Additionally each edge indicates the maximal dimension of a bounded
# face containing it.  Mainly used for visualization purposes.

property EDGE_COLORED_BOUNDED_GRAPH
$type="graph";


# category: Basic properties
# True if `(1,0,0,..)` is a relative interior point. Polar to @see BOUNDED.

property CENTERED
$type="boolean";


# category: Basic properties
# True if all vertices of the polyhedron have non-negative coordinates, that is, it lies entirely in the positive orthant.

property POSITIVE
$type="boolean";


# category: Basic properties
# Number of points.

property N_POINTS
$type="cardinal";

# category: Basic properties
# Number of inequalities.

property N_INEQUALITIES
$type="cardinal";


# category: Combinatorics
# Number of vertices.

property N_VERTICES
$type="cardinal";


# category: Combinatorics
# Number of bounded vertices (non-rays).

property N_BOUNDED_VERTICES
$type="cardinal";


# category: Combinatorics
# Number of facets.

property N_FACETS
$type="cardinal";


# category: Combinatorics
# Number of pairs of incident vertices and facets.

property N_VERTEX_FACET_INC
$type="cardinal";


# category: Combinatorics
# Vertex-facet incidence matrix, with rows corresponding to facets and columns
# to vertices. Vertices and facets are numbered from 0 to @see N_VERTICES-1 rsp.
# @see N_FACETS-1, according to their order in @see VERTICES rsp. @see FACETS.

property VERTICES_IN_FACETS
$type="incidence_matrix";
$apply_diff{VERTICES}=\&permute_cols;
$apply_diff{FACETS}=\&permute_rows;


# category: Convex hull computation
# Similar to @see VERTICES_IN_FACETS, but with columns corresponding to @see POINTS instead of @see VERTICES.
# This property is a byproduct of convex hull computation algorithms.
# It is discarded as soon as VERTICES_IN_FACETS is computed.

property POINTS_IN_FACETS
$type="incidence_matrix";
$apply_diff{FACETS}=\&permute_rows;


# category: Combinatorics
# transposed @see VERTICES_IN_FACETS

property FACETS_THRU_VERTICES
$type="incidence_matrix";
$temporary=1;


# category: Convex hull computation
# Similar to @see VERTICES_IN_FACETS, but with rows corresponding to @see INEQUALITIES instead of @see FACETS.
# This property is a byproduct of convex hull computation algorithms.
# It is discarded as soon as VERTICES_IN_FACETS is computed.

property VERTICES_IN_INEQUALITIES
$type="incidence_matrix";
$apply_diff{VERTICES}=\&permute_cols;


# category: Combinatorics
# The face lattice of the polytope organized as a directed graph.
# Each node corresponds to some proper face of the polytope.
# The nodes corresponding to the vertices and facets appear in the same order
# as the elements of @see VERTICES and @see FACETS properties.
#
# Two special nodes represent the whole polytope and the empty face.

property HASSE_DIAGRAM
$type="face_lattice";
$apply_diff{VERTICES}=
$apply_diff{FACETS}=
sub { die "update of HASSE_DIAGRAM too complicated\n" };
@upgrade=(
   v2.0,
   sub {
      my ($value)=@_;
      $value->[1] =~ s/^(?!\s*<)/</;
      push @$value, ">\n";
      return $value;
   }
);


# category: Combinatorics
# Number of incident facets for each vertex.

property VERTEX_SIZES
$type="array<cardinal>";
$apply_diff{VERTICES}=\&permute_elements;


# category: Combinatorics
# Number of incident vertices for each facet.

property FACET_SIZES
$type="array<cardinal>";
$apply_diff{FACETS}=\&permute_elements;


# category: Combinatorics
# Vertex-edge graph.

property GRAPH
$type="graph";
$apply_diff{VERTICES}=\&permute_rows_cols;


# category: Combinatorics
# Facet-ridge graph. Dual to @see GRAPH.

property DUAL_GRAPH
$type="graph";
$apply_diff{FACETS}=\&permute_rows_cols;


# category: Combinatorics
# Number of edges.

property N_EDGES
$type="cardinal";


# category: Combinatorics
# Number of ridges.

property N_RIDGES
$type="cardinal";


# category: Combinatorics
# Degrees of vertices in the @see GRAPH.

property VERTEX_DEGREES
$type="array<cardinal>";
$apply_diff{VERTICES}=\&permute_elements;


# category: Combinatorics
# Degrees of facets in the @see DUAL_GRAPH.

property FACET_DEGREES
$type="array<cardinal>";
$apply_diff{FACETS}=\&permute_elements;


# category: Combinatorics
# Lists for each occurring size (= number of incident vertices or edges) of a 2-face how many there are.

property TWO_FACE_SIZES
$type="array< tuple<cardinal,cardinal> >";


# category: Combinatorics
# Lists for each occurring size (= number of incident facets or ridges) of a subridge how many there are.

property SUBRIDGE_SIZES
$type="array< tuple<cardinal,cardinal> >";


# category: Combinatorics
# Graph theoretical diameter of @see GRAPH.

property DIAMETER
$type="cardinal";


# category: Combinatorics
# Graph theoretical diameter of @see DUAL_GRAPH.

property DUAL_DIAMETER
$type="cardinal";


# category: Combinatorics
# True if @see GRAPH does not contain a triangle.

property TRIANGLE_FREE
$type="boolean";


# category: Combinatorics
# True if @see DUAL_GRAPH does not contain a triangle.

property DUAL_TRIANGLE_FREE
$type="boolean";


# category: Combinatorics
# Let `M` be the vertex-facet incidence matrix, then the Altshulter determinant is
# defined as max{det(`M`&lowast;`M^T`), det(`M^T`&lowast;`M`)}.

property ALTSHULER_DET
$type="cardinal";


# category: Combinatorics
# `f_k` is the number of `k`-faces.

property F_VECTOR
$type="vector<cardinal>";


# category: Combinatorics
# `f_ik` is the number of incident pairs of `i`-faces and `k`-faces; the main diagonal contains the @see F_VECTOR.

property F2_VECTOR
$type="matrix<cardinal>";


# category: Combinatorics
# All intermediate polytopes (with respect to the given insertion order) in the beneath-and-beyond algorithm are simplicial.
# We have the implications: @see VERTICES in general position => ESSENTIALLY_GENERIC => @see SIMPLICIAL

property ESSENTIALLY_GENERIC
$type="boolean";


# category: Combinatorics
# True if the polytope is simplicial.

property SIMPLICIAL
$type="boolean";


# category: Combinatorics
# True if the polytope is simple. Dual to @see SIMPLICIAL.

property SIMPLE
$type="boolean";


# category: Combinatorics
# True if the @see GRAPH of the polytope is bipartite.

property EVEN
$type="boolean";


# category: Combinatorics
# True if the @see DUAL_GRAPH of the polytope is bipartite. Dual to @see EVEN.

property DUAL_EVEN
$type="boolean";


# category: Combinatorics
# True if the polytope is self-dual.

property SELF_DUAL
$type="boolean";


# category: Topology
# Difference of the black and white nodes if the @see GRAPH is @see BIPARTITE.
# Otherwise -1.
#
property GRAPH_SIGNATURE
$type="integer";


# category: Topology
# Differenz of the black and white nodes if the @see DUAL_GRAPH is @see BIPARTITE.
# Otherwise -1.
#
property DUAL_GRAPH_SIGNATURE
$type="integer";


# category: Combinatorics
# Node connectivity of the @see GRAPH of the polytope, that is, the minimal number of nodes to be removed
# from the graph such that the result is disconnected.

property CONNECTIVITY
$type="cardinal";


# category: Combinatorics
# Node connectivity of the @see DUAL_GRAPH of the polytope. Dual to @see CONNECTIVITY.

property DUAL_CONNECTIVITY
$type="cardinal";


# category: Combinatorics
# Maximal dimension in which all faces are simplices.

property SIMPLICIALITY
$type="cardinal";


# category: Combinatorics
# Maximal dimension in which all dual faces are simplices.

property SIMPLICITY
$type="cardinal";


# category: Combinatorics
# Maximal dimension in which all faces are simple polytopes.

property FACE_SIMPLICITY
$type="cardinal";


# category: Combinatorics
# True if all facets are cubes.

property CUBICAL
$type="boolean";


# category: Combinatorics
# Maximal dimension in which all facets are cubes.

property CUBICALITY
$type="cardinal";


# category: Combinatorics
# Dual to @see CUBICAL.

property COCUBICAL
$type="boolean";


# category: Combinatorics
# Dual to @see CUBICALITY.

property COCUBICALITY
$type="cardinal";


# category: Combinatorics
# True if the polytope is neighborly.

property NEIGHBORLY
$type="boolean";


# category: Combinatorics
# Maximal dimension in which all facets are neighborly.

property NEIGHBORLINESS
$type="cardinal";


# category: Combinatorics
# Dual to @see NEIGHBORLY.

property BALANCED
$type="boolean";


# category: Combinatorics
# Maximal dimension in which all facets are balanced.

property BALANCE
$type="cardinal";


# category: Combinatorics
# Parameter describing the shape of the face-lattice of a 4-polytope.

property FATNESS
$type="scalar";


# category: Combinatorics
# Parameter describing the shape of the face-lattice of a 4-polytope.

property COMPLEXITY
$type="scalar";


# category: Basic properties
# The center of gravity of the vertices of a bounded polytope.

property VERTEX_BARYCENTER
$type="vector";


# category: Basic properties
# The minimum angle between any two vertices (seen from the @see VERTEX_BARYCENTER).

property MINIMAL_VERTEX_ANGLE
$type="scalar";


# category: Basic properties
# Contains the vector configuration for which a @see zonotope can be built.

property ZONOTOPE_INPUT_VECTORS
$type="matrix";


# topic: $this/properties/Triangulation and volume
# Everything in this group is defined for @see BOUNDED polytopes only.


# category: Triangulation and volume
# Volume of the polytope.

property VOLUME
$type="scalar";


# Centroid (center of mass) of the polytope.

property CENTROID
$type="vector";


# category: Triangulation and volume
# Some triangulation of the polytope using only its vertices.
# Each line contains indices from @see VERTICES comprising a simplex.

property TRIANGULATION
$type="array<set>";
$apply_diff{VERTICES}=\&permute_cols;


# category: Triangulation and volume
# Similar to @see TRIANGULATION, but using @see POINTS.

property TRIANGULATION_INT
$type="array<set>";


# category: Triangulation and volume
# Intersection of @see TRIANGULATION with polytope boundary.
# Each line describes the triangulation of the corresponding facet as a list of simplices.

property TRIANGULATION_BOUNDARY
$type="array<powerset>";
$apply_diff{VERTICES}=\&permute_sets;
$apply_diff{FACETS}=\&permute_rows;


# category: Triangulation and volume
# For each simplex in @see TRIANGULATION, contains the sign of determinant of its coordinate matrix,
# telling about its orientation.

property TRIANGULATION_SIGNS
$type="vector<integer>";
$temporary=1;


# category: Triangulation and volume
# Similar to @see TRIANGULATION_SIGNS, but relates to @see TRIANGULATION_INT.

property TRIANGULATION_INT_SIGNS
$type="vector<integer>";
$temporary=1;

# category: Triangulation and volume
# Weight vector to construct a regular @see TRIANGULATION.

property WEIGHTS
$type=vector;




### category: Combinatorics
### Minimal non-faces of a @see SIMPLICIAL polytope.
###
###property MINIMAL_NON_FACES
###$type="array<set>";
###$apply_diff{vertex_permutation}=\&permute_cols;


# category: Visualization
# Reordered @see VERTICES_IN_FACETS for 2-d and 3-d polytopes.
# Vertices are listed in the order of their appearance
# when traversing the facet border counterclockwise seen from outside of the polytope.
#
# For a 2-d polytope (which is a closed polygon), lists all vertices in the border traversing order.

property VIF_CYCLIC_NORMAL
$type="array< list<cardinal> >";
$temporary=1;


# category: Visualization
# Reordered @see DUAL_GRAPH for 3-d polytopes.
# The neighbor facets are listed in the order corresponding to @see VIF_CYCLIC_NORMAL,
# so that the first two vertices in VIF_CYCLIC_NORMAL make up the ridge to the first neighbor
# facet and so on.

property NEIGHBOR_FACETS_CYCLIC_NORMAL
$type="array< list<cardinal> >";
$temporary=1;


# category: Visualization
# Reordered transposed @see VERTICES_IN_FACETS. Dual to @see VIF_CYCLIC_NORMAL.

property FTV_CYCLIC_NORMAL
$type="array< list<cardinal> >";
$temporary=1;


# category: Visualization
# Reordered @see GRAPH. Dual to @see NEIGHBOR_FACETS_CYCLIC_NORMAL.

property NEIGHBOR_VERTICES_CYCLIC_NORMAL
$type="array< list<cardinal> >";
$temporary=1;


# category: Basic properties
# Some invertible linear transformation that can be used to get back a previous coordinate repersentation of the polytope.
# It operates from the right on point row vectors (e.g. in properties like @see POINTS, @see VERTICES, @see REL_INT_POINT);
# its inverse operates from the left on hyperplane column vectors.

property REVERSE_TRANSFORMATION
$type="matrix";


# category: Basic properties
# Unique names assigned to the @see VERTICES.
# If specified, they are shown by visualization tools instead of vertex indices.
#
# For a polytope build from scratch, you should create this property by yourself,
# either manually in a text editor, or with a client program. If you build a polytope with a construction client
# taking some other input polytope(s), you can create the labels automatically if you
# call the client with a @c -relabel option. The exact format of the labels is dependent on the
# construction, and is described by the corresponding client.

property VERTEX_LABELS
$type="array<label>";
$apply_diff{VERTICES}=\&permute_elements;


# category: Basic properties
# Unique names assigned to the @see FACETS, analogous to @see VERTEX_LABELS.

property FACET_LABELS
$type="array<label>";
$apply_diff{FACETS}=\&permute_elements;


# category: Lattice polytopes
# This is the defining property: A polytope is lattice if each vertex has integer coordinates.

property LATTICE
$type="boolean";


# Category: 0/1-polytopes
# Number of points with 0/1-coordinates in a polytope.

property N_01POINTS
$type="cardinal";

# The splits of the polytope, i.e. hyperplanes cutting the polytope in
# two parts such that we have a regular subdivision.

property SPLITS
$type="matrix";

# Local Variables:
# c-basic-offset:3
# mode: perl
# End: