Changeset 7e8485 in git


Ignore:
Timestamp:
Oct 21, 2013, 3:57:03 PM (11 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'c7af8613769b29c741d6c338945669719f1fc4f8')
Children:
48935b4077cd8f5a0f1e6050b74b4fbd0f364df1
Parents:
f1babfbabc0fc2906b36df32051eaaf09673dc6f
git-author:
Martin Lee <martinlee84@web.de>2013-10-21 15:57:03+02:00
git-committer:
Yue Ren <ren@mathematik.uni-kl.de>2013-12-11 17:46:45+01:00
Message:
chg: new version of oldpolymake.lib from Thomas Markwig (keilen@mathematik.uni-kl.de)
File:
1 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/oldpolymake.lib

    rf1babf r7e8485  
    1 ////
    2 version="version oldpolymake.lib 4.0.0.0 Jun_2013 "; // $Id$
     1version="version oldpolymake.lib 4.0.0.0 Jun_2013 ";
    32category="Tropical Geometry";
    43info="
    5 LIBRARY:   oldpolymake.lib  Computations with polytopes and fans,
    6                             interface to polymake and TOPCOM
     4LIBRARY:   oldpolymake.lib    Computations with polytopes and fans,
     5                              interface to polymake and TOPCOM
    76AUTHOR:    Thomas Markwig,  email: keilen@mathematik.uni-kl.de
    87
     
    109   Most procedures will not work unless polymake or topcom is installed and
    1110   if so, they will only work with the operating system LINUX!
    12    For more detailed information see the following note or consult the
     11   For more detailed information see IMPORTANT NOTE respectively consult the
    1312   help string of the procedures.
    1413
    15 NOTE:
    16    Even though this is a Singular library for computing polytopes and fans
    17    such as the Newton polytope or the Groebner fan of a polynomial, most of
    18    the hard computations are NOT done by Singular but by the program
     14   The conventions used in this library for polytopes and fans, e.g. the
     15   length and labeling of their vertices resp. rays, differs from the conventions
     16   used in polymake and thus from the conventions used in the polymake
     17   extension polymake.so of Singular. We recommend to use the newer polymake.so
     18   whenever possible.
     19
     20IMPORTANT NOTE:
     21   Even though this is a Singular library for computing polytopes and fans
     22   such as the Newton polytope or the Groebner fan of a polynomial, most of
     23   the hard computations are NOT done by Singular but by the program
    1924@* - polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt
    20 @*   (see http://www.math.tu-berlin.de/polymake/),
    21 @* respectively (only in the procedure triangularions) by the program
    22 @* - topcom by Joerg Rambau, Universitaet Bayreuth (see http://www.uni-bayreuth.de/
    23      departments/wirtschaftsmathematik/rambau/TOPCOM);
    24 @*   This library should rather be seen as an interface which allows to use a
    25      (very limited) number of options which polymake respectively topcom offers
    26      to compute with polytopes and fans and to make the results available in
    27      Singular for further computations;
     25@*   (see http://www.math.tu-berlin.de/polymake/), 
     26@* respectively (only in the procedure triangulations) by the program
     27@* - topcom by Joerg Rambau, Universitaet Bayreuth (see
     28@*   http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM);
     29@*   this library should rather be seen as an interface which allows to use a
     30     (very limited) number of options which polymake respectively topcom offers 
     31     to compute with polytopes and fans and to make the results available in 
     32     Singular for further computations; 
    2833     moreover, the user familiar with Singular does not have to learn the syntax
    29      of polymake or topcom, if the options offered here are sufficient for his
     34     of polymake or topcom, if the options offered here are sufficient for his 
    3035     purposes.
    31 @*   Note, though, that the procedures concerned with planar polygons are
     36@*   Note, though, that the procedures concerned with planar polygons are 
    3237     independent of both, polymake and topcom.
    3338
    34 PROCEDURES:
    35   polymakePolytope()   computes the vertices of a polytope using polymake
    36   newtonPolytopeP()     computes the Newton polytope of a polynomial
    37   newtonPolytopeLP()   computes the lattice points of the Newton polytope
    38   normalFan()          computes the normal fan of a polytope
    39   groebnerFan()        computes the Groebner fan of a polynomial
    40   intmatToPolymake()   transforms an integer matrix into polymake format
    41   polymakeToIntmat()   transforms polymake output into an integer matrix
    42 
    43   triangulations()     computes all triangulations of a marked polytope
    44   secondaryPolytope()  computes the secondary polytope of a marked polytope
    45 
    46   secondaryFan()       computes the secondary fan of a marked polytope
    47 
    48   cycleLength()      computes the cycleLength of cycle
    49   splitPolygon()     splits a marked polygon into vertices, facets, interior points
    50   eta()              computes the eta-vector of a triangulation
    51   findOrientedBoundary()    computes the boundary of a convex hull
    52   cyclePoints()      computes lattice points connected to some lattice point
    53   latticeArea()      computes the lattice area of a polygon
    54   picksFormula()     computes the ingrediants of Pick's formula for a polygon
    55   ellipticNF()       computes the normal form of an elliptic polygon
    56   ellipticNFDB()     displays the 16 normal forms of elliptic polygons
    57 
    58   polymakeKeepTmpFiles()  determines if the files created in /tmp should be kept
     39PROCEDURES USING POLYMAKE:
     40  polymakePolytope()  computes the vertices of a polytope using polymake
     41  newtonPolytope()    computes the Newton polytope of a polynomial
     42  newtonPolytopeLP()  computes the lattice points of the Newton polytope
     43  normalFan()         computes the normal fan of a polytope
     44  groebnerFan()       computes the Groebner fan of a polynomial
     45
     46PROCEDURES USING TOPCOM:
     47  triangulations()    computes all triangulations of a marked polytope
     48  secondaryPolytope() computes the secondary polytope of a marked polytope
     49
     50PROCEDURES USING POLYMAKE AND TOPCOM:
     51  secondaryFan()      computes the secondary fan of a marked polytope
     52
     53PROCEDURES CONERNED WITH PLANAR POLYGONS:
     54  cycleLength()    computes the cycleLength of cycle
     55  splitPolygon()   splits a marked polygon into vertices, facets, interior points
     56  eta()            computes the eta-vector of a triangulation
     57  findOrientedBoundary()  computes the boundary of a convex hull
     58  cyclePoints()    computes lattice points connected to some lattice point
     59  latticeArea()    computes the lattice area of a polygon
     60  picksFormula()   computes the ingrediants of Pick's formula for a polygon
     61  ellipticNF()     computes the normal form of an elliptic polygon
     62  ellipticNFDB()   displays the 16 normal forms of elliptic polygons
    5963
    6064KEYWORDS:    polytope; fan; secondary fan; secondary polytope; polymake;
    61              Newton polytope; Groebner fan
     65             Newton polytope; Groebner fan 
    6266";
    6367
     
    8387LIB "linalg.lib";
    8488LIB "random.lib";
     89LIB "polymake.so";
    8590////////////////////////////////////////////////////////////////////////////////
    8691
     
    9095/////////////////////////////////////////////////////////////////////////////
    9196
    92 proc polymakePolytope (intmat polytop,list #)
    93 "USAGE:  polymakePolytope(polytope[,#]);   polytope list, # string
    94 ASSUME:  each row of polytope gives the coordinates of a lattice point of a
    95          polytope with their affine coordinates as given by the output of
     97proc polymakePolytope (intmat points)
     98"USAGE:  polymakePolytope(points);   polytope intmat
     99ASSUME:  each row of points gives the coordinates of a lattice point of a
     100         polytope with their affine coordinates as given by the output of 
    96101         secondaryPolytope
    97 PURPOSE: the procedure calls polymake to compute the vertices of the polytope
     102PURPOSE: the procedure calls polymake to compute the vertices of the polytope 
    98103         as well as its dimension and information on its facets
    99 RETURN:  list L with four entries
     104RETURN:  list, L with four entries
    100105@*            L[1] : an integer matrix whose rows are the coordinates of vertices
    101                      of the polytope
     106                     of the polytope 
    102107@*            L[2] : the dimension of the polytope
    103 @*            L[3] : a list whose i-th entry explains to which vertices the
    104                      ith vertex of the Newton polytope is connected
    105                      -- i.e. L[3][i] is an integer vector and an entry k in
    106                         there means that the vertex L[1][i] is connected to the
     108@*            L[3] : a list whose ith entry explains to which vertices the
     109                     ith vertex of the Newton polytope is connected 
     110                     -- i.e. L[3][i] is an integer vector and an entry k in 
     111                        there means that the vertex L[1][i] is connected to the 
    107112                        vertex L[1][k]
    108 @*            L[4] : an integer matrix whose rows mulitplied by
    109                      (1,var(1),...,var(nvar)) give a linear system of equations
     113@*            L[4] : an matrix of type bigintmat whose rows mulitplied by
     114                     (1,var(1),...,var(nvar)) give a linear system of equations 
    110115                     describing the affine hull of the polytope,
    111116                     i.e. the smallest affine space containing the polytope
    112 NOTE: -  for its computations the procedure calls the program polymake by
    113          Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt;
    114          it therefore is necessary that this program is installed in order
     117NOTE: -  for its computations the procedure calls the program polymake by 
     118         Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; 
     119         it therefore is necessary that this program is installed in order 
    115120         to use this procedure;
    116121         see http://www.math.tu-berlin.de/polymake/
    117 @*    -  note that in the vertex edge graph we have changed the polymake
    118          convention which starts indexing its vertices by zero while we start
     122@*    -  note that in the vertex edge graph we have changed the polymake 
     123         convention which starts indexing its vertices by zero while we start 
    119124         with one !
    120 @*    -  the procedure creates the file  /tmp/polytope.polymake which contains
    121          the polytope in polymake format; if you wish to use this for further
    122          computations with polymake, you have to use the procedure
    123          polymakeKeepTmpFiles in before
    124 @*    -  moreover, the procedure creates the file /tmp/polytope.output which
    125          it deletes again before ending
    126 @*    -  it is possible to provide an optional second argument a string
    127          which then will be used instead of 'polytope' in the name of the
    128          polymake output file
    129125EXAMPLE: example polymakePolytope;   shows an example"
    130126{
    131   // the header for the file secendarypolytope.polymake
    132   string sp="_application polytope
    133 _version 2.2
    134 _type RationalPolytope
    135 
    136 POINTS
    137 ";
     127  // add a first column to polytope as homogenising coordinate
     128  points=intmatAddFirstColumn(points,"points");
     129  polytope polytop=polytopeViaPoints(points);
     130  list graph=vertexAdjacencyGraph(polytop)[2];
    138131  int i,j;
    139   // set the name for the polymake output file
    140   if (size(#)>0)
    141   {
    142     if (typeof(#[1])=="string")
    143     {
    144       string dateiname=#[1];
    145     }
    146     else
    147     {
    148       string dateiname="polytope";
    149     }
    150   }
    151   else
    152   {
    153     string dateiname="polytope";
    154   }
    155   // create the lattice point list for polymake
    156   sp=sp+intmatToPolymake(polytop,"points");
    157   // initialise dateiname.polymake and compute the vertices
    158   write(":w /tmp/"+dateiname+".polymake",sp);
    159   system("sh","cd /tmp; polymake "+dateiname+".polymake VERTICES > "+dateiname+".output");
    160   string vertices=read("/tmp/"+dateiname+".output");
    161   system("sh","/bin/rm /tmp/"+dateiname+".output");
    162   intmat np=polymakeToIntmat(vertices,"affine");
    163   // compute the dimension
    164   system("sh","cd /tmp; polymake "+dateiname+".polymake DIM > "+dateiname+".output");
    165   string pdim=read("/tmp/"+dateiname+".output");
    166   system("sh","/bin/rm /tmp/"+dateiname+".output");
    167   pdim=pdim[5,size(pdim)-6];
    168   execute("int nd="+pdim+";");
    169   // compute the vertex-edge graph
    170   system("sh","cd /tmp; polymake "+dateiname+".polymake GRAPH > "+dateiname+".output");
    171   string vertexedgegraph=read("/tmp/"+dateiname+".output");
    172   system("sh","/bin/rm /tmp/"+dateiname+".output");
    173   vertexedgegraph=vertexedgegraph[7,size(vertexedgegraph)-8];
    174   string newveg;
    175   for (i=1;i<=size(vertexedgegraph);i++)
    176   {
    177     if (vertexedgegraph[i]=="{")
    178     {
    179       newveg=newveg+"intvec(";
    180     }
    181     else
    182     {
    183       if (vertexedgegraph[i]=="}")
    184       {
    185         newveg=newveg+"),";
    186       }
    187       else
    188       {
    189         if (vertexedgegraph[i]==" ")
    190         {
    191           newveg=newveg+",";
    192         }
    193         else
    194         {
    195           newveg=newveg+vertexedgegraph[i];
    196         }
    197       }
    198     }
    199   }
    200   newveg=newveg[1,size(newveg)-1];
    201   execute("list nveg="+newveg+";");
    202   // raise each entry in nveg by one
    203   for (i=1;i<=size(nveg);i++)
    204   {
    205     for (j=1;j<=size(nveg[i]);j++)
    206     {
    207       nveg[i][j]=nveg[i][j]+1;
    208     }
    209   }
    210   // compute the affine hull
    211   system("sh","cd /tmp; polymake "+dateiname+".polymake AFFINE_HULL > "+dateiname+".output");
    212   string equations=read("/tmp/"+dateiname+".output");
    213   system("sh","/bin/rm /tmp/"+dateiname+".output");
    214   if (size(equations)>14)
    215   {
    216     intmat neq=polymakeToIntmat(equations,"cleardenom");
    217   }
    218   else
    219   {
    220     intmat neq[1][ncols(polytop)+1];
    221   }
    222   // delete the tmp-files, if polymakekeeptmpfiles is not set
    223   if (defined(polymakekeeptmpfiles)==0)
    224   {
    225     system("sh","/bin/rm /tmp/"+dateiname+".polymake");
    226   }
    227   // return the files
    228   return(list(np,nd,nveg,neq));
     132  for (i=1;i<=size(graph);i++)
     133  {
     134    for (j=1;j<=size(graph[i]);j++)
     135    {
     136      graph[i][j]=graph[i][j]+1;
     137    }
     138  }
     139  return(list(intmatcoldelete(vertices(polytop),1),dimension(polytop),graph,equations(polytop)));
    229140}
    230141example
     
    232143   "EXAMPLE:";
    233144   echo=2;
    234    // the lattice points of the unit square in the plane
     145   // the lattice points of the unit square in the plane 
    235146   list points=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1);
    236147   // the secondary polytope of this lattice point configuration is computed
     
    247158   ring r=0,x(1..4),dp;
    248159   matrix M[5][1]=1,x(1),x(2),x(3),x(4);
    249    np[4]*M;
     160   intmat(np[4])*M;
    250161}
    251162
    252163/////////////////////////////////////////////////////////////////////////////
    253164
    254 proc newtonPolytopeP (poly f,list #)
    255 "USAGE: newtonPolytopeP(f[,#]);  f poly, # string
    256 RETURN: list L with four entries
     165proc newtonPolytope (poly f)
     166"USAGE: newtonPolytope(f);  f poly
     167RETURN: list, L with four entries
    257168@*            L[1] : an integer matrix whose rows are the coordinates of vertices
    258169                     of the Newton polytope of f
    259170@*            L[2] : the dimension of the Newton polytope of f
    260 @*            L[3] : a list whose ith entry explains to which vertices the
    261                      ith vertex of the Newton polytope is connected
    262                      -- i.e. L[3][i] is an integer vector and an entry k in
     171@*            L[3] : a list whose ith entry explains to which vertices the 
     172                     ith vertex of the Newton polytope is connected 
     173                     -- i.e. L[3][i] is an integer vector and an entry k in 
    263174                        there means that the vertex L[1][i] is
    264175                        connected to the vertex L[1][k]
    265 @*            L[4] : an integer matrix whose rows mulitplied by
    266                      (1,var(1),...,var(nvar)) give a linear system of equations
     176@*            L[4] : an matrix of type bigintmat whose rows mulitplied by
     177                     (1,var(1),...,var(nvar)) give a linear system of equations 
    267178                     describing the affine hull of the Newton polytope, i.e. the
    268179                     smallest affine space containing the Newton polytope
    269 NOTE: -  if we replace the first column of L[4] by zeros, i.e. if we move
    270          the affine hull to the origin, then we get the equations for the
    271          orthogonal comploment of the linearity space of the normal fan dual
     180NOTE: -  if we replace the first column of L[4] by zeros, i.e. if we move 
     181         the affine hull to the origin, then we get the equations for the 
     182         orthogonal complement of the linearity space of the normal fan dual
    272183         to the Newton polytope, i.e. we get the EQUATIONS that
    273184         we need as input for polymake when computing the normal fan
     
    275186         TU Berlin and Michael Joswig, so it only works if polymake is installed;
    276187         see http://www.math.tu-berlin.de/polymake/
    277 @*    -  the procedure creates the file  /tmp/newtonPolytope.polymake which
    278          contains the polytope in polymake format and which can be used for
    279          further computations with polymake
    280 @*    -  moreover, the procedure creates the file /tmp/newtonPolytope.output
    281          and deletes it again before ending
    282 @*    -  it is possible to give as an optional second argument a string
    283          which then will be used instead of 'newtonPolytope' in the name of
    284          the polymake output file
    285 EXAMPLE: example newtonPolytopeP;   shows an example"
     188EXAMPLE: example newtonPolytope;   shows an example"
    286189{
    287190  int i,j;
    288   // compute the list of exponent vectors of the polynomial,
     191  // compute the list of exponent vectors of the polynomial, 
    289192  // which are the lattice points
    290193  // whose convex hull is the Newton polytope of f
     
    296199    f=f-lead(f);
    297200  }
    298   if (size(#)==0)
    299   {
    300     #[1]="newtonPolytope";
    301   }
    302201  // call polymakePolytope with exponents
    303   return(polymakePolytope(exponents,#));
     202  return(polymakePolytope(exponents));
    304203}
    305204example
     
    311210   poly f=y3+x2+xy+2xz+yz+z2+1;
    312211   // the Newton polytope of f is
    313    list np=newtonPolytopeP(f);
     212   list np=newtonPolytope(f);
    314213   // the vertices of the Newton polytope are:
    315214   np[1];
     
    317216   np[2];
    318217   // np[3] contains information how the vertices are connected to each other,
    319    // e.g. the first vertex (number 0) is connected to the second, third and
     218   // e.g. the first vertex (number 0) is connected to the second, third and 
    320219   //      fourth vertex
    321220   np[3][1];
     
    323222   f=x2-y3;
    324223   // the Newton polytope of f is
    325    np=newtonPolytopeP(f);
     224   np=newtonPolytope(f);
    326225   // the vertices of the Newton polytope are:
    327226   np[1];
    328227   // its dimension is
    329    np[2];
    330    // the Newton polytope is contained in the affine space given
     228   np[2];   
     229   // the Newton polytope is contained in the affine space given 
    331230   //     by the equations
    332    np[4]*M;
     231   intmat(np[4])*M;
    333232}
    334233
     
    337236proc newtonPolytopeLP (poly f)
    338237"USAGE:  newtonPolytopeLP(f);  f poly
    339 RETURN: list, the exponent vectors of the monomials occuring in f,
     238RETURN: list, the exponent vectors of the monomials occuring in f, 
    340239              i.e. the lattice points of the Newton polytope of f
    341240EXAMPLE: example normalFan;   shows an example"
     
    365264proc normalFan (intmat vertices,intmat affinehull,list graph,int er,list #)
    366265"USAGE:  normalFan (vert,aff,graph,rays,[,#]);   vert,aff intmat,  graph list, rays int, # string
    367 ASSUME:  - vert is an integer matrix whose rows are the coordinate of
    368            the vertices of a convex lattice polytope;
     266ASSUME:  - vert is an integer matrix whose rows are the coordinate of 
     267           the vertices of a convex lattice polytope; 
    369268@*       - aff describes the affine hull of this polytope, i.e.
    370            the smallest affine space containing it, in the following sense:
    371            denote by n the number of columns of vert, then multiply aff by
    372            (1,x(1),...,x(n)) and set the resulting terms to zero in order to
     269           the smallest affine space containing it, in the following sense: 
     270           denote by n the number of columns of vert, then multiply aff by 
     271           (1,x(1),...,x(n)) and set the resulting terms to zero in order to 
    373272           get the equations for the affine hull;
    374 @*       - the ith entry of graph is an integer vector describing to which
    375            vertices the ith vertex is connected, i.e. a k as entry means that
     273@*       - the ith entry of graph is an integer vector describing to which 
     274           vertices the ith vertex is connected, i.e. a k as entry means that 
    376275           the vertex vert[i] is connected to vert[k];
    377 @*       - the integer rays is either one (if the extreme rays should be
     276@*       - the integer rays is either one (if the extreme rays should be 
    378277           computed) or zero (otherwise)
    379 RETURN:  list, the ith entry of L[1] contains information about the cone in the
    380                normal fan dual to the ith vertex of the polytope
    381 @*             L[1][i][1] = integer matrix representing the inequalities which
     278RETURN:  list, the ith entry of L[1] contains information about the cone in the 
     279               normal fan dual to the ith vertex of the polytope 
     280@*             L[1][i][1] = integer matrix representing the inequalities which 
    382281                            describe the cone dual to the ith vertex
    383 @*             L[1][i][2] = a list which contains the inequalities represented
    384                             by L[i][1] as a list of strings, where we use the
     282@*             L[1][i][2] = a list which contains the inequalities represented 
     283                            by L[i][1] as a list of strings, where we use the 
    385284                            variables x(1),...,x(n)
    386285@*             L[1][i][3] = only present if 'er' is set to 1; in that case it is
    387                             an interger matrix whose rows are the extreme rays
     286                            an interger matrix whose rows are the extreme rays 
    388287                            of the cone
    389 @*             L[2] = is an integer matrix whose rows span the linearity space
    390                       of the fan, i.e. the linear space which is contained in
     288@*             L[2] = is an integer matrix whose rows span the linearity space 
     289                      of the fan, i.e. the linear space which is contained in 
    391290                      each cone
    392291NOTE:    - the procedure calls for its computation polymake by Ewgenij Gawrilow,
    393            TU Berlin and Michael Joswig, so it only works if polymake is
     292           TU Berlin and Michael Joswig, so it only works if polymake is 
    394293           installed;
    395294           see http://www.math.tu-berlin.de/polymake/
    396 @*       - in the optional argument # it is possible to hand over other names
     295@*       - in the optional argument # it is possible to hand over other names 
    397296           for the variables to be used -- be careful, the format must be correct
    398            which is not tested, e.g. if you want the variable names to be
    399            u00,u10,u01,u11 then you must hand over the string 'u11,u10,u01,u11'
     297           and that is not tested, e.g. if you want the variable names to be
     298           u00,u10,u01,u11 then you must hand over the string u11,u10,u01,u11
    400299EXAMPLE: example normalFan;   shows an example"
    401300{
    402301  list ineq; // stores the inequalities of the cones
    403302  int i,j,k;
    404   // we work over the following ring
     303  // we work over the following ring 
    405304  execute("ring ineqring=0,x(1.."+string(ncols(vertices))+"),lp;");
    406305  string greatersign=">";
     
    427326  for (i=1;i<=nrows(vertices);i++)
    428327  {
    429     // first we produce for each vertex in the polytope
     328    // first we produce for each vertex in the polytope 
    430329    // the inequalities describing the dual cone in the normal fan
    431     list pp;  // contain strings representing the inequalities
     330    list pp;  // contain strings representing the inequalities 
    432331              // describing the normal cone
    433     intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities
     332    intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities 
    434333                                                // as rows
    435     // consider all the vertices to which the ith vertex in the
     334    // consider all the vertices to which the ith vertex in the 
    436335    // polytope is connected by an edge
    437336    for (j=1;j<=size(graph[i]);j++)
    438337    {
    439338      // produce the vector ie_j pointing from the jth vertex to the ith vertex;
    440       // this will be the jth inequality for the cone in the normal fan dual to
     339      // this will be the jth inequality for the cone in the normal fan dual to 
    441340      // the ith vertex
    442341      ie[j,1..ncols(vertices)]=vertices[i,1..ncols(vertices)]-vertices[graph[i][j],1..ncols(vertices)];
     
    445344      p=(VAR*EXP)[1,1];
    446345      pl,pr=0,0;
    447       // separate the terms with positive coefficients in p from
     346      // separate the terms with positive coefficients in p from 
    448347      // those with negative coefficients
    449348      for (k=1;k<=size(p);k++)
     
    458357        }
    459358      }
    460       // build the string which represents the jth inequality
     359      // build the string which represents the jth inequality 
    461360      // for the cone dual to the ith vertex
    462       // as polynomial inequality of type string, and store this
     361      // as polynomial inequality of type string, and store this 
    463362      // in the list pp as jth entry
    464363      pp[j]=string(pl)+" "+greatersign+" "+string(pr);
     
    469368  }
    470369  // remove the first column of affine hull to compute the linearity space
    471   intmat linearity=intmatcoldelete(affinehull,1);
     370  intmat linearity[1][ncols(vertices)];
     371  if (nrows(affinehull)>0)
     372  {
     373    linearity=intmatcoldelete(affinehull,1);
     374  }
    472375  //////////////////////////////////////////////////////////////////
    473376  // Compute next the extreme rays of the cones
     
    476379  {
    477380    list extremerays; // keeps the result
    478     string polymake; // keeps polymake output
    479     // the header for ineq.polymake
    480     string head="_application polytope
    481 _version 2.2
    482 _type RationalPolytope
    483 
    484 INEQUALITIES
    485 ";
    486     // the tail for both polymake files
    487     string tail="
    488 EQUATIONS
    489 ";
    490     tail=tail+intmatToPolymake(linearity,"rays");
    491     string ungleichungen; // keeps the inequalities for the polymake code
     381    cone kegel;
     382    intmat linearspan=intmatAddFirstColumn(linearity,"rays");
    492383    intmat M; // the matrix keeping the inequalities
    493     // create the file ineq.output
    494     write(":w /tmp/ineq.output","");
    495     int dimension; // keeps the dimension of the intersection the
    496                    // bad cones with the u11tobeseencone
    497384    for (i=1;i<=size(ineq);i++)
    498385    {
    499       i,". Cone of ",nrows(vertices); // indicate how many
    500                                       // vertices have been dealt with
    501       ungleichungen=intmatToPolymake(ineq[i][1],"rays");
    502       // write the inequalities to ineq.polymake and call polymake
    503       write(":w /tmp/ineq.polymake",head+ungleichungen+tail);
    504       ungleichungen=""; // clear ungleichungen
    505       system("sh","cd /tmp; /bin/rm ineq.output; polymake ineq.polymake VERTICES > ineq.output");
    506       // read the result of polymake
    507       polymake=read("/tmp/ineq.output");
    508       intmat VERT=polymakeToIntmat(polymake,"affine");
    509       extremerays[i]=VERT;
    510       kill VERT;
     386      kegel=coneViaInequalities(intmatAddFirstColumn(ineq[i][1],"rays"),linearspan);
     387      extremerays[i]=intmatcoldelete(rays(kegel),1);
    511388    }
    512389    for (i=1;i<=size(ineq);i++)
     
    515392    }
    516393  }
    517   // delete the tmp-files, if polymakekeeptmpfiles is not set
    518   if (defined(polymakekeeptmpfiles)==0)
    519   {
    520     system("sh","/bin/rm /tmp/ineq.polymake");
    521     system("sh","/bin/rm /tmp/ineq.output");
    522   }
    523394  // get the linearity space
    524   return(list(ineq,linearity));
     395  return(list(ineq,linearity)); 
    525396}
    526397example
     
    532403   poly f=y3+x2+xy+2xz+yz+z2+1;
    533404   // the Newton polytope of f is
    534    list np=newtonPolytopeP(f);
     405   list np=newtonPolytope(f);
    535406   // the Groebner fan of f, i.e. the normal fan of the Newton polytope
    536407   list gf=normalFan(np[1],np[4],np[3],1,"x,y,z");
     
    549420/////////////////////////////////////////////////////////////////////////////
    550421
    551 proc groebnerFan (poly f,list #)
    552 "USAGE:  groebnerFan(f[,#]);  f poly, # string
    553 RETURN:  list, the ith entry of L[1] contains information about the ith cone
    554                in the Groebner fan dual to the ith vertex in the Newton
     422proc groebnerFan (poly f)
     423"USAGE:  groebnerFan(f);  f poly
     424RETURN:  list, the ith entry of L[1] contains information about the ith cone 
     425               in the Groebner fan dual to the ith vertex in the Newton 
    555426               polytope of the f
    556 @*             L[1][i][1] = integer matrix representing the inequalities
    557                             which describe the cone
    558 @*             L[1][i][2] = a list which contains the inequalities represented
     427@*             L[1][i][1] = integer matrix representing the inequalities 
     428                            which describe the cone         
     429@*             L[1][i][2] = a list which contains the inequalities represented 
    559430                            by L[1][i][1] as a list of strings
    560 @*             L[1][i][3] = an interger matrix whose rows are the extreme rays
     431@*             L[1][i][3] = an interger matrix whose rows are the extreme rays 
    561432                            of the cone
    562 @*             L[2] = is an integer matrix whose rows span the linearity space
    563                       of the fan, i.e. the linear space which is contained
    564                       in each cone
    565 @*             L[3] = the Newton polytope of f in the format of the procedure
     433@*             L[2] = is an integer matrix whose rows span the linearity space 
     434                      of the fan, i.e. the linear space which is contained 
     435                      in each cone               
     436@*             L[3] = the Newton polytope of f in the format of the procedure 
    566437                      newtonPolytope
    567 @*             L[4] = integer matrix where each row represents the exponet
     438@*             L[4] = integer matrix where each row represents the exponent
    568439                      vector of one monomial occuring in the input polynomial
    569440NOTE: - if you have already computed the Newton polytope of f then you might want
    570         to use the procedure normalFan instead in order to avoid doing costly
     441        to use the procedure normalFan instead in order to avoid doing costly 
    571442        computation twice
    572443@*    - the procedure calls for its computation polymake by Ewgenij Gawrilow,
    573444        TU Berlin and Michael Joswig, so it only works if polymake is installed;
    574445        see http://www.math.tu-berlin.de/polymake/
    575 @*    - the procedure creates the file  /tmp/newtonPolytope.polymake which
    576         contains the Newton polytope of f in polymake format and which can
    577         be used for further computations with polymake
    578 @*    - it is possible to give as an optional second argument as string which
    579         then will be used instead of 'newtonPolytope' in the name of the
    580         polymake output file
    581446EXAMPLE: example groebnerFan;   shows an example"
    582447{
    583448  int i,j;
    584   // compute the list of exponent vectors of the polynomial, which are
     449  // compute the list of exponent vectors of the polynomial, which are 
    585450  // the lattice points whose convex hull is the Newton polytope of f
    586451  intmat exponents[size(f)][nvars(basering)];
     
    591456    f=f-lead(f);
    592457  }
    593   if (size(#)==0)
    594   {
    595     #[1]="newtonPolytope";
    596   }
    597458  // call polymakePolytope with exponents
    598   list newtonp=polymakePolytope(exponents,"newtonPolytope");
     459  list newtonp=polymakePolytope(exponents);
    599460  // get the variables as string
    600461  string variablen;
     
    642503
    643504
    644 /////////////////////////////////////////////////////////////////////////////
    645 
    646 proc intmatToPolymake (intmat M,string art)
    647 "USAGE:  intmatToPolymake(M,art);  M intmat, art string
    648 ASSUME:  - M is an integer matrix which should be transformed into polymake
    649            format;
    650 @*       - art is one of the following strings:
    651 @*           + 'rays'   : indicating that a first column of 0's should be added
    652 @*           + 'points' : indicating that a first column of 1's should be added
    653 RETURN:  string, the matrix is transformed in a string and a first column has
    654                  been added
    655 EXAMPLE: example intmatToPolymake;   shows an example"
    656 {
    657   if (art=="rays")
    658   {
    659     string anf="0 ";
    660   }
    661   else
    662   {
    663     string anf="1 ";
    664   }
    665   string sp;
    666   int i,j;
    667   // create the lattice point list for polymake
    668   for (i=1;i<=nrows(M);i++)
    669   {
    670     sp=sp+anf;
    671     for (j=1;j<=ncols(M);j++)
    672     {
    673       sp=sp+string(M[i,j])+" ";
    674       if (j==ncols(M))
    675       {
    676         sp=sp+"
    677 ";
    678       }
    679     }
    680   }
    681   return(sp);
    682 }
    683 example
    684 {
    685    "EXAMPLE:";
    686    echo=2;
    687    intmat M[3][4]=1,2,3,4,5,6,7,8,9,10,11,12;
    688    intmatToPolymake(M,"rays");
    689    intmatToPolymake(M,"points");
    690 }
    691 
    692 /////////////////////////////////////////////////////////////////////////////
    693 
    694 proc polymakeToIntmat (string pm,string art)
    695 "USAGE:  polymakeToIntmat(pm,art);  pm, art string
    696 ASSUME:  pm is the result of calling polymake with one 'argument' like
    697          VERTICES, AFFINE_HULL, etc., so that the first row of the string is
    698          the name of the corresponding 'argument' and the further rows contain
    699          the result which consists of vectors either over the integers
    700          or over the rationals
    701 RETURN:  intmat, the rows of the matrix are basically the vectors in pm, starting
    702                  from the second row, where each row has been multiplied with the
    703                  lowest common multiple of the denominators of its entries as if
    704                  it is an integer matrix; moreover, if art=='affine', then
    705                  the first column is omitted since we only want affine
    706                  coordinates
    707 EXAMPLE: example polymakeToIntmat;   shows an example"
    708 {
    709   // we need a line break
    710   string zeilenumbruch="
    711 ";
    712   // remove the 'argment' name, i.e. the first row of pm
    713   while (pm[1]!=zeilenumbruch)
    714   {
    715     pm=stringdelete(pm,1);
    716   }
    717   pm=stringdelete(pm,1);
    718   // find out how many entries each vector has, namely one more
    719   // than 'spaces' in a row
    720   int i=1;
    721   int s=1;
    722   int z=1;
    723   while (pm[i]!=zeilenumbruch)
    724   {
    725     if (pm[i]==" ")
    726     {
    727       s++;
    728     }
    729     i++;
    730   }
    731   // if we want to have affine coordinates
    732   if (art=="affine")
    733   {
    734     s--; // then there is one column less
    735     // and the entry of the first column (in the first row) has to be removed
    736     while (pm[1]!=" ")
    737     {
    738       pm=stringdelete(pm,1);
    739     }
    740     pm=stringdelete(pm,1);
    741   }
    742   // we add two line breaks at the end in order to have this as
    743   // a stopping criterion
    744   pm=pm+zeilenumbruch+zeilenumbruch;
    745   // we now have to work through each row
    746   for (i=1;i<=size(pm);i++)
    747   {
    748     // if there are two consecutive line breaks we are done
    749     if ((pm[i]==zeilenumbruch) and (pm[i+1]==zeilenumbruch))
    750     {
    751       i=size(pm)+1;
    752     }
    753     else
    754     {
    755       // a line break has to be replaced by a comma
    756       if (pm[i]==zeilenumbruch)
    757       {
    758         z++;
    759         pm[i]=",";
    760         // if we want to have affine coordinates,
    761         // then we have to delete the first entry in each row
    762         if (art=="affine")
    763         {
    764          while (pm[i+1]!=" ")
    765          {
    766            pm=stringdelete(pm,i+1);
    767          }
    768          pm=stringdelete(pm,i+1);
    769         }
    770       }
    771       // a space has to be replaced by a comma
    772       if (pm[i]==" ")
    773       {
    774         pm[i]=",";
    775       }
    776     }
    777   }
    778   // if we have introduced superflous commata at the end, they should be removed
    779   while (pm[size(pm)]==",")
    780   {
    781     pm=stringdelete(pm,size(pm));
    782   }
    783   // since the matrix could be over the rationals,
    784   // we need a ring with rational coefficients
    785   ring zwischering=0,x,lp;
    786   // create the matrix with the elements of pm as entries
    787   execute("matrix mm["+string(z)+"]["+string(s)+"]="+pm+";");
    788   // transform this into an integer matrix
    789   matrix M[1][ncols(mm)]; // takes a row of mm
    790   int cm;  // takes a lowest common multiple
    791   // multiply each row by an integer such that its entries are integers
    792   for (int j=1;j<=nrows(mm);j++)
    793   {
    794     M=mm[j,1..ncols(mm)];
    795     cm=commondenominator(M);
    796     for (i=1;i<=ncols(mm);i++)
    797     {
    798       mm[j,i]=cm*mm[j,i];
    799     }
    800   }
    801   // transform the matrix mm into an integer matrix
    802   execute("intmat im["+string(z)+"]["+string(s)+"]="+string(mm)+";");
    803   return(im);
    804 }
    805 example
    806 {
    807    "EXAMPLE:";
    808    echo=2;
    809    // this is the usual output of some polymake computation
    810    string pm="VERTICES
    811 0 1 3 5/3 1/3 -1 -23/3 -1/3 5/3 1/3 1
    812 0 1 3 -23/3 5/3 1 5/3 1/3 1/3 -1/3 -1
    813 0 1 1 1/3 -1/3 -1 5/3 1/3 -23/3 5/3 3
    814 0 1 1 5/3 -23/3 3 1/3 5/3 -1/3 1/3 -1
    815 0 1 -1 1/3 5/3 3 -1/3 -23/3 1/3 5/3 1
    816 0 1 -1 -1/3 1/3 1 1/3 5/3 5/3 -23/3 3
    817 0 1 -1 1 3 -5 -1 3 -1 1 -1
    818 0 1 -1 -1 -1 -1 1 1 3 3 -5
    819 0 1 -5 3 1 -1 3 -1 1 -1 -1
    820 
    821 ";
    822    intmat PM=polymakeToIntmat(pm,"affine");
    823    // note that the first column has been removed, since we asked for
    824    // affine coordinates, and the denominators have been cleared
    825    print(PM);
    826 }
    827 
    828505///////////////////////////////////////////////////////////////////////////////
    829506/// PROCEDURES USING TOPCOM
    830507///////////////////////////////////////////////////////////////////////////////
    831508
    832 proc triangulations (list polygon)
    833 "USAGE:  triangulations(polygon); list polygon
    834 ASSUME:  polygon is a list of integer vectors of the same size representing
    835          the affine coordinates of the lattice points
     509proc triangulations (list polygon,list #)
     510"USAGE:  triangulations(polygon[,#]); list polygon, list #
     511ASSUME:  polygon is a list of integer vectors of the same size representing 
     512         the affine coordinates of the lattice points 
    836513PURPOSE: the procedure considers the marked polytope given as the convex hull of
    837514         the lattice points and with these lattice points as markings; it then
    838          computes all possible triangulations of this marked polytope
     515         computes all possible triangulations of this marked polytope 
    839516RETURN:  list, each entry corresponds to one triangulation and the ith entry is
    840517               itself a list of integer vectors of size three, where each integer
     
    843520NOTE:- the procedure calls for its computations the program points2triangs
    844521       from the program topcom by Joerg Rambau, Universitaet Bayreuth; it
    845        therefore is necessary that this program is installed in order to use
     522       therefore is necessary that this program is installed in order to use 
    846523       this  procedure; see
    847524@*     http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
    848 @*   - the procedure creates the files /tmp/triangulationsinput and
     525@*   - if you only want to have the regular triangulations the procedure should
     526       be called with the string 'regular' as optional argument
     527@*   - the procedure creates the files /tmp/triangulationsinput and
    849528       /tmp/triangulationsoutput;
    850        the former is used as input for points2triangs and the latter is its
    851        output containing the triangulations of corresponding to points in the
    852        format of points2triangs; if you wish to use this for further
    853        computations with topcom, you have to use the procedure
    854        polymakeKeepTmpFiles in before
    855 @*   - note that an integer i in an integer vector representing a triangle
    856        refers to the ith lattice point, i.e. polygon[i]; this convention is
    857        different from TOPCOM's convention, where i would refer to the i-1st
     529       the former is used as input for points2triangs and the latter is its 
     530       output containing the triangulations of corresponding to points in the 
     531       format of points2triangs; if you wish to use this for further 
     532       computations with topcom, you have to call the procedure with the
     533       string 'keepfiles' as optional argument
     534@*   - note that an integer i in an integer vector representing a triangle 
     535       refers to the ith lattice point, i.e. polygon[i]; this convention is 
     536       different from TOPCOM's convention, where i would refer to the i-1st 
    858537       lattice point
    859538EXAMPLE: example triangulations;   shows an example"
    860539{
    861540  int i,j;
    862   // prepare the input for points2triangs by writing the input polygon in the
     541  // check for optional arguments
     542  int regular,keepfiles;
     543  if (size(#)>0)
     544  {
     545    for (i=1;i<=size(#);i++)
     546    {
     547      if (typeof(#[i])=="string")
     548      {
     549        if (#[i]=="keepfiles")
     550        {
     551          keepfiles=1;
     552        }
     553        if (#[i]=="regular")
     554        {
     555          regular=1;
     556        }
     557      }
     558    }
     559  }
     560  // prepare the input for points2triangs by writing the input polygon in the
    863561  // necessary format
    864562  string spi="[";
     
    875573  write(":w /tmp/triangulationsinput",spi);
    876574  // call points2triangs
    877   system("sh","cd /tmp; points2triangs < triangulationsinput > triangulationsoutput");
     575  if (regular==1) // compute only regular triangulations
     576  {
     577    system("sh","cd /tmp; points2triangs --regular < triangulationsinput > triangulationsoutput");
     578  }
     579  else // compute all triangulations
     580  {
     581    system("sh","cd /tmp; points2triangs < triangulationsinput > triangulationsoutput");
     582  }
    878583  string p2t=read("/tmp/triangulationsoutput"); // takes result of points2triangs
    879   // delete the tmp-files, if polymakekeeptmpfiles is not set
    880   if (defined(polymakekeeptmpfiles)==0)
     584  // delete the tmp-files, if no second argument is given
     585  if (keepfiles==0)
    881586  {
    882587    system("sh","cd /tmp; rm -f triangulationsinput; rm -f triangulationsoutput");
    883588  }
    884   // preprocessing of p2t if points2triangs is version >= 0.15
     589  // preprocessing of p2t if points2triangs is version >= 0.15 
    885590  // brings p2t to the format of version 0.14
    886591  string np2t; // takes the triangulations in Singular format
     
    904609      }
    905610      else
    906       {
     611      {       
    907612        np2t=np2t+p2t[i];
    908613      }
     
    916621  {
    917622    if (np2t[size(np2t)]!=";")
    918     {
     623    {     
    919624      np2t=np2t+p2t[size(p2t)-1]+p2t[size(p2t)];
    920625    }
     
    938643          np2t=np2t+"))";
    939644          i++;
    940         }
     645        }     
    941646        else
    942647        {
     
    953658            else
    954659            {
    955               np2t=np2t+p2t[i];
     660              if (p2t[i]=="[")
     661              {
     662                // in Topcom version 17.4 (and maybe also in earlier versions) the list
     663                // of triangulations is indexed starting with index 0, in Singular
     664                // we have to start with index 1
     665                np2t=np2t+p2t[i]+"1+";
     666              }
     667              else
     668              {
     669                np2t=np2t+p2t[i];
     670              }
    956671            }
    957672          }
     
    962677  list T;
    963678  execute(np2t);
     679  // depending on the version of Topcom, the list T has or has not an entry T[1]
     680  // if it has none, the entry should be removed
     681  while (typeof(T[1])=="none")
     682  {
     683    T=delete(T,1);
     684  }
    964685  // raise each index by one
    965686  for (i=1;i<=size(T);i++)
     
    976697   "EXAMPLE:";
    977698   echo=2;
    978    // the lattice points of the unit square in the plane
     699   // the lattice points of the unit square in the plane 
    979700   list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1);
    980701   // the triangulations of this lattice point configuration are computed
     
    987708proc secondaryPolytope (list polygon,list #)
    988709"USAGE:  secondaryPolytope(polygon[,#]); list polygon, list #
    989 ASSUME:  - polygon is a list of integer vectors of the same size representing
     710ASSUME:  - polygon is a list of integer vectors of the same size representing 
    990711           the affine coordinates of lattice points
    991 @*       - if the triangulations of the corresponding polygon have already been
     712@*       - if the triangulations of the corresponding polygon have already been 
    992713           computed with the procedure triangulations then these can be given as
    993714           a second (optional) argument in order to avoid doing this computation
     
    995716PURPOSE: the procedure considers the marked polytope given as the convex hull of
    996717         the lattice points and with these lattice points as markings; it then
    997          computes the lattice points of the secondary polytope given by this
     718         computes the lattice points of the secondary polytope given by this 
    998719         marked polytope which correspond to the triangulations computed by
    999720         the procedure triangulations
    1000721RETURN:  list, say L, such that:
    1001722@*             L[1] = intmat, each row gives the affine coordinates of a lattice
    1002                       point in the secondary polytope given by the marked polytope
    1003                       corresponding to polygon
     723                      point in the secondary polytope given by the marked
     724                      polytope corresponding to polygon
    1004725@*             L[2] = the list of corresponding triangulations
    1005 NOTE: if the triangluations are not handed over as optional argument the
     726NOTE: if the triangluations are not handed over as optional argument the 
    1006727      procedure calls for its computation of these triangulations the program
    1007       points2triangs from the program topcom by Joerg Rambau, Universitaet
    1008       Bayreuth; it therefore is necessary that this program is installed in
     728      points2triangs from the program topcom by Joerg Rambau, Universitaet 
     729      Bayreuth; it therefore is necessary that this program is installed in 
    1009730      order to use this procedure; see
    1010731@*    http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
     
    1022743  int i,j,k,l;
    1023744  intmat N[2][2]; // is used to compute areas of triangles
    1024   intvec vertex;  // stores a point in the secondary polytope as
     745  intvec vertex;  // stores a point in the secondary polytope as 
    1025746                  // intermediate result
    1026747  int eintrag;
    1027748  int halt;
    1028   intmat secpoly[size(triangs)][size(polygon)];   // stores all lattice points
     749  intmat secpoly[size(triangs)][size(polygon)];   // stores all lattice points 
    1029750                                                  // of the secondary polytope
    1030   // consider each triangulation and compute the corresponding point
     751  // consider each triangulation and compute the corresponding point 
    1031752  // in the secondary polytope
    1032753  for (i=1;i<=size(triangs);i++)
    1033754  {
    1034     // for each triangulation we have to compute the coordinates
     755    // for each triangulation we have to compute the coordinates 
    1035756    // corresponding to each marked point
    1036757    for (j=1;j<=size(polygon);j++)
    1037758    {
    1038759      eintrag=0;
    1039       // for each marked point we have to consider all triangles in the
     760      // for each marked point we have to consider all triangles in the 
    1040761      // triangulation which involve this particular point
    1041762      for (k=1;k<=size(triangs[i]);k++)
     
    1059780    secpoly[i,1..size(polygon)]=vertex;
    1060781  }
    1061   return(list(secpoly,triangs));
     782  return(list(secpoly,triangs));         
    1062783}
    1063784example
     
    1081802proc secondaryFan (list polygon,list #)
    1082803"USAGE:  secondaryFan(polygon[,#]); list polygon, list #
    1083 ASSUME:  - polygon is a list of integer vectors of the same size representing
     804ASSUME:  - polygon is a list of integer vectors of the same size representing 
    1084805           the affine coordinates of lattice points
    1085 @*       - if the triangulations of the corresponding polygon have already been
    1086            computed with the procedure triangulations then these can be given
    1087            as a second (optional) argument in order to avoid doing this
     806@*       - if the triangulations of the corresponding polygon have already been 
     807           computed with the procedure triangulations then these can be given 
     808           as a second (optional) argument in order to avoid doing this 
    1088809           computation again
    1089810PURPOSE: the procedure considers the marked polytope given as the convex hull of
    1090811         the lattice points and with these lattice points as markings; it then
    1091          computes the lattice points of the secondary polytope given by this
     812         computes the lattice points of the secondary polytope given by this 
    1092813         marked polytope which correspond to the triangulations computed by
    1093814         the procedure triangulations
    1094 RETURN:  list, the ith entry of L[1] contains information about the ith cone in
    1095                the secondary fan of the polygon, i.e. the cone dual to the
     815RETURN:  list, the ith entry of L[1] contains information about the ith cone in 
     816               the secondary fan of the polygon, i.e. the cone dual to the 
    1096817               ith vertex of the secondary polytope
    1097 @*             L[1][i][1] = integer matrix representing the inequalities which
     818@*             L[1][i][1] = integer matrix representing the inequalities which 
    1098819                            describe the cone dual to the ith vertex
    1099 @*             L[1][i][2] = a list which contains the inequalities represented
     820@*             L[1][i][2] = a list which contains the inequalities represented 
    1100821                            by L[1][i][1] as a list of strings, where we use the
    1101822                            variables x(1),...,x(n)
    1102823@*             L[1][i][3] = only present if 'er' is set to 1; in that case it is
    1103                             an interger matrix whose rows are the extreme rays
     824                            an interger matrix whose rows are the extreme rays 
    1104825                            of the cone
    1105 @*             L[2] = is an integer matrix whose rows span the linearity space
    1106                       of the fan, i.e. the linear space which is contained in
     826@*             L[2] = is an integer matrix whose rows span the linearity space 
     827                      of the fan, i.e. the linear space which is contained in 
    1107828                      each cone
    1108 @*             L[3] = the secondary polytope in the format of the procedure
     829@*             L[3] = the secondary polytope in the format of the procedure 
    1109830                      polymakePolytope
    1110 @*             L[4] = the list of triangulations corresponding to the vertices
     831@*             L[4] = the list of triangulations corresponding to the vertices 
    1111832                      of the secondary polytope
    1112833NOTE:- the procedure calls for its computation polymake by Ewgenij Gawrilow,
    1113834       TU Berlin and Michael Joswig, so it only works if polymake is installed;
    1114835       see http://www.math.tu-berlin.de/polymake/
    1115 @*   - in the optional argument # it is possible to hand over other names for
    1116        the variables to be used -- be careful, the format must be correct
    1117        which is not tested, e.g. if you want the variable names to be
     836@*   - in the optional argument # it is possible to hand over other names for 
     837       the variables to be used -- be careful, the format must be correct and
     838       that is not tested, e.g. if you want the variable names to be
    1118839       u00,u10,u01,u11 then you must hand over the string 'u11,u10,u01,u11'
    1119 @*   - if the triangluations are not handed over as optional argument the
    1120        procedure calls for its computation of these triangulations the program
    1121        points2triangs from the program topcom by Joerg Rambau, Universitaet
    1122        Bayreuth; it therefore is necessary that this program is installed in
     840@*   - if the triangluations are not handed over as optional argument the 
     841       procedure calls for its computation of these triangulations the program 
     842       points2triangs from the program topcom by Joerg Rambau, Universitaet 
     843       Bayreuth; it therefore is necessary that this program is installed in 
    1123844       order to use this procedure; see
    1124845@*     http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
     
    1132853  {
    1133854    list triang=#[1];
    1134   }
     855  } 
    1135856  list sp=secondaryPolytope(polygon,triang);
    1136857  list spp=polymakePolytope(sp[1]);
     
    1169890proc cycleLength (list boundary,intvec interior)
    1170891"USAGE:  cycleLength(boundary,interior); list boundary, intvec interior
    1171 ASSUME:  boundary is a list of integer vectors describing a cycle in some
    1172          convex lattice polygon around the lattice point interior ordered
     892ASSUME:  boundary is a list of integer vectors describing a cycle in some 
     893         convex lattice polygon around the lattice point interior ordered 
    1173894         clock wise
    1174895RETURN:  string, the cycle length of the corresponding cycle in the dual
     
    1177898{
    1178899  int j;
    1179   // create a ring whose variables are indexed by the points in
     900  // create a ring whose variables are indexed by the points in 
    1180901  // boundary resp. by interior
    1181902  string rst="ring cyclering=0,(u"+string(interior[1])+string(interior[2]);
     
    1215936   // interior is a lattice point in the interior of this lattice polygon
    1216937   intvec interior=1,1;
    1217    // compute the general cycle length of a cycle of the corresponding cycle
     938   // compute the general cycle length of a cycle of the corresponding cycle 
    1218939   // in the dual tropical curve, note that (0,1) and (2,1) do not contribute
    1219940   cycleLength(boundary,interior);
     
    1224945proc splitPolygon (list markings)
    1225946"USAGE:  splitPolygon (markings);  markings list
    1226 ASSUME:  markings is a list of integer vectors representing lattice points in
    1227          the plane which we consider as the marked points of the convex lattice
     947ASSUME:  markings is a list of integer vectors representing lattice points in 
     948         the plane which we consider as the marked points of the convex lattice 
    1228949         polytope spanned by them
    1229 PURPOSE: split the marked points in the vertices, the points on the facets
     950PURPOSE: split the marked points in the vertices, the points on the facets 
    1230951         which are not vertices, and the interior points
    1231952RETURN:  list, L consisting of three lists
     
    1233954@*                       L[1][i][1] = intvec, the coordinates of the ith vertex
    1234955@*                       L[1][i][2] = int, the position of L[1][i][1] in markings
    1235 @*             L[2][i] : represents the lattice points on the facet of the
    1236                          polygon with endpoints L[1][i] and L[1][i+1]
     956@*             L[2][i] : represents the lattice points on the facet of the 
     957                         polygon with endpoints L[1][i] and L[1][i+1] 
    1237958                         (i considered modulo size(L[1]))
    1238 @*                       L[2][i][j][1] = intvec, the coordinates of the jth
     959@*                       L[2][i][j][1] = intvec, the coordinates of the jth 
    1239960                                                 lattice point on that facet
    1240 @*                       L[2][i][j][2] = int, the position of L[2][i][j][1]
     961@*                       L[2][i][j][2] = int, the position of L[2][i][j][1] 
    1241962                                              in markings
    1242 @*             L[3]    : represents the interior lattice points of the polygon
     963@*             L[3]    : represents the interior lattice points of the polygon 
    1243964@*                       L[3][i][1] = intvec, coordinates of ith interior point
    1244965@*                       L[3][i][2] = int, the position of L[3][i][1] in markings
     
    1251972  vert[1]=pb[2];
    1252973  int i,j,k;      // indices
    1253   list boundary;  // stores the points on the facets of the
     974  list boundary;  // stores the points on the facets of the 
    1254975                  // polygon which are not vertices
    1255   // append to the boundary points as well as to the vertices
     976  // append to the boundary points as well as to the vertices 
    1256977  // the first vertex a second time
    1257978  pb[1]=pb[1]+list(pb[1][1]);
     
    1278999  // store the information on the boundary in vert[2]
    12791000  vert[2]=boundary;
    1280   // find the remaining points in the input which are not on
     1001  // find the remaining points in the input which are not on 
    12811002  // the boundary by checking
    12821003  // for each point in markings if it is contained in pb[1]
     
    12951016  // store the interior points in vert[3]
    12961017  vert[3]=interior;
    1297   // add to each point in vert the index which it gets from
     1018  // add to each point in vert the index which it gets from 
    12981019  // its position in the input markings;
    12991020  // do so for ver[1]
     
    13291050    }
    13301051    vert[3][i]=list(vert[3][i],j);
    1331   }
     1052  } 
    13321053  return(vert);
    13331054}
     
    13361057   "EXAMPLE:";
    13371058   echo=2;
    1338    // the lattice polygon spanned by the points (0,0), (3,0) and (0,3)
     1059   // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 
    13391060   // with all integer points as markings
    13401061   list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),
     
    13561077proc eta (list triang,list polygon)
    13571078"USAGE:  eta(triang,polygon);  triang, polygon list
    1358 ASSUME:  polygon has the format of the output of splitPolygon, i.e. it is a
    1359          list with three entries describing a convex lattice polygon in the
     1079ASSUME:  polygon has the format of the output of splitPolygon, i.e. it is a 
     1080         list with three entries describing a convex lattice polygon in the 
    13601081         following way:
    1361 @*       polygon[1] : is a list of lists; for each i the entry polygon[1][i][1]
    1362                       is a lattice point which is a vertex of the lattice
     1082@*       polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] 
     1083                      is a lattice point which is a vertex of the lattice 
    13631084                      polygon, and polygon[1][i][2] is an integer assigned to
    13641085                      this lattice point as identifying index
    1365 @*       polygon[2] : is a list of lists; for each vertex of the polygon,
    1366                       i.e. for each entry in polygon[1], it contains a list
    1367                       polygon[2][i], which contains the lattice points on the
    1368                       facet with endpoints polygon[1][i] and polygon[1][i+1]
     1086@*       polygon[2] : is a list of lists; for each vertex of the polygon, 
     1087                      i.e. for each entry in polygon[1], it contains a list 
     1088                      polygon[2][i], which contains the lattice points on the 
     1089                      facet with endpoints polygon[1][i] and polygon[1][i+1] 
    13691090                      - i considered mod size(polygon[1]);
    1370                       each such lattice point contributes an entry
     1091                      each such lattice point contributes an entry 
    13711092                      polygon[2][i][j][1] which is an integer
    1372                       vector giving the coordinate of the lattice point and an
     1093                      vector giving the coordinate of the lattice point and an 
    13731094                      entry polygon[2][i][j][2] which is the identifying index
    1374 @*       polygon[3] : is a list of lists, where each entry corresponds to a
    1375                       lattice point in the interior of the polygon, with
     1095@*       polygon[3] : is a list of lists, where each entry corresponds to a 
     1096                      lattice point in the interior of the polygon, with 
    13761097                      polygon[3][j][1] being the coordinates of the point
    13771098                      and polygon[3][j][2] being the identifying index;
    1378 @*       triang is a list of integer vectors all of size three describing a
    1379          triangulation of the polygon described by polygon; if an entry of
    1380          triang is the vector (i,j,k) then the triangle is built from the vertices
     1099@*       triang is a list of integer vectors all of size three describing a 
     1100         triangulation of the polygon described by polygon; if an entry of 
     1101         triang is the vector (i,j,k) then the triangle is built by the vertices
    13811102         with indices i, j and k
    1382 RETURN:  intvec, the integer vector eta describing that vertex of the Newton
    1383                  polytope discriminant of the polygone whose dual cone in the
    1384                  Groebner fan contains the cone of the secondary fan of the
     1103RETURN:  intvec, the integer vector eta describing that vertex of the Newton 
     1104                 polytope discriminant of the polygone whose dual cone in the 
     1105                 Groebner fan contains the cone of the secondary fan of the 
    13851106                 polygon corresponding to the given triangulation
    1386 NOTE:  for a better description of eta see Gelfand, Kapranov,
     1107NOTE:  for a better description of eta see Gelfand, Kapranov, 
    13871108       Zelevinski: Discriminants, Resultants and multidimensional Determinants.
    13881109       Chapter 10.
     
    13901111{
    13911112  int i,j,k,l,m,n; // index variables
    1392   list ordpolygon;   // stores the lattice points in the order
     1113  list ordpolygon;   // stores the lattice points in the order 
    13931114                     // used in the triangulation
    13941115  list triangarea; // stores the areas of the triangulations
     
    14161137  for (i=1;i<=size(triang);i++)
    14171138  {
    1418     // Note that the ith lattice point in orderedpolygon has the
     1139    // Note that the ith lattice point in orderedpolygon has the 
    14191140    // number i-1 in the triangulation!
    14201141    N=ordpolygon[triang[i][1]]-ordpolygon[triang[i][2]],ordpolygon[triang[i][1]]-ordpolygon[triang[i][3]];
     
    14221143  }
    14231144  intvec ETA;        // stores the eta_ij
    1424   int etaij;         // stores the part of eta_ij during computations
     1145  int etaij;         // stores the part of eta_ij during computations 
    14251146                     // which comes from triangle areas
    1426   int seitenlaenge;  // stores the part of eta_ij during computations
     1147  int seitenlaenge;  // stores the part of eta_ij during computations 
    14271148                     // which comes from boundary facets
    14281149  list seiten;       // stores the lattice points on facets of the polygon
    14291150  intvec v;          // used to compute a facet length
    1430   // 3) store first in seiten[i] all lattice points on the facet
     1151  // 3) store first in seiten[i] all lattice points on the facet 
    14311152  //    connecting the ith vertex,
    1432   //    i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1],
     1153  //    i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], 
    14331154  //    where we replace i+1
    14341155  //    1 if i=size(polygon[1]);
    1435   //    then append the last entry of seiten once more at the very
     1156  //    then append the last entry of seiten once more at the very 
    14361157  //    beginning of seiten, so
    14371158  //    that the index is shifted by one
     
    14591180      if ((polygon[1][j][2]==triang[k][1]) or (polygon[1][j][2]==triang[k][2]) or (polygon[1][j][2]==triang[k][3]))
    14601181      {
    1461         // ... if so, add the area of the triangle to etaij
     1182        // ... if so, add the area of the triangle to etaij 
    14621183        etaij=etaij+triangarea[k];
    1463         // then check if that triangle has a facet which is contained
    1464         // in one of the
     1184        // then check if that triangle has a facet which is contained 
     1185        // in one of the 
    14651186        // two facets of the polygon which are adjecent to the given vertex ...
    14661187        // these two facets are seiten[j] and seiten[j+1]
     
    14761197              if ((seiten[n][l][2]==triang[k][m]) and (seiten[n][l][2]!=polygon[1][j][2]))
    14771198              {
    1478                 // if so, then compute the vector pointing from this
     1199                // if so, then compute the vector pointing from this 
    14791200                // lattice point to the vertex
    14801201                v=polygon[1][j][1]-seiten[n][l][1];
    1481                 // and the lattice length of this vector has to be
     1202                // and the lattice length of this vector has to be 
    14821203                // subtracted from etaij
    14831204                etaij=etaij-abs(gcd(v[1],v[2]));
     
    14911212    ETA[polygon[1][j][2]]=etaij;
    14921213  }
    1493   // 5) compute the eta_ij for all lattice points on the facets
     1214  // 5) compute the eta_ij for all lattice points on the facets 
    14941215  //    of the polygon which are not vertices, these are the
    14951216  //    lattice points in polygon[2][1] to polygon[2][size(polygon[1])]
     
    14971218  {
    14981219    for (j=1;j<=size(polygon[2][i]);j++)
    1499     {
     1220    {     
    15001221      // initialise etaij
    15011222      etaij=0;
     
    15081229        if ((polygon[2][i][j][2]==triang[k][1]) or (polygon[2][i][j][2]==triang[k][2]) or (polygon[2][i][j][2]==triang[k][3]))
    15091230        {
    1510           // ... if so, add the area of the triangle to etaij
     1231          // ... if so, add the area of the triangle to etaij 
    15111232          etaij=etaij+triangarea[k];
    1512           // then check if that triangle has a facet which is contained in the
     1233          // then check if that triangle has a facet which is contained in the 
    15131234          // facet of the polygon which contains the lattice point in question,
    15141235          // this is the facet seiten[i+1];
     
    15181239            // ... and for each lattice point in the triangle ...
    15191240            for (m=1;m<=size(triang[k]);m++)
    1520             {
     1241            {           
    15211242              // ... if they coincide and are not the vertex itself ...
    15221243              if ((seiten[i+1][l][2]==triang[k][m]) and (seiten[i+1][l][2]!=polygon[2][i][j][2]))
    15231244              {
    1524                 // if so, then compute the vector pointing from
     1245                // if so, then compute the vector pointing from 
    15251246                // this lattice point to the vertex
    15261247                v=polygon[2][i][j][1]-seiten[i+1][l][1];
    1527                 // and the lattice length of this vector contributes
     1248                // and the lattice length of this vector contributes 
    15281249                // to seitenlaenge
    15291250                seitenlaenge=seitenlaenge+abs(gcd(v[1],v[2]));
     
    15331254        }
    15341255      }
    1535       // if the lattice point was a vertex of any triangle
     1256      // if the lattice point was a vertex of any triangle 
    15361257      // in the triangulation ...
    15371258      if (etaij!=0)
     
    15581279      if ((polygon[3][j][2]==triang[k][1]) or (polygon[3][j][2]==triang[k][2]) or (polygon[3][j][2]==triang[k][3]))
    15591280      {
    1560         // ... if so, add the area of the triangle to etaij
     1281        // ... if so, add the area of the triangle to etaij 
    15611282        etaij=etaij+triangarea[k];
    15621283      }
     
    15711292   "EXAMPLE:";
    15721293   echo=2;
    1573    // the lattice polygon spanned by the points (0,0), (3,0) and (0,3)
     1294   // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 
    15741295   // with all integer points as markings
    15751296   list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),
     
    15781299   // split the polygon in its vertices, its facets and its interior points
    15791300   list sp=splitPolygon(polygon);
    1580    // define a triangulation by connecting the only interior point
     1301   // define a triangulation by connecting the only interior point 
    15811302   //        with the vertices
    15821303   list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,5,10);
     
    15841305   eta(triang,sp);
    15851306}
    1586 
     1307 
    15871308/////////////////////////////////////////////////////////////////////////////
    15881309
    15891310proc findOrientedBoundary (list polygon)
    15901311"USAGE: findOrientedBoundary(polygon); polygon list
    1591 ASSUME: polygon is a list of integer vectors defining integer lattice points
     1312ASSUME: polygon is a list of integer vectors defining integer lattice points 
    15921313        in the plane
    15931314RETURN: list l with the following interpretation
    1594 @*            l[1] = list of integer vectors such that the polygonal path
    1595                      defined by these is the boundary of the convex hull of
     1315@*            l[1] = list of integer vectors such that the polygonal path 
     1316                     defined by these is the boundary of the convex hull of 
    15961317                     the lattice points in polygon
    15971318@*            l[2] = list, the redundant points in l[1] have been removed
     
    16111332  }
    16121333  // check is the polygon is only a line segment given by more than two points;
    1613   // for this first compute sum of the absolute values of the determinants
     1334  // for this first compute sum of the absolute values of the determinants 
    16141335  // of the matrices whose
    1615   // rows are the vectors pointing from the first to the second point
     1336  // rows are the vectors pointing from the first to the second point 
    16161337  // and from the
    1617   // the first point to the ith point for i=3,...,size(polygon);
     1338  // the first point to the ith point for i=3,...,size(polygon); 
    16181339  // if this sum is zero
    16191340  // then the polygon is a line segment and we have to find its end points
     
    16281349    intmat laenge[size(polygon)][size(polygon)];
    16291350    intvec mp;
    1630     //   for this collect first all vectors pointing from one lattice
     1351    //   for this collect first all vectors pointing from one lattice 
    16311352    //   point to the next,
    16321353    //   compute their pairwise angles and their lengths
    16331354    for (i=1;i<=size(polygon)-1;i++)
    1634     {
     1355    {     
    16351356      for (j=i+1;j<=size(polygon);j++)
    16361357      {
     
    16561377    polygon=sortlistbyintvec(polygon,abstand);
    16571378    return(list(polygon,endpoints));
    1658   }
     1379  } 
    16591380  ///////////////////////////////////////////////////////////////
    16601381  list orderedvertices;  // stores the vertices in an ordered way
    1661   list minimisedorderedvertices;  // stores the vertices in an ordered way;
     1382  list minimisedorderedvertices;  // stores the vertices in an ordered way; 
    16621383                                  // redundant ones removed
    1663   list comparevertices; // stores vertices which should be compared to
     1384  list comparevertices; // stores vertices which should be compared to 
    16641385                        // the testvertex
    16651386  orderedvertices[1]=polygon[1]; // set the starting vertex
    16661387  minimisedorderedvertices[1]=polygon[1]; // set the starting vertex
    16671388  intvec testvertex=polygon[1];  //vertex to which the others have to be compared
    1668   intvec startvertex=polygon[1]; // keep the starting vertex to test,
     1389  intvec startvertex=polygon[1]; // keep the starting vertex to test, 
    16691390                                 // when the end is reached
    16701391  int endtest;                   // is set to one, when the end is reached
    1671   int startvertexfound;// is 1, once for some testvertex a candidate
    1672                        // for the next vertex has been found
     1392  int startvertexfound;// is 1, once for some testvertex a candidate 
     1393                       // for the next vertex has been found 
    16731394  polygon=delete(polygon,1);    // delete the testvertex
    16741395  intvec v,w;
    16751396  int l=1;  // counts the vertices
    1676   // the basic idea is that a vertex can be
     1397  // the basic idea is that a vertex can be 
    16771398  // the next one on the boundary if all other vertices
    1678   // lie to the right of the vector v pointing
     1399  // lie to the right of the vector v pointing 
    16791400  // from the testvertex to this one; this can be tested
    1680   // by checking if the determinant of the 2x2-matrix
     1401  // by checking if the determinant of the 2x2-matrix 
    16811402  // with first column v and second column the vector w,
    1682   // pointing from the testvertex to the new vertex,
     1403  // pointing from the testvertex to the new vertex, 
    16831404  // is non-positive; if this is the case for all
    1684   // new vertices, then the one in consideration is
     1405  // new vertices, then the one in consideration is 
    16851406  // a possible choice for the next vertex on the boundary
    1686   // and it is stored in naechste; we can then order
     1407  // and it is stored in naechste; we can then order 
    16871408  // the candidates according to their distance from
    16881409  // the testvertex; then they occur on the boundary in that order!
     
    16961417      v=polygon[i]-testvertex; // points from the testvertex to the ith vertex
    16971418      comparevertices=delete(polygon,i); // we needn't compare v to itself
    1698       // we should compare v to the startvertex-testvertex;
     1419      // we should compare v to the startvertex-testvertex; 
    16991420      // in the first calling of the loop
    1700       // this is irrelevant since the difference will be zero;
     1421      // this is irrelevant since the difference will be zero; 
    17011422      // however, later on it will
    1702       // be vital, since we delete the vertices
     1423      // be vital, since we delete the vertices 
    17031424      // which we have already tested from the list
    1704       // of all vertices, and when all vertices
     1425      // of all vertices, and when all vertices 
    17051426      // on the boundary have been found we would
    1706       // therefore find a vertex in the interior
     1427      // therefore find a vertex in the interior 
    17071428      // as candidate; but always testing against
    17081429      // the starting vertex, this cannot happen
    1709       comparevertices[size(comparevertices)+1]=startvertex;
     1430      comparevertices[size(comparevertices)+1]=startvertex; 
    17101431      for (j=1;(j<=size(comparevertices)) and (d<=0);j++)
    17111432      {
     
    17151436        d=det(D);
    17161437      }
    1717       if (d<=0) // if all determinants are non-positive,
     1438      if (d<=0) // if all determinants are non-positive, 
    17181439      { // then the ith vertex is a candidate
    17191440        naechste[k]=list(polygon[i],i,scalarproduct(v,v));// we store the vertex,
     
    17231444    }
    17241445    if (size(naechste)>0) // then a candidate for the next vertex has been found
    1725     {
     1446    {     
    17261447      startvertexfound=1; // at least once a candidate has been found
    1727       naechste=sortlist(naechste,3);  // we order the candidates according
     1448      naechste=sortlist(naechste,3);  // we order the candidates according 
    17281449                                      // to their distance from testvertex;
    1729       for (j=1;j<=size(naechste);j++) // then we store them in this
     1450      for (j=1;j<=size(naechste);j++) // then we store them in this 
    17301451      { // order in orderedvertices
    17311452        l++;
    17321453        orderedvertices[l]=naechste[j][1];
    17331454      }
    1734       testvertex=naechste[size(naechste)][1];  // we store the last one as
     1455      testvertex=naechste[size(naechste)][1];  // we store the last one as 
    17351456                                               // next testvertex;
    17361457      // store the next corner of NSD
    1737       minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex;
    1738       naechste=sortlist(naechste,2); // then we reorder the vertices
     1458      minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; 
     1459      naechste=sortlist(naechste,2); // then we reorder the vertices 
    17391460                                     // according to their position
    17401461      for (j=size(naechste);j>=1;j--) // and we delete them from the vertices
     
    17431464      }
    17441465    }
    1745     else // that means either that the vertex was inside the polygon,
    1746     {    // or that we have reached the last vertex on the boundary
     1466    else // that means either that the vertex was inside the polygon, 
     1467    {    // or that we have reached the last vertex on the boundary 
    17471468         // of the polytope
    1748       if (startvertexfound==0) // the vertex was in the interior;
     1469      if (startvertexfound==0) // the vertex was in the interior; 
    17491470      { // we delete it and start all over again
    1750         orderedvertices[1]=polygon[1];
    1751         minimisedorderedvertices[1]=polygon[1];
     1471        orderedvertices[1]=polygon[1]; 
     1472        minimisedorderedvertices[1]=polygon[1]; 
    17521473        testvertex=polygon[1];
    17531474        startvertex=polygon[1];
    17541475        polygon=delete(polygon,1);
    17551476      }
    1756       else // we have reached the last vertex on the boundary of
     1477      else // we have reached the last vertex on the boundary of 
    17571478      { // the polytope and can stop
    17581479        endtest=1;
     
    17611482    kill naechste;
    17621483  }
    1763   // test if the first vertex in minimisedorderedvertices
     1484  // test if the first vertex in minimisedorderedvertices 
    17641485  // is on the same line with the second and
    1765   // the last, i.e. if we started our search in the
     1486  // the last, i.e. if we started our search in the 
    17661487  // middle of a face; if so, delete it
    17671488  v=minimisedorderedvertices[2]-minimisedorderedvertices[1];
     
    17721493    minimisedorderedvertices=delete(minimisedorderedvertices,1);
    17731494  }
    1774   // test if the first vertex in minimisedorderedvertices
     1495  // test if the first vertex in minimisedorderedvertices 
    17751496  // is on the same line with the two
    1776   // last ones, i.e. if we started our search at the end of a face;
     1497  // last ones, i.e. if we started our search at the end of a face; 
    17771498  // if so, delete it
    17781499  v=minimisedorderedvertices[size(minimisedorderedvertices)-1]-minimisedorderedvertices[1];
     
    18061527proc cyclePoints (list triang,list points,int pt)
    18071528"USAGE:      cyclePoints(triang,points,pt)  triang,points list, pt int
    1808 ASSUME:      - points is a list of integer vectors describing the lattice
     1529ASSUME:      - points is a list of integer vectors describing the lattice 
    18091530               points of a marked polygon;
    1810 @*           - triang is a list of integer vectors describing a triangulation
    1811                of the marked polygon in the sense that an integer vector of
    1812                the form (i,j,k) describes the triangle formed by polygon[i],
     1531@*           - triang is a list of integer vectors describing a triangulation 
     1532               of the marked polygon in the sense that an integer vector of 
     1533               the form (i,j,k) describes the triangle formed by polygon[i], 
    18131534               polygon[j] and polygon[k];
    1814 @*           - pt is an integer between 1 and size(points), singling out a
     1535@*           - pt is an integer between 1 and size(points), singling out a 
    18151536               lattice point among the marked points
    1816 PURPOSE:     consider the convex lattice polygon, say P, spanned by all lattice
    1817              points in points which in the triangulation triang are connected
    1818              to the point points[pt]; the procedure computes all marked points
     1537PURPOSE:     consider the convex lattice polygon, say P, spanned by all lattice 
     1538             points in points which in the triangulation triang are connected 
     1539             to the point points[pt]; the procedure computes all marked points 
    18191540             in points which lie on the boundary of that polygon, ordered
    18201541             clockwise
    1821 RETURN:      list, of integer vectors which are the coordinates of the lattice
    1822                    points on the boundary of the above mentioned polygon P, if
    1823                    this polygon is not the empty set (that would be the case if
    1824                    points[pt] is not a vertex of any triangle in the
     1542RETURN:      list, of integer vectors which are the coordinates of the lattice 
     1543                   points on the boundary of the above mentioned polygon P, if 
     1544                   this polygon is not the empty set (that would be the case if 
     1545                   points[pt] is not a vertex of any triangle in the 
    18251546                   triangulation); otherwise return the empty list
    18261547EXAMPLE:     example cyclePoints;   shows an example"
    18271548{
    18281549  int i,j; // indices
    1829   list v;  // saves the indices of lattice points connected to the
     1550  list v;  // saves the indices of lattice points connected to the 
    18301551           // interior point in the triangulation
    18311552  // save all points in triangulations containing pt in v
     
    18631584    pts[i]=points[v[i]];
    18641585  }
    1865   // consider the convex polytope spanned by the points in pts,
     1586  // consider the convex polytope spanned by the points in pts, 
    18661587  // find the points on the
    18671588  // boundary and order them clockwise
     
    18721593   "EXAMPLE:";
    18731594   echo=2;
    1874    // the lattice polygon spanned by the points (0,0), (3,0) and (0,3)
     1595   // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 
    18751596   // with all integer points as markings
    18761597   list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),
    18771598               intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2),
    18781599               intvec(0,2),intvec(0,3);
    1879    // define a triangulation
     1600   // define a triangulation 
    18801601   list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10),
    18811602               intvec(1,8,9),intvec(1,2,8);
     
    18891610"USAGE:  latticeArea(polygon);   polygon list
    18901611ASSUME:  polygon is a list of integer vectors in the plane
    1891 RETURN:  int, the lattice area of the convex hull of the lattice points in
     1612RETURN:  int, the lattice area of the convex hull of the lattice points in 
    18921613              polygon, i.e. twice the Euclidean area
    18931614EXAMPLE: example polygonlatticeArea;   shows an example"
     
    19181639proc picksFormula (list polygon)
    19191640"USAGE:  picksFormula(polygon);   polygon list
    1920 ASSUME:  polygon is a list of integer vectors in the plane and consider their
    1921          convex hull C
    1922 RETURN:  list, L of three integersthe
     1641ASSUME:  polygon is a list of integer vectors in the plane and consider their 
     1642         convex hull C 
     1643RETURN:  list, L of three integersthe 
    19231644@*             L[1] : the lattice area of C, i.e. twice the Euclidean area
    19241645@*             L[2] : the number of lattice points on the boundary of C
     
    19451666    bdpts=bdpts+abs(gcd(edge[1],edge[2]));
    19461667  }
    1947   // Pick's formula says that the lattice area A, the number g of interior
     1668  // Pick's formula says that the lattice area A, the number g of interior 
    19481669  // points and
    19491670  // the number b of boundary points are connected by the formula: A=b+2g-2
     
    19721693proc ellipticNF (list polygon)
    19731694"USAGE:  ellipticNF(polygon);   polygon list
    1974 ASSUME:  polygon is a list of integer vectors in the plane such that their
    1975          convex hull C has precisely one interior lattice point, i.e. C is the
     1695ASSUME:  polygon is a list of integer vectors in the plane such that their 
     1696         convex hull C has precisely one interior lattice point; i.e. C is the
    19761697         Newton polygon of an elliptic curve
    1977 PURPOSE: compute the normal form of the polygon with respect to the unimodular
     1698PURPOSE: compute the normal form of the polygon with respect to the unimodular 
    19781699         affine transformations T=A*x+v; there are sixteen different normal forms
    1979          (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons
    1980                    and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3,
     1700         (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons 
     1701                   and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3, 
    19811702                   238--250.)
    19821703RETURN:  list, L such that
    1983 @*             L[1] : list whose entries are the vertices of the normal form of
     1704@*             L[1] : list whose entries are the vertices of the normal form of 
    19841705                      the polygon
    19851706@*             L[2] : the matrix A of the unimodular transformation
    19861707@*             L[3] : the translation vector v of the unimodular transformation
    1987 @*             L[4] : list such that the ith entry is the image of polygon[i]
     1708@*             L[4] : list such that the ith entry is the image of polygon[i] 
    19881709                      under the unimodular transformation T
    19891710EXAMPLE: example ellipticNF;   shows an example"
     
    19911712  int i;            // index
    19921713  intvec edge;      // stores the vector of an edge
    1993   intvec boundary;  // stores lattice lengths of the edges of the Newton cylce
     1714  intvec boundary;  // stores lattice lengths of the edges of the Newton cycle
    19941715  // find the vertices of the Newton cycle and order it clockwise
    19951716  list pg=findOrientedBoundary(polygon)[2];
     
    20171738  intvec trans;    // stores the vector by which we have to translate the polygon
    20181739  intmat A[2][2];  // stores the matrix by which we have to transform the polygon
    2019   matrix M[3][3];  // stores the projective coordinates of the points
     1740  matrix M[3][3];  // stores the projective coordinates of the points 
    20201741                   // which are to be transformed
    2021   matrix N[3][3];  // stores the projective coordinates of the points to
     1742  matrix N[3][3];  // stores the projective coordinates of the points to 
    20221743                   // which M is to be transformed
    2023   intmat T[3][3];  // stores the unimodular affine transformation in
     1744  intmat T[3][3];  // stores the unimodular affine transformation in 
    20241745                   // projective form
    20251746  // add the second point of pg once again at the end
    20261747  pg=insert(pg,pg[2],size(pg));
    2027   // if there is only one edge which has the maximal number of lattice points,
     1748  // if there is only one edge which has the maximal number of lattice points, 
    20281749  // then M should be:
    20291750  M=pg[max],1,pg[max+1],1,pg[max+2],1;
     
    21151836    M=pg[max],1,pg[max+1],1,pg[max+2],1;
    21161837    // the orientation of the polygon matters
    2117     A=pg[max-1]-pg[max],pg[max+1]-pg[max];
     1838    A=pg[max-1]-pg[max],pg[max+1]-pg[max];   
    21181839    if (det(A)==4)
    21191840    {
     
    21641885    {
    21651886      max++;
    2166     }
     1887    }   
    21671888    M=pg[max],1,pg[max+1],1,pg[max+2],1;
    21681889    N=0,1,1,1,2,1,2,1,1;
     
    22271948   // the vertices of the normal form are
    22281949   nf[1];
    2229    // it has been transformed by the unimodular affine transformation A*x+v
     1950   // it has been transformed by the unimodular affine transformation A*x+v 
    22301951   // with matrix A
    22311952   nf[2];
     
    22441965"USAGE:  ellipticNFDB(n[,#]);   n int, # list
    22451966ASSUME:  n is an integer between 1 and 16
    2246 PURPOSE: this is a database storing the 16 normal forms of planar polygons with
     1967PURPOSE: this is a database storing the 16 normal forms of planar polygons with 
    22471968         precisely one interior point up to unimodular affine transformations
    2248 @*       (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons
     1969@*       (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons 
    22491970                   and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3,
    22501971                   238--250.)
    22511972RETURN:  list, L such that
    2252 @*             L[1] : list whose entries are the vertices of the nth normal form
    2253 @*             L[2] : list whose entries are all the lattice points of the
    2254                       nth normal form
    2255 @*             L[3] : only present if the optional parameter # is present, and
    2256                       then it is a polynomial in the variables (x,y) whose
     1973@*             L[1] : list whose entries are the vertices of the nth normal form 
     1974@*             L[2] : list whose entries are all the lattice points of the 
     1975                      nth normal form 
     1976@*             L[3] : only present if the optional parameter # is present, and 
     1977                      then it is a polynomial in the variables (x,y) whose 
    22571978                      Newton polygon is the nth normal form
    2258 NOTE:    the optional parameter is only allowed if the basering has the
     1979NOTE:    the optional parameter is only allowed if the basering has the 
    22591980         variables x and y
    22601981EXAMPLE: example ellipticNFDB;   shows an example"
     
    22982019   // its lattice points are
    22992020   nf[2];
    2300 }
    2301 
    2302 
    2303 /////////////////////////////////////////////////////////////////////////////////
    2304 /// AUXILARY PROCEDURES
    2305 /////////////////////////////////////////////////////////////////////////////////
    2306 
    2307 proc polymakeKeepTmpFiles (int i)
    2308 "USAGE:  polymakeKeepTmpFiles(int i);   i int
    2309 PURPOSE: some procedures create files in the directory /tmp which are used for
    2310          computations with polymake respectively topcom; these will be removed
    2311          when the corresponding procedure is left; however, it might be
    2312          desireable to keep them for further computations with either polymake or
    2313          topcom; this can be achieved by this procedure; call the procedure as:
    2314 @*       - polymakeKeepTmpFiles(1); - then the files will be kept
    2315 @*       - polymakeKeepTmpFiles(0); - then files will be removed in the future
    2316 RETURN:  none"
    2317 {
    2318   if ((i==1) and (defined(polymakekeeptmpfiles)==0))
    2319   {
    2320     int polymakekeeptmpfiles;
    2321     export(polymakekeeptmpfiles);
    2322   }
    2323   if (i!=1)
    2324   {
    2325     if (defined(polymakekeeptmpfiles))
    2326     {
    2327       kill polymakekeeptmpfiles;
    2328     }
    2329   }
    23302021}
    23312022
     
    23522043static proc scalarproduct (intvec w,intvec v)
    23532044"USAGE:      scalarproduct(w,v); w,v intvec
    2354 ASSUME:      w and v are integer vectors of the same length
     2045ASSUME:      w and v are integer vectors of the same length 
    23552046RETURN:      int, the scalarproduct of v and w
    23562047NOTE:        the procedure is called by findOrientedBoundary"
     
    23992090  {
    24002091    int m=nrows(M);
    2401 
     2092   
    24022093  }
    24032094  else
     
    24572148  {
    24582149    return("");
    2459 
     2150   
    24602151  }
    24612152  if (i==1)
     
    25672258        k++;
    25682259      }
    2569       else
     2260      else 
    25702261      {
    25712262        stop=1;
     
    26102301        k++;
    26112302      }
    2612       else
     2303      else 
    26132304      {
    26142305        stop=1;
     
    26592350static proc polygonToCoordinates (list points)
    26602351"USAGE:      polygonToCoordinates(points);   points list
    2661 ASSUME:      points is a list of integer vectors each of size two describing the
    2662              marked points of a convex lattice polygon like the output of
     2352ASSUME:      points is a list of integer vectors each of size two describing the 
     2353             marked points of a convex lattice polygon like the output of 
    26632354             polygonDB
    2664 RETURN:      list, the first entry is a string representing the coordinates
     2355RETURN:      list, the first entry is a string representing the coordinates 
    26652356                   corresponding to the latticpoints seperated by commata
    2666                    the second entry is a list where the ith entry is a string
    2667                    representing the coordinate of corresponding to the ith
    2668                    lattice point the third entry is the latex format of the
     2357                   the second entry is a list where the ith entry is a string 
     2358                   representing the coordinate of corresponding to the ith 
     2359                   lattice point the third entry is the latex format of the 
    26692360                   first entry
    26702361NOTE:        the procedure is called by fan"
     
    26832374  return(list(coord,coords,latex));
    26842375}
     2376
     2377static proc intmatAddFirstColumn (intmat M,string art)
     2378"USAGE:  intmatAddFirstColumn(M,art);  M intmat, art string
     2379ASSUME:  - M is an integer matrix where a first column of 0's or 1's should be added
     2380@*       - art is one of the following strings:
     2381@*         + 'rays'   : indicating that a first column of 0's should be added
     2382@*         + 'points' : indicating that a first column of 1's should be added
     2383RETURN:  intmat, a first column has been added to the matrix"
     2384{
     2385  intmat N[nrows(M)][ncols(M)+1];
     2386  int i,j;
     2387  for (i=1;i<=nrows(M);i++)
     2388  {
     2389    if (art=="rays")
     2390    {
     2391      N[i,1]=0;
     2392    }
     2393    else
     2394    {
     2395      N[i,1]=1;
     2396    }
     2397    for (j=1;j<=ncols(M);j++)
     2398    {
     2399      N[i,j+1]=M[i,j];
     2400    }
     2401  }
     2402  return(N);
     2403}
     2404
     2405
     2406
Note: See TracChangeset for help on using the changeset viewer.