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.

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.
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.
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.
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
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.
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.
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
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].
n-gon file n [r]
Produce a regular n-gon.
All vertices lie on a circle of radius r. The radius defaults to 1.
neighborly_cubical file n d
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).
permutahedron file d
Produce the d-permutahedron. The vertices correspond to the elements of the symmetric group of degree d+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.
rand01 file d n [ seed ]
Produce a d-dimensional 0/1-polytope with n random vertices. Uniform distribution.
rand_sphere file dimension n [ seed ]
Produce a d-dimensional polytope with n random vertices on the unit sphere. Floating-point coordinates are used. Uniform distribution.
simplex file d [scale]
Produce the standard d-simplex. Combinatorially equivalent to regular polytope corresponding to the Coxeter group of type Ad-1.

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, but create a copy and modify it.

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.

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'".
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.
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.
conv output_file input_file_1 input_file_2 [ ... ]
Construct a new polyhedron as the convex hull of given polyhedra.
edge_middle output_file input_file
Produce the convex hull of all edge middle points of some polytope. The polytope must be bounded.
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.
intersection output_file input_file_1 input_file_2 [ ... ]
Construct a new polyhedron as the intersection of given polyhedra.
minkowski_sum output_file input_file_1 input_file_2
Construct a new polytope as the Minkowski sum of two given ones. Unbounded polyhedra are allowed.
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.
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".
proj output_file input_file [-] [ k1 [ k2 ... ] ]
Make a orthogonal projection of a polyhedron.
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".
rand outfile infile n [ seed ]
Produce a polytope with n random points from 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.
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.
spherize output_file input_file
Project all vertices of a polyhedron on the unit sphere. Input polyhedron must be centered.
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.
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.
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.
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.
unirand output_file input_file n [ 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.
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 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.
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.

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.

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 - bound - center - polarize.

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.
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).
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.
polarize output_file input_file [-noc]
Given a bounded and centered polytope P, produce its polar. Polar with respect to the standard Euclidean scalar product.
If the option -noc (no coordinates) is set, then only combinatorial information is handled.
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.

Visualization

schlegel_params file [ facet [ zoom ] ]
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.

Comparing polytopes

The programs described in this section are not clients in the strict sense, but rather perl wrappers to the dreadnaut program. The screen output you will see when you call them comes entirely from dreadnaut; please refer to its documentation if you need to decrypt it in all details.

check_congruence file1 file2
Check whether two given polytopes P and Q are congruent, i.e. whether there is an affine isomorphism between them that is induced by an orthogonal matrix. If the given polytopes are not congruent, the client checks whether there is an affine isomorphism between them that is induced by a scaled orthogonal matrix.
Uses the reduction of the congruence problem (for arbitrary point sets) 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
The construction is described in the documentation of the client congruence_graphs.
check_iso [--graph] file1 file2
Check whether the face lattices of two polytopes are isomorphic. The problem is reduced to graph isomorphism of the vertex-facet incidence graphs.
Use option --graph to check the isomorphism of two vertex-edge graphs.
congruence_graphs file1 file2
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
Used by (perl) client check_congruence.
Roughly speaking, the client reads the VERTICES of two polytopes and prints two graphs in nauty format to stdout. Each of these graphs is a complete graph with labeled edges, such that an edge e of the first graph has the same label as an an edge f of the second one iff the vertices corresponding to e have the same (squared) Euclidian distance as the vertices corresponding to f.
Since 'nauty' does not handle edge labels, the client splits each edge e of the two graphs and adds a path of length l+1 to the 'split node', where l is the label of the edge e.

Clients for internal use

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

altshuler_det file
Calculate the Altshuler Determinant of a polytope.
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.
cdd_ch_client file { -primal | -dual}
For an inequality description of a polyhedron, compute the vertices with cddlib
cdd_ch_float_client file { -primal | -dual}
For an inequality description of a polyhedron, compute the vertices with cddlib. Floating-point coordinates are used.
cdd_lp_client file { -maximize | -minimize }
Solve a linear programm with cddlib.
cdd_lp_float_client file {-maximize, -minimize}
Solve a linear programm with cddlib, using floating-point arithmetic.
compress_incidence file mode
Detect the vertices (dually: facets) among the given points (dually: inequalities). Used as postprocessing after the convex hull computation.
mode may be -primal or -dual
dgraph file [+/-]
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 optional "+" or "-" signals whether the graph is directed with incresing or decreasing edges, respectively. By default, the edges are increasing.
dim_from_incidence file
Compute the dimension of a polytope which is given combinatorially.
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.
dimension_float file mode output_section
Compute the dimension of the vector space built of points or hyperplanes. Floating-point coordinates are used.
f2_vector file
Compute the f_vector and f2_vector of a polytope.
face_lattice file mode
Write the face lattice of the polytope or its dual to stdout.
mode may be -primal or -dual
facets_from_incidence file
Compute the facet description of a polyhedron from its vertices and its incidence matrix.
facets_from_incidence_float file
Compute the facet description of a polyhedron from its vertices and its incidence matrix. The floating-point coordinates are used.
mode may be -primal or -dual
gale_transform file
Calculate the Gale transform matrix for vertices of a given polytope. Polytope must be bounded.
gale_vertices file
Calculate the coordinates of points for an affine Gale diagram. First the projection vector (1, 1, ... ) is tried, then random vectors.
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
graph_from_incidence file mode
Compute the vertex or facet graph of a polyhedron.
mode may be -primal or -dual
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.
h_vector file { SIMPLICIAL,SIMPLE }
Compute the h-vector of a simplicial or simple polytope from the f-vector.
hasse_diagram file mode
Compute the HASSE_DIAGRAM of the polytope.
incidence file first_matrix_section second_matrix_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.
incidence_float file first_matrix_section second_matrix_section incidence_section [ epsilon ]
Compute the incidence matrix of two vector sets with floating-point coordinates.
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 the abs of cosine of the angle between them is less than epsilon. Default value of epsilon is 0.01.
inner_point file matrix_section inner_point_section
Compute a true inner point of a convex hull of the given set of points
inner_point_float file matrix_section inner_point_section
Compute a true inner point of a convex hull of the given set of points. Floating-point coordinates are used.
lrs_ch_client file { -primal | -dual | -valid }
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 valid is specified, the procedure terminates immediately after the first vertex (pivot) is found.
lrs_lp_client file { -maximize | -minimize }
Simplex algorithm using lrslib
lrs_redund_client file
Redundant point elimination using lrslib
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.
nullspace file matrix_section nullspace_section
Compute the basis of the orthogonal complement to the row space of a given matrix.
pseudo-simplex file +|-
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.
pvolume file points_section triangulation_section
Compute the volume of a polytope using its triangulation.
random_edge_epl file
For each vertex compute the expected path length to the maximum. The random edge pivot rule is applied.
schlegel_interactiveschlegel_transform file.poly jvx_section java command line ...
Driver for interactive Schlegel diagram visualization.
schlegel_transform file
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.
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.
triang_boundary file
For a given polytope triangulation, find the trace on its surface (triangulation of facets)
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.
vertex_barycenter file
Compute the vertex barycenter of a polytope. Polytope must be bounded.
vertex_barycenter_float file
Compute the vertex barycenter of a polytope. Floating-point coordinates are used. Polytope must be bounded.
vertex_colors file min_r min_g min_b max_r max_g max_b
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.
vertices_from_incidence file
Compute the vertex description of a polyhedron from its facets and its incidence matrix.
vertices_from_incidence_float file
Compute the vertex description of a polyhedron from its facets and its incidence matrix. Floating-point coordinates are used.
bipartite file graph_section even_section
Determine whether an undirected graph is bipartite.
connectivity file graph_section connectivity_section
Compute the connectivity of a given graph using the Ford-Fulkerson flow algorithm.
diameter file graph_section diameter_section
Compute the diameter of an undirected graph.
spring_embedder file graph_section embedding_section [ {-objective,-selection} section -seed s ] [ {-scale,-balance,-viscosity,-inertion,-orientation,-separation} 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.
If the nodes already have an embedding in Rd and there is a linear 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 objective.
Alternatively, a selected subset of nodes can be requested to be set apart from the rest of the graph. The numbers of selected nodes are read as a set from the section specified in option selection.
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. orientation changes the relative influence of the linear objective function on the embedding. separation changes the additional repulsion force between the selected and non-selected nodes.
triangle_free file graph_section triangle_free_section
Determine whether a (possibly directed) graph has triangles or not.

Other

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.
steiner_point_all file [ eps ] [ -seed s ]
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 -seed s parameter may be set to initialize the random calculation of the angles.
Polytope must be bounded.
steiner_point_graph file [ -seed seed ] [ eps ]
Compute the Steiner point 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 -seed s parameter may be set to initialize the random calculation of the angles.