There are various means to obtain new objects without having to type the data in a new file manually. Application polytope defines many standard construction and transformation algorithms. Unfortunately, due to the preliminary state of polymake reconstruction, we can't supply a uniform, comfortable function-like interface to all of them. At the moment you still have to call the construction clients as separate programs from the shell command line.

Producing from scratch

With these clients you can create polytopes belonging to various parameterized families which occur frequently in polytope theory, as well as random polytopes with different models of randomness.

rand01 <file> <d> <n> [ -seed <s> ]
Produce a d-dimensional 0/1-polytope with n random vertices. Uniform distribution.
cross <file> <d> [<scale>]
Produce a d-dimensional cross polytope. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.
scale must be positive. All coordinates are +/- scale or 0.
dwarfed_product_polygons <file> <dim> <size>
Produce an even dimensional dwarfed product of polygons.
permutahedron <file> <d>
Produce the d-permutahedron. The vertices correspond to the elements of the symmetric group of degree d+1.
multiplex <file> <d> <n>
Produce a combinatorial description of a multiplex with parameters (d,n). This yields a self-dual d-dimensional polytope with n+1 vertices. They are introduced by T. Bisztriczky [On a class of generalized simplices, Mathematika 43:27-285, 1996], see also Bayer et al.
[M.M. Bayer, A.M. Bruening, and J.D. Stewart:
A combinatorial study of multiplexes and ordinary polytopes,
Discrete Comput. Geom. 27(1):49--63, 2002].
Originally contributed by Alexander Schwartz
rand_sphere <file> <dimension> <n> [ -precision <digits> ] [ -seed <s> ]
Produce a d-dimensional polytope with n random vertices on the unit sphere. Floating-point coordinates are used. Uniform distribution.
The default precision is set to 6 digits.
neighborly_cubical <file> <d> <n>
Produce the combinatorial description of a neighborly cubical polytope. The facets are labelled in oriented matroid notation as in the cubical Gale evenness criterion. See Joswig and Ziegler, Discr. Comput. Geom. 24:315-344 (2000).
d is the dimension of the polytope to be built, n is the dimension of the equivalent cube.
k_cyclic <file> <k> <n> <s_1> ... <s_k>
Produce a (rounded) 2*k-dimensional k-cyclic polytope with n points. Special cases are the bicyclic (k=2) and tricyclic (k=3) polytopes. Only possible in even dimensions.
The parameters si can be specified as integer, floating-point, or rational numbers. The coordinates of the i-th point are taken as follows:
cos(s1 * 2πi/n), sin(s1 * 2πi/n), ... cos(sk * 2πi/n), sin(sk * 2πi/n)
Warning: Some of the k-cyclic polytopes are not simplicial.
Since the components are rounded, this client might
output a polytope which is not a k-cyclic polytope!
More information can be found in the following references:
P. Schuchert: "Matroid-Polytope und Einbettungen kombinatorischer Mannigfaltigkeiten", PhD thesis, TU Darmstadt, 1995.
Z. Smilansky: "Bi-cyclic 4-polytopes", Isr. J. Math. 70, 1990, 82-92
24-cell <file>
Produce a polymake description of the 24-cell.
cyclic <file> <d> <n> [<x start value>]
Produce a d-dimensional cyclic polytope with n points. Prototypical example of a neighborly polytope. Combinatorics completely known due to Gale's evenness criterion. Coordinates are chosen on the moment curve.
cyclic_caratheodory <file> <d> <n>
Produce a d-dimensional cyclic polytope with n points. Prototypical example of a neighborly polytope. Combinatorics completely known due to Gale's evenness criterion. Coordinates are chosen on the trigonometric moment curve.
d must be even; n > d
simplex <file> <d> [<scale>]
Produce the standard d-simplex. Combinatorially equivalent to regular polytope corresponding to the Coxeter group of type Ad-1.
associahedron <file> <d>
Produce a d-dimensional associahedron (or Stasheff polytope). We use the facet description given in Ziegler's book on polytopes, section 9.2.
cube <file> <d> [<scale>]
Produce a d-dimensional cube. Regular polytope corresponding to the Coxeter group of type Bd-1 = Cd-1.
If scale is non-zero, then all coordinates are +/- scale. If scale is zero, then all coordinates are 0/1. Default is scale=1.
dwarfed_cube <file> <d>
Produce a d-dimensional dwarfed-cube.
hypersimplex <file> <d> [<k>]
Produce the hypersimplex Δd(k). The value of k defaults to 1, yielding a simplex. Note that the output is never full-dimensional.
n-gon <file> <n> [r]
Produce a regular n-gon.
All vertices lie on a circle of radius r. The radius defaults to 1.
pile <file> <d> <factor_1> .. <factor_d>
Produce a (d+1)-dimensional polytope from a pile of cubes. Start with a d-dimensional pile of cubes. Take a generic convex function to lift this polytopal complex to the boundary of a (d+1)-polytope.
factor_i gives the number of boxes in the i-th dimension.
Goldfarb <file> <d> [<e>] [<g>]
Produces a d-dimensional Goldfarb cube if e<1/2 and g<=1/4e. The Goldfarb cube is a combinatorial cube and yields a bad example for the Simplex Algorithm using the Shadow Vertex Pivoting Strategy. Here we use the description as a deformed product due to Amenta and Ziegler. For e<1/2 and g=0 we obtain the Klee-Minty cubes.
Responsible author: Niko Witte
600-cell <file>
Produce a polymake description of the 600-cell. Cf. Coxeter, Introduction to Geometry, pp 403-404.
birkhoff <file> <n> [ -even ]
Constructs a VERY INTERESTING polytope.

Producing a new polyhedron from others

Another important way of constructing polytopes is to modify an already existing polytope.

Actually, these clients don't alter the input polytope (it is forbidden in polymake), but create a new polytope object (file).

Many clients can at your choice either calculate the vertex or facet coordinates, or constrain themselves on the purely combinatorial description of the resulting polytope.

rand <outfile> <infile> <n> [ -seed <s> ]
Produce a polytope with n random points from the input polytope.
Each generated point is a convex linear combination of the input vertices with uniformly distributed random coefficients. Thus, the output points can't in general be expected to be distributed uniformly within the input polytope; cf. unirand for this.
A seed value for the random number generator can be specified.
Originally contributed by Carsten Jackisch
product <output_file> <input_file_1> <input_file_2> [ -noc ] [ -relabel ]
Construct a new polytope as the product of two given ones. Unbounded polyhedra are not allowed.
If the option -noc (no coordinates) is set, only combinatorial information is handled.
The option -relabel creates an additional section VERTEX_LABELS. The label of a new vertex corresponding to v1 ⊕ v2 will have the form "LABEL1*LABEL2".
truncation <output_file> <input_file> { <vertex> [ <vertex> ... ] | all } [ -cutoff <cf> | -noc ] [ -relabel ]
Cut off one or more vertices of a polyhedron.
vertex is the number of the vertex to be cut off. The keyword all means all vertices of the original polyhedron.
Parameter cf controls the exact location of the cutting hyperplane(s). It should be a rational number from (0,1]. When cf=0, the hyperplane would go through the chosen vertex, thus cutting off nothing. When cf=1, the hyperplane touches the nearest neighbor vertex of a polyhedron. Default value for cf is 1/2.
Alternatively, the option -noc (no coordinates) can be specified to produce a pure combinatorial description of the resulting polytope, which would correspond to the cutoff factor 1/2.
The option -relabel creates an additional section VERTEX_LABELS. New vertices get labels of the form 'LABEL1-LABEL2', where LABEL1 is the original label of the truncated vertex, and LABEL2 is the original label of its neighbor.
Originally contributed by Kerstin Fritzsche
intersection <output_file> <input_file_1> <input_file_2> [ ... ]
Construct a new polyhedron as the intersection of given polyhedra.
bipyramid <output_file> <input_file> [ <z> [ <z'> ] | -noc ] [ -relabel ]
Make a bipyramid over a polyhedron. The bipyramid is the convex hull of the input polyhedron P and two points v, v' on both sides of the affine span of P. For bounded polyhedra, the projections of v and v' to the affine span of P coincide with the vertex barycenter of P.
z and z' are distances between the vertex barycenter and v and v' respectively. Default values are z=1 and z'=-z.
If the option -noc (no coordinates) is set, then only combinatorial information is handled.
The option -relabel creates an additional section VERTEX_LABELS. The vertices from the original polytope keep their labels; the new vertices are labeled "Apex" and "Apex'".
edge_middle <output_file> <input_file>
Produce the convex hull of all edge middle points of some polytope. The polytope must be bounded.
spherize <output_file> <input_file>
Project all vertices of a polyhedron on the unit sphere. Input polyhedron must be centered.
conv <output_file> <input_file_1> <input_file_2> [ ... ]
Construct a new polyhedron as the convex hull of given polyhedra.
pyramid <output_file> <input_file> [ <z> | -noc ] [ -relabel ]
Make a pyramid over a polyhedron. The pyramid is the convex hull of the input polyhedron P and a point v outside the affine span of P. For bounded polyhedra, the projection of v to the affine span of P coincides with the vertex barycenter of P.
z is the distance between the vertex barycenter and v, default value is 1.
If the option -noc (no coordinates) is set, then only combinatorial information is handled.
The option -relabel creates an additional section VERTEX_LABELS. The vertices from the original polytope keep their labels; the new top vertex is labeled "Apex".
vertex_figure <output_file> <input_file> <n> [ -cutoff <cf> | -noc ] [ -relabel ]
Construct the vertex figure of the vertex n of a polyhedron The vertex figure is dual to a facet of the dual polytope.
n is the number of the chosen vertex
Parameter cf controls the exact location of the cutting hyperplane. It should be a rational number from (0,1). By cf=0, the hyperplane would go through the chosen vertex, thus degenerating the vertex figure to a single point. By cf=1, the hyperplane would touch the nearest neighbor vertex of a polyhedron. Default value for cf is 1/2.
Alternatively, the option -noc (no coordinates) can be specified to produce a pure combinatorial description.
The option -relabel creates an additional section VERTEX_LABELS. The vertices inherit the labels from the corresponding neighbor vertices of the original polytope.
prism <output_file> <input_file> [ <z> [ <z'> ] | -noc ] [ -relabel ]
Make a prism over a polytope. The prism is the product of the input polytope and the interval [z,z']. The default interval is [0,1]. If z != 0, then z' defaults to -z.
If the option -noc (no coordinates) is set, then only combinatorial information is handled. The input polytope is assumed to be bounded.
The option -relabel creates an additional section VERTEX_LABELS. The bottom facet vertices get the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended.
wreath <output_file> <input_file_1> <input_file_2> {-primal, -dual} [ -relabel ]
Construct a new polytope as the wreath product of two given ones. Unbounded polyhedra are not allowed.
The option -relabel creates an additional section VERTEX_LABELS. The label of a new vertex corresponding to v1 ⊕ v2 will have the form "v1*v2".
mapping_polytope <output_file> <input_file_1> <input_file_2> [ -relabel ]
Construct a new polytope as the mapping polytope of two polytopes P and Q. The mapping polytope is the set of all affine maps from Rp to Rq, that map P into Q.
The label of a new facet corresponding to v1 and h1 will have the form "v1*h1".
wedge <output_file> <input_file> <facet> [ <z> [ <z'> ] | -noc ] [ -relabel ]
Make a wedge from a polytope over its facet.
facet is the number of the `cutting edge' facet. The inclination of the bottom and top side facet is controlled by z and z' paremeters, where z is the height of the projection of the old vertex barycenter on the bottom side facet, and z' - on the top one.
Default heights are [0,1]; if only z is specified and non-zero, then z' defaults to -z.
The polytope must be bounded.
If the option -noc (no coordinates) is set, then only combinatorial information is handled.
The option -relabel creates an additional section VERTEX_LABELS. The bottom facet vertices get the labels from the original polytope; the labels of their clones in the top facet get a tick (') appended.
Originally contributed by Kerstin Fritzsche
blending <output_file> <input_file1> <vertex1> <input_file2> <vertex2> [ -relabel ] [ <permutation> ]
Compute the blending of two polyhedra at simple vertices. This is a slightly less standard construction. A vertex is simple if its vertex figure is a simplex.
Moving a vertex v of a bounded polytope to infinity yields an unbounded polyhedron with all edges through v becoming mutually parallel rays. Do this to both input polytopes P and P' at simple vertices v and v', respectively. Up to an affine transformation one can assume that the orthogonal projections of P and P' in direction v and v', respectively, are mutually congruent.
Any bijection b from the set of edges through v to the edges through v' uniquely defines a way of glueing the unbounded polyhedra to obtain a new bounded polytope, the blending with respect to b. The bijection is specified as a permutation of indices 0 1 2 etc. Default permutation is identity.
The number of vertices of the blending is the sum of the numbers of vertices of the input polytopes minus 2. The number of facets is the sum of the numbers of facets of the input polytopes minus the dimension.
The resulting polytope is described only combinatorially.
Originally contributed by Kerstin Fritzsche
rand_vert <output_file> <input_file> <n> [ <seed> ]
Produce a polytope with n random vertices from input polytope.
This can be used to produce random polytopes which are neither simple nor simplicial as follows. First produce a simple polytope (for instance at random, by using rand_sphere, rand, or unirand). Then use this client to choose among the vertices at random. Generalizes random 0/1-polytopes.
A seed value for the random number generator can be specified.
facet <output_file> <input_file> <n> [ -noc ] [ -relabel ]
Extract the given facet of a polyhedron and write it as a new polyhedron. n is the number of the chosen facet.
If the option -noc (no coordinates) is specified, only combinatorial description is produced.
The option -relabel creates an additional section VERTEX_LABELS. The vertices belonging to the extracted facet keep their labels from the original polytope.
stellar_indep_faces <out_file> <in_file> <faces_section>
Perform a stellar subdivision of the given faces.
The faces must have the following property: The open vertex stars of any pair of faces must be disjoint.
Responsible author: Nikolaus Witte
cayley_embedding <output_file> <input_file1> <input_file2> [ <z> [ <z'> ] ] [ -relabel ]
Create a Cayley embedding of two polytopes. The vertices of the first polytope get an extra coordinate z, and the vertices of the second one get z'.
Default values are z=1 and z'=-z.
The option -relabel creates an additional section VERTEX_LABELS. The vertices of the first polytope inherit the original labels unchanged; the vertex labels from the second polytope get a tick (') appended.
stack <output_file> <input_file> { <facet> [ <facet> ... ] | all } [ -lift <lf> | -noc ] [ -relabel ]
Stack a (simplicial or cubical) polytope over one or more of its facets.
For each specified facet, the barycenter of its vertices is lifted along the normal vector of the facet. In the simplicial case, this point is directly added to the vertex set, thus building a pyramid over the facet. In the cubical case, this pyramid is truncated by a hyperplane parallel to the original facet at its half height. This way, the property of being simplicial or cubical is preserved in both cases.
The keyword all means all facets of the original polytope.
Parameter lf controls the exact coordinates of the new vertices. It should be a rational number between 0 and 1, which expresses the ratio of the distance between the new vertex and the stacked facet, to the maximal possible distance. When lf=0, the new vertex would lie on the original facet. lf=1 corresponds to the opposite extremal case, where the new vertex hit the hyperplane of some neighbor facet. As an additional restriction, the new vertex can't lie further from the facet as the vertex barycenter of the whole polytope. Default value for lf is 1/2.
Alternatively, the option -noc (no coordinates) can be specified to produce a pure combinatorial description of the resulting polytope.
The option -relabel creates an additional section VERTEX_LABELS. New vertices get labels 'f(FACET_LABEL)' in the simplicial case, and 'f(FACET_LABEL)-NEIGHBOR_VERTEX_LABEL' in the cubical case.
p_proj <output_file> <input_file> [-] [ <k1> [ <k2> ... ] ] [-nofm]
Orthogonally project a polyhedron to a coordinate subspace.
The subspace the polyhedron is projected on is given by the coordinate indices ki. The dash argument inverts the coordinate list. If no coordinates are specified the polytope is projected by omitting "redundant" columns, i.e., the projection becomes full-dimensional without changing the combinatorial type.
The client scans for all coordinate sections and produces proper output from each. If a description in terms of inequalities is found, the client performs Fourier-Motzkin elimination unless the -nofm option is set. Setting the -nofm option is useful if the corank of the projection is large; in this case the number of inequalities produced grows quickly.
stellar_all_faces <out_file> <in_file> [ <d> ]
Perform a stellar subdivision of all proper faces, starting with the facets.
Parameter d specifies the lowest dimension of the faces to be divided. It can also be negative, then treated as the co-dimension. Default is 1, that is, the edges of the polytope.
Responsible author: Nikolaus Witte
minkowski_sum <output_file> <scalar1> <infile1> <scalar2> <infile2>
Produces the polytope lambda*P+mu*Q, where * and + are scalar multiplication and Minkowski addition, respectively.
unirand <output_file> <input_file> <n> [-seed <seed> ] [-boundary]
Produce a polytope with n random points. Points are uniformly distributed within the given polytope, which must be full-dimensional.
If -boundary option is used, generated points will lie on the boundary of the given polytope.

Transforming a polyhedron

These clients take a realized polytope and produce a new one by applying a suitable affine or projective transformation in order to obtain some special coordinate description but preserve the combinatorial type.

For example, before you can polarize an arbitrary polyhedron, it must be transformed to a combinatorially equivalent bounded polytope with the origin as a relatively interior point. It is achieved with the sequence orthantify - p_bound - center - polarize.

p_bound <output_file> <input_file>
Make a positive polyhedron bounded. Apply a projective linear transformation to a polyhedron mapping the far hyperplane to the hyperplane spanned by the points (1,0,...,0,1,0,...). The origin (1,0,...,0) is fixed.
The input polyhedron should be positive; i.e. no non-negative coordinates.
orthantify <output_file> <input_file> [ origin ]
Make a polyhedron POSITIVE. Apply an affine transformation to a polyhedron such that a vertex is mapped to the origin (1,0,...,0) and as many facets through this vertex as possible are mapped to the bounding facets of the first orthant.
origin is the number of the vertex that will be moved to the origin (1,0,...,0). Default is the first affine vertex of the polyhedron. -----
Make a polyhedron POSITIVE. Apply an affine transformation to a polyhedron such that a vertex is mapped to the origin (1,0,...,0) and as many facets through this vertex as possible are mapped to the bounding facets of the first orthant.
origin is the number of the vertex that will be moved to the origin (1,0,...,0). Default is the first affine vertex of the polyhedron.
revert <output_file> <input_file>
Apply a reverse transformation to a given polyhedron. All transformation clients keep track of the polytope's history. They write or update the section REVERSE_TRANSFORMATION.
Applying revert to the transformed polytope re-constructs the original polyhedron.
center <output_file> <input_file>
Make a polyhedron centered. Apply a linear transformation to a polyhedron such that a relatively interior point (preferably the vertex barycenter) is moved to the origin (1,0,...,0).
polarize <output_file> <input_file> [-noc]
Given a bounded, centered, and full-dimensional polytope P, produce its polar, that is, polar with respect to the standard Euclidean scalar product.
If the option -noc (no coordinates) is set, then only combinatorial information is handled.

Comparing polytopes

congruent_polytopes <file1> <file2> [ <factor_section> ]
Implements the reduction of polytope congruence to the graph isomorphism problem due to
Akutsu, T.: On determining the congruence of point sets in {d} dimensions.
Comput. Geom. Theory Appl. 9, 247--256 (1998), no. 4
Writes the scaling factor to the given result section. Zero means non-congruent polytopes. If no result section is specified, prints the scaling factor on the standard output.
Originally contributed by Alexander Schwartz

Combinatorics

toric_g_vector <file>
Calculate the toric g-vector and the (generalised) h-vector from the cd-index of a polytope. See
Richard Ehrenborg, Lifting inequalities for polytopes,
Adv.Math. 193 (2005), 205-222, section 4
Contributed by Axel Werner
flag_vector <file>
Calculate (the non-redundant part of) the flag vector of a polytope.
Contributed by Axel Werner
cd_index <file>
Calculate the cd-index from (the non-redundant part of) the flag vector of a polytope. See
Billera, Ehrenborg, Monotonicity of the cd-index for polytopes
Math.Z. 233 (2000), 421-441, section 7
Contributed by Axel Werner

Producing from given data

zonotope <file>
Produce a zonotope from given vectors. The zonotope is obtained as the iterated Minkowski sum of all intervals [-x,x], where x ranges over the rows of a given matrix.
zonotope_facets <file>
Produce a zonotope from given vectors. The zonotope is obtained as the iterated Minkowski sum of all intervals [-x,x], where x ranges over the rows of a given matrix. If the input vectors are in general position VERTICES and FACETS are written, otherwise POINTS and INEQUALITIES

Other

regular_triangulation <file>
Compute the regular triangulation of the polytope obtained by lifting the vertices to WEIGHTS and taking the lower complex of the resulting polytope.
Note that the output will not be a triangulation if the WEIGHTS are not generic. However, one then gets the polytopes of a regular subdivision.
Contributed by Sven Herrmann
steiner_point_all <file> [ -seed <s> ] [ -acc <eps> ]
Compute the Steiner points of all faces of a polytope using a randomized approximation of the angles.
eps is an accuracy parameter controlling the accuracy ( 10-eps ) of the angles computed. The s parameter may be set to initialize the random calculation of the angles.
Polytope must be bounded.
Responsible author: Thilo Rörig
steiner_point_graph <file> [ -seed <s> ] [ -acc <eps> ]
Compute the Steiner point of a polytope using a randomized approximation of the angles.
-acc is an accuracy parameter controlling the accuracy (10-eps ) of the angles computed. The -seed parameter may be set to initialize the random calculation of the angles.
Responsible author: Thilo Rörig
rand_aof <out_file> <in_file> [ <vertex> ] [ -seed <s> ]
Produce a random abstract objective function on a given simple polytope. It is assumed that the boundary complex of the dual polytope is extendibly shellable. If, during the computation, it turns out that a certain partial shelling cannot be extended, then this is given instead of an abstract objective function.
It is possible (but not required) to specify the starting vertex. Also a seed value for the random number generator may be given.

Tight Spans

poly2metric <metric file> <polytope file>
Define a metric by restricting the Euclidean distance function to the vertex set of a polytope. Due to floating point computations (sqrt is used) the metric defined may not be exact.
metric2poly <file>
Given a finite metric space (encoded as a symmetric distance matrix), produce an unbounded polyhedron whose bounded subcomplex is the tight span.
metric2hyp_triang <outfile> <infile>
Given a generic finite metric space, construct the associated (i.e. dual) triangulation of the hypersimplex. The newly created object is of type RationalPolytope.
Contributed by Sven Herrmann

Polytope Propagation

edge_directions <file> <graph_section> <edge_directed_graph_section> [-labeled]
Computes the edge directions of a graph. The option -labeled signals that the graph is a subgraph with suitable vertex labels.
sum-product <file>
Polytope propagation for polytopes. This is the actual core algorithm which makes the propagated polytope explicit.
binary-markov-graph <file> <n>
Defines a very simple graph for a polytope propagation related to a Hidden Markov Model. The propagated polytope is always a polygon. For a detailed description see M. Joswig: Polytope propagation, in: Algebraic statistics and computational biology by L. Pachter and B. Sturmfels (eds.), Cambridge, 2005.

Visualization

schlegel_params <file>
Store the parameters of the Schlegel diagram in the file.
facet is the index of the facet the polytope is projected on.
This client puts the viewpoint always on the ray joining the vertex barycenter of the polytope with the one of the chosen projection facet. Obviously, it should lie outside the polytope. On the other side, the ray crosses the hyperplanes of the neighbor facets. The viewpoint should lie closer to the projection facet than any of these crossing points; otherwise the diagram will not be a valid polytopal complex any more. However, in some rare cases all crossing points lie on the positive side of the projection facet; then the range of the valid viewpoint positions is open.
zoom controls the exact position of the viewpoint within the valid range. If specified, it should be a rational number between 0 and 1. The greater the zoom factor, the larger appear the rear facets in the diagram.
Defaults are the first facet (index 0) and zoom factor 9/10.

Consistency check

check_inc <file> <points_section> <hyperplanes_section> <sign>
Check the coordinate data of a polytope. For each pair of vectors from two given sections their inner product must satisfy the given relation.
sign is a string composed of one or two characters from [-+0], representing the allowed domain of the vector inner products.

Clients for internal use

These clients are called by polymake automatically via the rules. They compute some new properties of an object. You will hardly ever need to call them directly. They are documented here first of all for the sake of completeness.

triangle_free <file> <graph_section> <triangle_free_section>
Determine whether a (possibly directed) graph has triangles or not.
connected <file> <graph_section> <connected_section>
Determine whether an undirected graph is connected.
induced_subgraph <file> <graph_section> <subgraph_nodes_section> <subgraph_section> [ -nol ] [ -compl ]
Compute the subgraph induced by a given set of nodes.
The nodes are labeled with the original node indices, unless nol option is specified. If compl option is specified, the complement of the subgraph_nodes_section is used to select the subgraph nodes.
se_interactive <file> <port> [ -z-ordering <objective_section> -read-edge-weights -seed <s> -max-iterations <n> ] [ {-scale,-balance,-viscosity,-inertion,-eps,-z-factor} <x> ... ]
Driver for interactive graph visualization
greedy_coloring <file> <graph_section> <coloring_section>
Computes a coloring.
max_cliques <file> <max_cliques_section> <graph_section>
Computes all inclusion maximal cliques of a graph.
isomorphic_graphs <file1> <graph_section1> <file2> <graph_section2> [ <result_section> ]
Determine whether two given graphs are isomorphic.
The answer is written as a boolean property result_section of the first file. If the result section is omitted, prints the node permutation to the standard output.
connectivity <file> <graph_section> <connectivity_section>
Compute the connectivity of a given graph using the Ford-Fulkerson flow algorithm.
Responsible author: Nikolaus Witte
connected_comp <file> <graph_section> <connected_comp_section>
Computes the connected components. The connected components are encoded by their node sets.
hd_embedder <file> <hd_section> <embedding_section> <label_width_section> { -primal | -dual } [ -seed <s> -eps <x> ]
Create an embedding of the Hasse diagram as a layered graph.
The embedding algorithm tries to minimize the weighted sum of squares of edge lengths, starting from a random distribution. The weights are relative to the fatness of the layers.
The y-space between the layers is constant; in the -primal mode the whole-lattice node is placed on the top, in the -dual mode it is the empty node.
label_width_section should contain estimates (better upper bounds) of the label width of each node. The computed layout guarantees that the distances between the nodes in a layer are at least equal to the widest label in this layer.
-eps is the calculation accuracy.
option -seed effects the initial placement of the nodes.
bipartite <file> <graph_section> <bipartite_section> [ <signature_section> ]
Determine whether an undirected graph is bipartite.
Responsible author: Niko Witte
edge_lengths <file> <coords_section> <graph_section> <result_section> [ -redirect ]
Compute the lenghts of all edges of a given graph with assigned coordinates for the nodes. If the -redirect option is set then it is assumed that the graph has indices as node attributes which point into the coordinate section.
spring_embedder <file> <graph_section> <embedding_section> [ -z-ordering <objective_section> -read-edge-weights -seed <s> -max-iterations <n> ] [ {-scale,-balance,-viscosity,-inertion,-eps,-z-factor} <x> ... ]
Produce a 3-d embedding for the graph using the spring embedding algorithm along the lines of
Thomas Fruchtermann and Edward Reingold:
Graph Drawing by Force-directed Placement.
Software Practice and Experience Vol. 21, 1129-1164 (1992), no. 11
The initial node coordinates are chosen randomly on the unit sphere. The optional parameter -seed controls the initial setting.
In the standard setting, the embedding algorithm tries to stretch all edges to the same length. If you prefer different edge lengths, store them as the edge attributes of the input graph, and put the -read-edge-weights option on the command line.
If the nodes already have an embedding in Rd and there is a linear or abstract objective function defined in the coordinate space, it can be used to rearrange the 3-d embedding along the z-axis corresponding to the objective function growth. This mode is enabled with option -z-ordering.
The embedding algorithm can be fine-tuned with several "black magic" options. All of them take double values, which are multiplied with internal initial settings, so all defaults are equal to 1.
-scale enlarges the ideal edge length. -balance changes the balance between the edge contraction and node repulsion forces. -inertion and -viscosity affects how the nodes are moved, and can be used to restrain oscillations. -z-factor changes the relative influence of the objective function on the embedding. -eps controls how far a point may move, to be considered standing still.
diameter <file> <graph_section> <diameter_section>
Compute the diameter of an undirected graph.
vertex_colors <file> <vertices_section> <far_face_section> <min_r> <min_g> <min_b> <max_r> <max_g> <max_b> { -linear <lof_section> | -abstract <aof_section> }
Calculate RGB-color-values for each vertex depending on a linear or abstract objective function. Maximal and minimal affine vertices are colored as specified. Far vertices (= rays) orthogonal to the linear function normal vector are white. The colors for other affine vertices are linearly interpolated in the HSV color model.
If the objective function is linear and the corresponding LP problem is unbounded, then the affine vertices that would become optimal after the removal of the rays are painted pale.
triang_sign <file> <triangulation_section> <vertex_section> <sign_section>
For a given triangulation of a polytope, compute the orientation of the simplices. The output section contains signs of determinants of simplices.
projective_transformation <file> <output_section> <input_section> <transformation_section> [-dual]
Apply a projective linear transformation to a section.
expansive_motions <file>
Calculate the extreme rays of the cone of expansive motions and the corresponding motions and patterns for a given framework.
incidence <file> <row_section> <col_section> <incidence_section>
Compute the incidence matrix of two vector sets.
Rows of the incidence matrix correspond to the vectors of the first set, columns correspond to the second set. Vector sets are encoded as rows of a matrix.
Two vectors are considered incident if their scalar product is exactly zero.
vertex_barycenter <file>
Compute the vertex barycenter of a polytope. Polytope must be bounded.
hasse_diagram <file> <incidence_section>
Compute the HASSE_DIAGRAM of the polytope.
graph_from_incidence <file> <incidence_section> <mode>
Compute the vertex or facet graph of a polyhedron.
mode may be -primal or -dual
basis_compare <file> <output> <matrix1> <matrix2>
Given two full rank matrices, checks whether their rows are two basis of the same linear subspace
compress_incidence <file> { -primal, -dual }
Detect the vertices (dually: facets) among the given points (dually: inequalities). Used as postprocessing after the convex hull computation.
facets_from_incidence <file> { -primal, -dual }
Compute the facet description of a polyhedron from its vertices and its incidence matrix.
isomorphic_polytopes <file1> { <file2> | -self-dual } [ <result_section> ]
Determine whether two given polytopes are combinatorially isomorphic. If the second argument is -self-dual, checks the first polytope for being isomorphic to its own dual.
The answer is written as a boolean property result_section of the first file. If the result section is omitted, prints the vertex and facet permutations to the standard output.
splits
Computes the SPLITS of a polytope, i. e. those hyperplanes which cut the polytope in two parts such that one gets a subdivision without new vertices. The splits are normalized by dividing by the first non-zero entry.
If the polytope is not fulldimensional the first entries are set two zero, however by additionally giving a section with a set of integers one forces the program to set these entries to zero.
Contributed by Sven Herrmann
inner_point <file> <matrix_section> <inner_point_section>
Compute a true inner point of a convex hull of the given set of points
nullspace <file> <matrix_section> <nullspace_section>
Compute the basis of the orthogonal complement to the row space of a given matrix.
voronoi <file> <ineq_section> <sites_section>
Compute the Voronoi polyhedron of a given set of points. The polyhedron is unbounded. Introduce artificial cut facets later (e.g., for visualization); this must be done after the vertex have been computed.
schlegel_interactive <SchlegelDiagram> ... <Polytope> <fd> <points_in> ...
Driver for interactive Schlegel diagram visualization.
The first section in points_in must be VERTICES
is_lattice <file> <vertices_section> <is_lattice_section>
Determine if all points in a coordinate matrix are integral.
revert_section <out_file> <in_file> { -primal | -dual } <section>
Apply a reverse transformation some section of a polyhedron. All transformation clients keep track of the polytope's history. They write or update the section REVERSE_TRANSFORMATION.
Only one section in the input polyhedron is reverted and written in the output polyhedron. The parameters "-primal" and "-dual" state if the section contains point-like or hyperplane-like content.
h_vector <file> { SIMPLICIAL,SIMPLE }
Compute the h-vector of a simplicial or simple polytope from the f-vector.
f2_vector <file>
Compute the f_vector and f2_vector of a polytope.
graph_from_face_lattice <file> <mode>
Compute the vertex or facet graph of a polyhedron from its face lattice.
mode may be -primal or -dual
cubical_h_vector <file> { CUBICAL, COCUBICAL }
Compute the cubical h-vector of a cubical or cocubical polytope from the f-vector as defined in "A New Cubical h-Vector" by Ron M. Adin in 1995.
altshuler_det <file>
Calculate the Altshuler Determinant of a polytope.
2-face-sizes-simple <file> { -primal | -dual }
Compute the sizes of all 2-faces of a simple polytope. Since this algorithm does not require the complete face lattice, it is much faster than the standard client @see 2-face-sizes.
beneath_beyond <file> <points_section> [ <vertex_permutation_section> ]
Compute the convex hull and the triangulation of the given point set using the beneath-beyond algorithm.
The triangulation computed will be a placing one according to the order of the points in the VERTICES or POINTS section. If you need an alternative order, you can store it in some section (it should be a valid permutation of the integer range 0 .. N_VERTICES-1) and specify its name as an additional command-line parameter.
lrs_ch_client <file> { -primal | -dual } [ -count [ -only_bounded ]]
Convex hull calculation using lrslib
In primal mode it converts the V-representation to the H-representation, in dual mode vice versa.
If the option -count is specified, only counts the facets rsp. vertices without storing them in a matrix. -only-bounded in connection with -dual counts bounded vertices only.
clip_graph <file> <clipped_graph_section> <vertices_section> <graph_section> <bounding_box_section>
Clip a graph with respect to a given bounding box. Used for the visualiztaion of Voronoi diagrams.
cdd_ch_client <file> { -primal | -dual}
For an inequality description of a polyhedron, compute the vertices with cddlib
Contributed by Marc Pfetsch
pvolume <file> <points_section> <triangulation_section>
Compute the volume of a polytope using its triangulation.
ts-max-metric <file> <n>
Metric maximizing the f-vector of the tight span for given number of points. See Herrmann & Joswig, Bounds on the f-vectors of tight spans.
rigidity_matrix <file>
Compute the the rigidity matrix of a bar and joint framework
rel_int_point <file> [-affinehull] [-unbounded]
Compute a relative interior point of a polyhedron. The option unbounded has to be set if the polyhedron may be unbounded. The option affinehull assumes that the affine hull of the polyhedron is still computed.
does_contain <file> <does_contain_section> [ <complement_section> | -complement ] <incidence_section> <set_section>
Finds all rows in an incidence matrix which do contain elements from a given set.
dgraph <file> <graph_section> <vertices_section> <far_face_section> { -linear <lof_section> | -abstract <aof_section> } [-inverse] [-generic]
Direct the graph of a polytope according to a linear or abstract objective function. The maximal and minimal values, which are attained by the objective function, as well as the minimal and the maximal face are written into separate sections.
The option -inverse directs the graph with decreasing instead of increasing edges. If the option -generic is set ties will be broken by lexicographical ordering.
gale_vertices <file>
Calculate the coordinates of points for an affine Gale diagram. First the projection vector (1, 1, ... ) is tried, then random vectors.
framework <out_file> <in_file> <graph_section> <coordinate_section>
Create a FRAMEWORK by combining a graph with coordinates given in <graph_section> and <coordinate_section>. The <coordinate_section> is given in homogeneous coordinates.
gale_transform <file>
Calculate the Gale transform matrix for vertices of a given polytope. Polytope must be bounded.
neighbors_cyclic_normal <file> { -primal | -dual }
Convert the combinatorial description of a 2-d or 3-d polytope to the form suitable for visualization tools.
The rows of the vertex-facet incidence and the facet neighborhood matrices are rearranged in the facet boundary counterclockwise traversal order, if seen from the outside of the polytope.
In dual mode, the notions of facets and vertices are interchanged.
graph_from_vertices <file>
Find the vertex graph of a polytope given by its vertices, without calculating the convex hull. Currently, can handle only bounded polytopes.
nn_crust <file> <nn_section> <nn_crust_section> <sites_section> <delaunay_section>
Polygonal reconstruction of a smooth curve from a finite set of samples. Sampling rate of <= 1/3 suffices. If -nnonly flag is set only the subgraph of nearest neighbors is computed.
T. K. Dey and P. Kumar: A simple provable algorithm for curve reconstruction. Proc. 10th. Annu. ACM-SIAM Sympos. Discrete Alg., 1999, 893-894.
bounding_box <file> <vertices_section> <bounding_box_section> [ -voronoi ] [ -offset <%> ]
Introduce artificial boundary facets (which are always vertical, i.e., last coordinate is zero) to allow for bounded images of unbounded polyhedra (e.g., Voronoi polyhedra). -offset defaults to 10%. By default all directions are bounded. If the option -voronoi is set, the last direction is left unbounded.
rigid_components_of_patterns <file> <rigid_components_section> <pattern_section>
Calculate the rigid components of the graphs induced by the given patterns.
pseudo-simplex <file> { -maximize | -minimize }
Find an optimum of a linear objective function. The method generalizes the behavior of the simplex algorithm, but it relies on complete information about the solution polytope.
WARNING: this is not an efficient way to solve a linear program.
tutte_lifting <file>
Given a 3-connected planar graph. If the corresponding polytope contains a triangular facet (ie. the graph contains a non- separating cycle of length 3), the client produces a realization in R3.
Responsible author: Thilo Rörig
cdd_ch_float_client <file> { -primal | -dual}
For an inequality description of a polyhedron, compute the vertices with cddlib. Floating-point coordinates are used.
Contributed by Marc Pfetsch
triang_boundary <file>
For a given polytope triangulation, find the trace on its surface (triangulation of facets)
2-face-sizes <file> <output_section> { -primal | -dual }
Compute the sizes of all 2-faces and codim-3-faces.
edge_colored_bounded_graph <file> <edge_colored_bounded_graph_section> <hasse_diagram_section> <far_face_section> [ <upper_bound> ]
Compute the bounded graph of an unbounded polyhedron and assign to each edge the maximal dimension of a face containing it. In the case of tight spans there are a priori upper bounds due to Mike Develin.
lrs_redund_client <file>
Redundant point elimination using lrslib
cdd_redund_client <file> [ -fromvertices ]
Redundant point elimination using cddlib
one_vertex <file>
Computes an arbitrary vertex of a pointed polyhedron.
schlegel_transform <Schlegel> <Polytope>
Calculate the transformation matrix for Schlegel diagram. Polytope must be bounded and full dimensional.
The transformation matrix, when applied to the points of the polytope, will put them on the projection facet, the latter will stay fixed. All calculations are made with rational coordinates. The last step towards a ready-to-display Schlegel diagram - an orthogonal transformation to Rd-1 - requires floating-point coordinates, and is `outsourced' into a separate client, schlegel_vertices.
dimension <file> <mode> <output_section>
Compute the dimension of the vector space built of points or hyperplanes.
mode may be -primal, -dual, or -rays. If option -rays is specified, only far points (rays) are considered, that is, the dimension of the far face is computed.
lrs_lp_client <file> { -maximize | -minimize | -valid }
Simplex algorithm using lrslib
infinitesimal_motions <file>
Compute the INFINITESIMAL_MOTIONS of a bar and joint framework from its RIGIDITY_MATRIX. Further this client computes the expansive patterns of the motions and the number of degrees of freedom.
dim_from_incidence <file>
Compute the dimension of a polytope which is given combinatorially.
cdd_lp_float_client <file> {-maximize, -minimize}
Solve a linear programm with cddlib, using floating-point arithmetic.
Contributed by Marc Pfetsch
face_lattice <file> <mode>
Write the face lattice of the polytope or its dual to stdout.
mode may be -primal or -dual
random_edge_epl <file>
For each vertex compute the expected path length to the maximum. The random edge pivot rule is applied.
centroid <file> <points_section> <triangulation_section>
Compute the centroid of a polytope using its triangulation. Polytope has to be bounded.
Contributed by Sven Herrmann
cdd_lp_client <file> { -maximize | -minimize }
Solve a linear programm with cddlib.
Contributed by Marc Pfetsch
ts-min-metric <file> <n>
Metric minimizing the number of facets of the tight span for given number of points. See Hermann & Joswig, Bounds on the f-vectors of tight spans.
schlegel_vertices_on_facet <SchlegelDiagram> <Polytope> <points_out> <points_in>
Apply the Schlegel transformation matrix to the given set of points.
schlegel_vertices <file> <points_in> <points_out>
Apply the Schlegel transformation matrix to the given set of points, then rotate the projection facet and obtain affine coordinates.