BigObject PropagatedPolytope<Scalar>

from application polytope

Polytope propagation means to define a polytope inductively by assigning vectors to arcs of a directed graph. At each node of such a graph a polytope arises as the joint convex hull of the polytopes at the translated sources of the inward pointing arcs. For details see

Joswig: Polytope Propagation on Graphs.
Chapter 6 in Pachter/Sturmfels: Algebraic Statistics for Computational Biology, Cambridge 2005.

Type Parameters:

Scalar: numeric data type used for the coordinates, must be an ordered field. Default is Rational.

derived from:

Polytope

Example:

We define an acyclic digraph on 8 nodes with a unique source and a unique sink. Each arc is equipped with a vector in Q^2.

 > $Gamma = new GraphAdjacency<Directed>(8);
 > $Vectors = new EdgeMap<Directed, Vector>($Gamma);
 > $Vectors->edge(0,1) = [1,0]; $Vectors->edge(0,2) = [0,0];
 > $Vectors->edge(1,3) = [1,0]; $Vectors->edge(1,4) = [0,1];
 > $Vectors->edge(2,3) = [0,0]; $Vectors->edge(2,4) = [0,2];
 > $Vectors->edge(3,5) = [1,0]; $Vectors->edge(3,6) = [0,1];
 > $Vectors->edge(4,5) = [0,0]; $Vectors->edge(4,6) = [0,2];
 > $Vectors->edge(5,7) = [0,0];
 > $Vectors->edge(6,7) = [0,0];

Then we can define the propagated polytope implicitly:

 > $P = new PropagatedPolytope(CONE_AMBIENT_DIM=>3, "SUM_PRODUCT_GRAPH.ADJACENCY"=>$Gamma, "SUM_PRODUCT_GRAPH.TRANSLATIONS"=>$Vectors);
 > print $P->VERTICES;
 1 3 0
 1 1 0
 1 0 1
 1 1 3
 1 0 4

Note that it is necessary to specify the dimension of the (homogeneous) ambient space by setting CONE_AMBIENT_DIM.

SUM_PRODUCT_GRAPH

Type:

Graph<Directed>

Properties of SUM_PRODUCT_GRAPH:

TRANSLATIONS

The translation vectors of the arcs.

Type:

EdgeMap<Directed,Vector<Scalar>>