This is PhylogeneticTrees.info, produced by Macaulay2, version 1.24.11

PhylogeneticTrees -- a package to compute phylogenetic invariants associated to group-based models
**************************************************************************************************

Description
===========

PhylogeneticTrees is a package for phylogenetic algebraic geometry. This
package calculates generating sets for phylogenetic ideals and their joins and
secants.  Additionally, the package computes lower bounds for the dimensions of
secants and joins of phylogenetic ideals.

This package handles a class of commonly used tree-based Markov models called
group-based models.  These models are subject to the Fourier-Hadamard
coordinate transformation, which make the parametrizations monomial and the
ideals toric. See the following for more details: [1] and [2].

For these models, the PhylogeneticTrees package includes two methods for
computing a generating set for ideals of phylogenetic invariants. The first
method calls FourTiTwo, to compute the generating set of
the toric ideal. The second implements a theoretical construction for
inductively determining the ideal of phylogenetic invariants for any $k$-valent
tree from the $k$-leaf claw tree as described in Theorem 24 of [3].

This package also handles the joins and secants of these ideals by implementing
the elimination method described in [4].

In cases where computing a generating set for a join or secant ideal is
infeasible, the package provides a probabilistic method, based on Terracini’s
Lemma, to compute a lower bound on the dimension of a join or secant ideal.

References:

[1] S.N. Evans and T.P. Speed, it Invariants of some probability models used in
phylogenetic inference, Ann. Statist. 21 (1993), no. 1, 355–377, and

[2] L. Székely, P.L. Erdös, M.A. Steel, and D. Penny, A Fourier inversion
formula for evolutionary trees, Applied Mathematics Letters 6 (1993), no. 2,
13–17.

[3] Bernd Sturmfels and Seth Sullivant, Toric ideals of phylogenetic
invariants, J. Comp. Biol. 12 (2005), no. 2, 204–228.

[4] Bernd Sturmfels and Seth Sullivant, Combinatorial secant varieties,
Quarterly Journal of Pure and Applied Mathematics 2 (2006), 285–309.

Authors
=======

  * Hector Baños <hbanos@gatech.edu>
  * Nathaniel Bushek <nbushek@css.edu>
  * Ruth Davidson <ruth.davidson.math@gmail.com>
  * Elizabeth Gross <egross@hawaii.edu>
  * Pamela Harris <peh2@williams.edu>
  * Robert Krone <rckrone@gmail.com>
  * Colby Long <clong@wooster.edu>
  * AJ Stewart <stewaral@seattleu.edu>
  * Robert Walker <robmarsw@umich.edu>

Certification a gold star
=========================

Version 2.0 of this package was accepted for publication in volume 11 (see
https://msp.org/jsag/2021/11-1/ ) of The Journal of Software for Algebra and
Geometry (see https://msp.org/jsag/ ) on 8 August 2020, in the article
Phylogenetic trees (see https://msp.org/jsag/2021/11-1/p01.xhtml ) (DOI:
10.2140/jsag.2021.11.1 (see https://doi.org/10.2140/jsag.2021.11.1 )). That
version can be obtained from the journal (see
https://msp.org/jsag/2021/11-1/jsag-v11-n1-x01-PhylogeneticTrees.m2 ) or from
the Macaulay2 source code repository (see
https://github.com/Macaulay2/M2/blob/abdf0903e7ffc31568c0cc4beb181368d943cb8d/
M2/Macaulay2/packages/PhylogeneticTrees.m2 ).

Version
=======

This documentation describes version 2.0 of PhylogeneticTrees.

Source code
===========

The source code from which this documentation is derived is in the file
PhylogeneticTrees.m2 (see common/share/Macaulay2/PhylogeneticTrees.m2 ).

Exports
=======

  * Types
      * LeafTree -- a tree described in terms of its leaves
      * Model -- a group-based model
  * Functions and commands
      * buckets -- the equivalence classes of group elements of
        a Model
      * edgeContract -- contract an edge of a tree
      * edgeCut -- break up a tree at an edge
      * fourierToProbability -- map from Fourier
        coordinates to probability coordinates
      * group -- the group of a Model
      * internalEdges -- list the internal edges of a
        tree
      * internalVertices -- list the internal vertices
        of a tree
      * isIsomorphic -- check isomorphism of two tree
      * joinIdeal -- compute the join of several ideals
      * labeledBinaryTrees -- enumerate all binary
        labeled trees
      * labeledTrees -- enumerate all labeled trees
      * leafColorings -- list the consistent colorings of
        a tree
      * leafTree -- construct a LeafTree
      * model -- construct a Model
      * phyloToric42 -- compute the invariants of a
        group-based phylogenetic model with 4ti2
      * phyloToricAMatrix -- construct the design
        matrix of a group-based phylogenetic model
      * phyloToricFP -- compute the invariants of a
        group-based phylogenetic model with toric fiber products
      * phyloToricLinears -- compute the linear
        invariants of a group-based phylogenetic model
      * phyloToricQuads -- compute the quadratic
        invariants of a group-based phylogenetic model
      * phyloToricRandom -- compute a random invariant
        of a group-based phylogenetic model
      * pRing -- construct the ring of probability coordinates
      * qRing -- construct the ring of Fourier coordinates
      * rootedBinaryTrees -- enumerate all rooted
        binary trees
      * rootedTrees -- enumerate all rooted trees
      * secant -- compute the secant of an ideal
      * toricJoinDim -- dimension of a join of toric
        varieties
      * toricSecantDim -- dimension of a secant of a
        toric variety
      * unlabeledTrees -- enumerate all unlabeled trees
      * vertexCut -- break up a tree at a vertex
  * Methods
      * "buckets(Model)" -- see buckets, -- the equivalence
        classes of group elements of a Model
      * digraph(LeafTree,List) -- convert
        a LeafTree to a Digraph
      * "digraph(LeafTree,Set)" -- see digraph(LeafTree,List),
        -- convert a LeafTree to a Digraph
      * "edgeContract(LeafTree,List)" -- see edgeContract,
        -- contract an edge of a tree
      * "edgeContract(LeafTree,Set)" -- see edgeContract,
        -- contract an edge of a tree
      * "edgeCut(LeafTree,List,Thing)" -- see edgeCut, -- break
        up a tree at an edge
      * "edgeCut(LeafTree,Set,Thing)" -- see edgeCut, -- break
        up a tree at an edge
      * edges(LeafTree) -- list the edges of a tree
      * "fourierToProbability(Ring,Ring,ZZ,Model)" -- see
        fourierToProbability, -- map from Fourier
        coordinates to probability coordinates
      * graph(LeafTree) -- convert a LeafTree to
        Graph
      * "group(Model)" -- see group, -- the group of a Model
      * "internalEdges(LeafTree)" -- see internalEdges, --
        list the internal edges of a tree
      * "internalVertices(LeafTree)" -- see internalVertices,
        -- list the internal vertices of a tree
      * "joinIdeal(Ideal,Ideal)" -- see joinIdeal, -- compute
        the join of several ideals
      * "joinIdeal(List)" -- see joinIdeal, -- compute the
        join of several ideals
      * "labeledBinaryTrees(ZZ)" -- see labeledBinaryTrees,
        -- enumerate all binary labeled trees
      * "labeledTrees(ZZ)" -- see labeledTrees, --
        enumerate all labeled trees
      * "leafColorings(LeafTree,Model)" -- see leafColorings,
        -- list the consistent colorings of a tree
      * "leafColorings(ZZ,Model)" -- see leafColorings, --
        list the consistent colorings of a tree
      * "LeafTree == LeafTree" -- see LeafTree, -- a tree
        described in terms of its leaves
      * "leafTree(Graph)" -- see leafTree, -- construct a
        LeafTree
      * "leafTree(List,List)" -- see leafTree, -- construct a
        LeafTree
      * "leafTree(ZZ,List)" -- see leafTree, -- construct a
        LeafTree
      * leaves(LeafTree) -- list the leaves of a
        tree
      * "model(List,List,List)" -- see model, -- construct a Model
      * "phyloToric42(Graph,Model)" -- see phyloToric42, --
        compute the invariants of a group-based phylogenetic model with 4ti2
      * "phyloToric42(LeafTree,Model)" -- see phyloToric42,
        -- compute the invariants of a group-based phylogenetic model with 4ti2
      * "phyloToric42(ZZ,List,Model)" -- see phyloToric42,
        -- compute the invariants of a group-based phylogenetic model with 4ti2
      * "phyloToricAMatrix(Graph,Model)" -- see phyloToricAMatrix,
        -- construct the design matrix of a group-based
        phylogenetic model
      * "phyloToricAMatrix(LeafTree,Model)" -- see phyloToricAMatrix,
        -- construct the design matrix of a group-based
        phylogenetic model
      * "phyloToricAMatrix(ZZ,List,Model)" -- see phyloToricAMatrix,
        -- construct the design matrix of a group-based
        phylogenetic model
      * "phyloToricFP(LeafTree,Model)" -- see phyloToricFP,
        -- compute the invariants of a group-based phylogenetic model with
        toric fiber products
      * "phyloToricFP(ZZ,List,Model)" -- see phyloToricFP,
        -- compute the invariants of a group-based phylogenetic model with
        toric fiber products
      * "phyloToricLinears(LeafTree,Model)" -- see phyloToricLinears,
        -- compute the linear invariants of a group-based
        phylogenetic model
      * "phyloToricLinears(ZZ,List,Model)" -- see phyloToricLinears,
        -- compute the linear invariants of a group-based
        phylogenetic model
      * "phyloToricQuads(LeafTree,Model)" -- see phyloToricQuads,
        -- compute the quadratic invariants of a group-based
        phylogenetic model
      * "phyloToricQuads(ZZ,List,Model)" -- see phyloToricQuads,
        -- compute the quadratic invariants of a group-based
        phylogenetic model
      * "phyloToricRandom(LeafTree,Model)" -- see phyloToricRandom,
        -- compute a random invariant of a group-based
        phylogenetic model
      * "phyloToricRandom(ZZ,List,Model)" -- see phyloToricRandom,
        -- compute a random invariant of a group-based
        phylogenetic model
      * "pRing(LeafTree,Model)" -- see pRing, -- construct the
        ring of probability coordinates
      * "pRing(ZZ,Model)" -- see pRing, -- construct the ring of
        probability coordinates
      * "qRing(LeafTree,Model)" -- see qRing, -- construct the
        ring of Fourier coordinates
      * "qRing(ZZ,Model)" -- see qRing, -- construct the ring of
        Fourier coordinates
      * "rootedBinaryTrees(ZZ)" -- see rootedBinaryTrees,
        -- enumerate all rooted binary trees
      * "rootedTrees(ZZ)" -- see rootedTrees, -- enumerate
        all rooted trees
      * "secant(Ideal,ZZ)" -- see secant, -- compute the secant
        of an ideal
      * "toricJoinDim(List)" -- see toricJoinDim, --
        dimension of a join of toric varieties
      * "toricJoinDim(Matrix,Matrix)" -- see toricJoinDim,
        -- dimension of a join of toric varieties
      * "toricSecantDim(Matrix,ZZ)" -- see toricSecantDim,
        -- dimension of a secant of a toric variety
      * "unlabeledTrees(ZZ)" -- see unlabeledTrees, --
        enumerate all unlabeled trees
      * "vertexCut(LeafTree,List,Thing,Thing)" -- see vertexCut,
        -- break up a tree at a vertex
      * "vertexCut(LeafTree,Set,Thing,Thing)" -- see vertexCut,
        -- break up a tree at a vertex
      * vertices(LeafTree) -- list the vertices
        of a tree
  * Symbols
      * QRing -- optional argument to specify Fourier coordinate
        ring
  * Other things
      * CFNmodel -- the model corresponding to the
        Cavender-Farris-Neyman model or binary Jukes Cantor
      * JCmodel -- the model corresponding to the Jukes Cantor
        model
      * K2Pmodel -- the model corresponding to the Kimura
        2-parameter model
      * K3Pmodel -- the model corresponding to the Kimura
        3-parameter model

For the programmer
==================

The object PhylogeneticTrees, is a package (Macaulay2Doc).

buckets -- the equivalence classes of group elements of a Model
***************************************************************

Synopsis
========

  * Usage:
        buckets M
  * Inputs:
      * M, an instance of the type Model,
  * Outputs:
      * a list (Macaulay2Doc), of lists of group elements

Description
===========

Every group-based phylogenetic model has a finite group G associated to it.
Parameters for the model are assigned to equivalence classes of group elements,
which are orbits of some subgroup of the automorphism group of G.  This
function returns the equivalence classes as a list of list of group elements.

+-----------------------------------------------------------------------------+
|i1 : M = K2Pmodel                                                            |
|                                                                             |
|o1 = Model{AList => HashTable{{0, 0} => {1, 0, 0}}                          }|
|                              {0, 1} => {0, 1, 0}                            |
|                              {1, 0} => {0, 0, 1}                            |
|                              {1, 1} => {0, 0, 1}                            |
|           Automorphisms => HashTable{{2, 3} => HashTable{{0, 0} => {0, 0}}} |
|                                                          {0, 1} => {0, 1}   |
|                                                          {1, 0} => {1, 1}   |
|                                                          {1, 1} => {1, 0}   |
|                                      {3, 2} => HashTable{{0, 0} => {0, 0}}  |
|                                                          {0, 1} => {0, 1}   |
|                                                          {1, 0} => {1, 1}   |
|                                                          {1, 1} => {1, 0}   |
|           Buckets => {{{0, 0}}, {{0, 1}}, {{1, 0}, {1, 1}}}                 |
|           Group => {{0, 0}, {0, 1}, {1, 0}, {1, 1}}                         |
|                                                                             |
|o1 : Model                                                                   |
+-----------------------------------------------------------------------------+
|i2 : B = buckets M                                                           |
|                                                                             |
|o2 = {{{0, 0}}, {{0, 1}}, {{1, 0}, {1, 1}}}                                  |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * Model -- a group-based model

Ways to use buckets:
====================

  * "buckets(Model)"

For the programmer
==================

The object buckets, is a method function (Macaulay2Doc).

CFNmodel -- the model corresponding to the Cavender-Farris-Neyman model or binary Jukes Cantor
**********************************************************************************************

Description
===========

The Cavender-Farris-Neyman (CFN) Model is a Markov model of base substitution.
It also known as the binary Jukes-Cantor model. It assumes the root
distribution vectors describe all bases occurring uniformly in the ancestral
sequence. It also assumes that the rate of all specific base changes is the
same.

The transition matrix has the form $$\begin{pmatrix} \alpha&\beta\\
\beta&\alpha \end{pmatrix}$$

See also
========

  * Model -- a group-based model
  * JCmodel -- the model corresponding to the Jukes Cantor
    model
  * K2Pmodel -- the model corresponding to the Kimura
    2-parameter model
  * K3Pmodel -- the model corresponding to the Kimura
    3-parameter model

For the programmer
==================

The object CFNmodel, is an instance of the type Model.

digraph(LeafTree,List) -- convert a LeafTree to a Digraph
*********************************************************

Synopsis
========

  * Function: digraph (Graphs),
  * Usage:
        digraph(T,r)
  * Inputs:
      * T, an instance of the type LeafTree,
      * r, a list (Macaulay2Doc), representing a vertex
  * Optional inputs (Macaulay2Doc),:
      * EntryMode (missing documentation) => ..., default value "auto",
      * Singletons (missing documentation) => ..., default value null,
  * Outputs:
      * a digraph (Graphs),

Description
===========

A rooted tree can be represented by an object of class LeafTree,
and a choice of vertex to be the root. This function converts such a
representation of a rooted tree into an object of class Digraph (Graphs),
with edges oriented away from the root.

The internal vertices of an object of class LeafTree, are not
named, so each vertex is specified by the partition of the set of leaves formed
by removing the vertex.  Each partition is given as a list of sets.  This is
also how the root vertex should be passed to the function.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}})                                                 |
|                                                                             |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}        |
|                                                                             |
|o1 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i2 : r = {set{0,1}, set{2}, set{3}}                                          |
|                                                                             |
|o2 = {set {0, 1}, set {2}, set {3}}                                          |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : D = digraph(T,r)                                                        |
|                                                                             |
|o3 = Digraph{set {set {0, 1, 2}} => {}                                       |
|             set {set {0, 1, 3}} => {}                                       |
|             set {set {0, 2, 3}} => {}                                       |
|             set {set {1, 2, 3}} => {}                                       |
|             set {set {1}, set {0}, set {2, 3}} => {set {set                 |
|             set {set {3}, set {0, 1}, set {2}} => {set {set                 |
|                                                                             |
|o3 : Digraph                                                                 |
|-----------------------------------------------------------------------------|
|                                                                    }        |
|                                                                             |
|                                                                             |
|                                                                             |
|{1, 2, 3}}, set {set {0, 2, 3}}}                                             |
|{1}, set {0}, set {2, 3}}, set {set {0, 1, 2}}, set {set {0, 1, 3}}}         |
+-----------------------------------------------------------------------------+
|i4 : adjacencyMatrix D                                                       |
|                                                                             |
|o4 = | 0 1 1 0 0 0 |                                                         |
|     | 0 0 0 0 0 0 |                                                         |
|     | 0 0 0 0 0 0 |                                                         |
|     | 1 0 0 0 1 1 |                                                         |
|     | 0 0 0 0 0 0 |                                                         |
|     | 0 0 0 0 0 0 |                                                         |
|                                                                             |
|              6       6                                                      |
|o4 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+

Ways to use this method:
========================

  * digraph(LeafTree,List) -- convert a
    LeafTree to a Digraph
  * "digraph(LeafTree,Set)"

edgeContract -- contract an edge of a tree
******************************************

Synopsis
========

  * Usage:
        edgeContract(T,e)
        edgeContract(T,E)
  * Inputs:
      * T, an instance of the type LeafTree,
      * e, a set (Macaulay2Doc), an edge specified by the set of
        leaves on one side of it
      * E, a list (Macaulay2Doc), an edge specified by a list of
        the leaves on one side of it
  * Outputs:
      * an instance of the type LeafTree, obtained from T by
        contracting the specified edge

Description
===========

This function produces a new object of class LeafTree, obtained
by contracting the edge e of tree T.

+---------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}})                                         |
|                                                                     |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}|
|                                                                     |
|o1 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i2 : edgeContract(T, set {0,1})                                      |
|                                                                     |
|o2 = {{0, 1, 2, 3}, {set {0}, set {1}, set {2}, set {3}}}            |
|                                                                     |
|o2 : LeafTree                                                        |
+---------------------------------------------------------------------+

Ways to use edgeContract:
=========================

  * "edgeContract(LeafTree,List)"
  * "edgeContract(LeafTree,Set)"

For the programmer
==================

The object edgeContract, is a method function (Macaulay2Doc).

edgeCut -- break up a tree at an edge
*************************************

Synopsis
========

  * Usage:
        edgeCut(T,e,newl)
        edgeCut(T,E,newl)
  * Inputs:
      * T, an instance of the type LeafTree,
      * e, a set (Macaulay2Doc), an edge specified by the set of
        leaves on one side of it
      * E, a list (Macaulay2Doc), an edge specified by a list of
        the leaves on one side of it
      * newl, a thing (Macaulay2Doc), the label for a new leaf
  * Outputs:
      * a list (Macaulay2Doc), of two LeafTree,s
        that are subtrees of T

Description
===========

This function outputs the two subtrees of T obtained by deleting edge e from T
and then re-adding the edge to each of the two resulting subtrees. Both
subtrees share a copy of the edge e and the newly labeled leaf adjacent to e.
Other than this overlap, they are disjoint.

Each subtree in P may have at most one leaf that was not a leaf of T, and
therefore previously unlabeled. The label for this new leaf is input as newl.

+---------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}})                                         |
|                                                                     |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}|
|                                                                     |
|o1 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i2 : P = edgeCut(T, set {0,1}, 4);                                   |
+---------------------------------------------------------------------+
|i3 : P#0                                                             |
|                                                                     |
|o3 = {{0, 1, 4}, {set {0}, set {1}, set {4}}}                        |
|                                                                     |
|o3 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i4 : P#1                                                             |
|                                                                     |
|o4 = {{2, 3, 4}, {set {2}, set {3}, set {4}}}                        |
|                                                                     |
|o4 : LeafTree                                                        |
+---------------------------------------------------------------------+

See also
========

  * vertexCut -- break up a tree at a vertex

Ways to use edgeCut:
====================

  * "edgeCut(LeafTree,List,Thing)"
  * "edgeCut(LeafTree,Set,Thing)"

For the programmer
==================

The object edgeCut, is a method function (Macaulay2Doc).

edges(LeafTree) -- list the edges of a tree
*******************************************

Synopsis
========

  * Function: edges (Graphs),
  * Usage:
        edges T
  * Inputs:
      * T, an instance of the type LeafTree,
  * Outputs:
      * a list (Macaulay2Doc), the edges of T

Description
===========

This function lists all edges of a tree.  Each entry of the list is a
Set (Macaulay2Doc), of the leaves on one side of the edge.

+--------------------------------------------------------------+
|i1 : T = leafTree(5,{{0,1}});                                 |
+--------------------------------------------------------------+
|i2 : leaves T                                                 |
|                                                              |
|o2 = set {0, 1, 2, 3, 4}                                      |
|                                                              |
|o2 : Set                                                      |
+--------------------------------------------------------------+
|i3 : edges T                                                  |
|                                                              |
|o3 = {set {0, 1}, set {0}, set {1}, set {2}, set {3}, set {4}}|
|                                                              |
|o3 : List                                                     |
+--------------------------------------------------------------+

See also
========

  * internalEdges -- list the internal edges of a tree

Ways to use this method:
========================

  * edges(LeafTree) -- list the edges of a tree

fourierToProbability -- map from Fourier coordinates to probability coordinates
*******************************************************************************

Synopsis
========

  * Usage:
        fourierToProbability(S,R,n,M)
  * Inputs:
      * S, a ring (Macaulay2Doc), of probability coordinates
      * R, a ring (Macaulay2Doc), of Fourier coordinates
      * n, an integer (Macaulay2Doc), the number of leaves
      * M, an instance of the type Model,
  * Outputs:
      * a ring map (Macaulay2Doc), from Fourier coordinates to
        probability coordinates

Description
===========

This function creates a ring map from the ring of Fourier coordinates to the
ring of probability coordinates, for the four predefined models, see
CFNmodel, JCmodel, K2Pmodel, or
K3Pmodel.  It will not work with user-defined models. The ring
of probability coordinates must have at least $|G|^n$ variables where $G$ is
the group associated to the model. The ring of Fourier coordinates must have at
least $|G|^{(n-1)}$ variables.

+-----------------------------------------------------------------------------+
|i1 : M = CFNmodel;                                                           |
+-----------------------------------------------------------------------------+
|i2 : S = pRing(3,M)                                                          |
|                                                                             |
|o2 = S                                                                       |
|                                                                             |
|o2 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i3 : R = qRing(3,M)                                                          |
|                                                                             |
|o3 = R                                                                       |
|                                                                             |
|o3 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i4 : m = fourierToProbability(S,R,3,M)                                       |
|                                                                             |
|o4 = map (S, R, {p      + p      + p      + p      + p      + p      + p     |
|                  0,0,0    0,0,1    0,1,0    0,1,1    1,0,0    1,0,1    1,1,0|
|                                                                             |
|o4 : RingMap S <-- R                                                         |
|-----------------------------------------------------------------------------|
|+ p     , p      - p      - p      + p      + p      - p      - p      +     |
|   1,1,1   0,0,0    0,0,1    0,1,0    0,1,1    1,0,0    1,0,1    1,1,0       |
|-----------------------------------------------------------------------------|
|p     , p      - p      + p      - p      - p      + p      - p      +       |
| 1,1,1   0,0,0    0,0,1    0,1,0    0,1,1    1,0,0    1,0,1    1,1,0         |
|-----------------------------------------------------------------------------|
|p     , p      + p      - p      - p      - p      - p      + p      +       |
| 1,1,1   0,0,0    0,0,1    0,1,0    0,1,1    1,0,0    1,0,1    1,1,0         |
|-----------------------------------------------------------------------------|
|p     })                                                                     |
| 1,1,1                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * pRing -- construct the ring of probability coordinates
  * qRing -- construct the ring of Fourier coordinates

Ways to use fourierToProbability:
=================================

  * "fourierToProbability(Ring,Ring,ZZ,Model)"

For the programmer
==================

The object fourierToProbability, is a method function (Macaulay2Doc).

graph(LeafTree) -- convert a LeafTree to Graph
**********************************************

Synopsis
========

  * Function: graph (Graphs),
  * Usage:
        graph T
  * Inputs:
      * T, an instance of the type LeafTree,
  * Optional inputs (Macaulay2Doc),:
      * EntryMode (Graphs), => ..., default value "auto",
      * Singletons (Graphs), => ..., default value null,
  * Outputs:
      * a graph (Graphs),

Description
===========

This converts a LeafTree, representation of a tree into a
Graph (Graphs).

The internal vertices of a LeafTree are not named, so each vertex is specified
by the partition of the set of leaves formed by removing the vertex.  Each
partition is given as a List (Macaulay2Doc), of Set (Macaulay2Doc),
s.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}})                                                 |
|                                                                             |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}        |
|                                                                             |
|o1 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i2 : G = graph T                                                             |
|                                                                             |
|o2 = Graph{set {set {0, 1, 2}} => {set {set {3},                             |
|           set {set {0, 1, 3}} => {set {set {3},                             |
|           set {set {0, 2, 3}} => {set {set {1},                             |
|           set {set {1, 2, 3}} => {set {set {1},                             |
|           set {set {1}, set {2, 3}, set {0}} =>                             |
|           set {set {3}, set {2}, set {0, 1}} =>                             |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|set {2}, set {0, 1}}}                                                        |
|set {2}, set {0, 1}}}                                                        |
|set {2, 3}, set {0}}}                                                        |
|set {2, 3}, set {0}}}                                                        |
|{set {set {3}, set {2}, set {0, 1}}, set {set {0, 2, 3}}, set {set {1, 2, 3  |
|{set {set {0, 1, 2}}, set {set {0, 1, 3}}, set {set {1}, set {2, 3}, set {0  |
|-----------------------------------------------------------------------------|
|   }                                                                         |
|                                                                             |
|                                                                             |
|                                                                             |
|}}}                                                                          |
|}}}                                                                          |
+-----------------------------------------------------------------------------+
|i3 : adjacencyMatrix G                                                       |
|                                                                             |
|o3 = | 0 1 1 1 0 0 |                                                         |
|     | 1 0 0 0 0 0 |                                                         |
|     | 1 0 0 0 0 0 |                                                         |
|     | 1 0 0 0 1 1 |                                                         |
|     | 0 0 0 1 0 0 |                                                         |
|     | 0 0 0 1 0 0 |                                                         |
|                                                                             |
|              6       6                                                      |
|o3 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+

Ways to use this method:
========================

  * graph(LeafTree) -- convert a LeafTree to Graph

group -- the group of a Model
*****************************

Synopsis
========

  * Usage:
        group M
  * Inputs:
      * M, an instance of the type Model,
  * Outputs:
      * a list (Macaulay2Doc), of group elements

Description
===========

Every group-based phylogenetic model has a finite group associated to it.  This
function returns the group, represented as a list of elements.

+---------------------------------------------------------------+
|i1 : M = K3Pmodel                                              |
|                                                               |
|o1 = Model{AList => HashTable{{0, 0} => {1, 0, 0, 0}}         }|
|                              {0, 1} => {0, 1, 0, 0}           |
|                              {1, 0} => {0, 0, 1, 0}           |
|                              {1, 1} => {0, 0, 0, 1}           |
|           Automorphisms => HashTable{}                        |
|           Buckets => {{{0, 0}}, {{0, 1}}, {{1, 0}}, {{1, 1}}} |
|           Group => {{0, 0}, {0, 1}, {1, 0}, {1, 1}}           |
|                                                               |
|o1 : Model                                                     |
+---------------------------------------------------------------+
|i2 : G = group M                                               |
|                                                               |
|o2 = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}                          |
|                                                               |
|o2 : List                                                      |
+---------------------------------------------------------------+

See also
========

  * Model -- a group-based model

Ways to use group:
==================

  * "group(Model)"

For the programmer
==================

The object group, is a method function (Macaulay2Doc).

internalEdges -- list the internal edges of a tree
**************************************************

Synopsis
========

  * Usage:
        internalEdges T
  * Inputs:
      * T, an instance of the type LeafTree,
  * Outputs:
      * a list (Macaulay2Doc), the internal edges of T

Description
===========

An internal edge of a tree is an edge that is not incident to a leaf. This
function lists such edges. Each entry of the list is a set (Macaulay2Doc),
of the leaves on one side of the edge.

+-----------------------------------------------+
|i1 : G = graph {{0,4},{1,4},{4,5},{5,2},{5,3}};|
+-----------------------------------------------+
|i2 : T = leafTree G;                           |
+-----------------------------------------------+
|i3 : internalEdges T                           |
|                                               |
|o3 = {set {0, 1}}                              |
|                                               |
|o3 : List                                      |
+-----------------------------------------------+

See also
========

  * edges(LeafTree) -- list the edges of a tree

Ways to use internalEdges:
==========================

  * "internalEdges(LeafTree)"

For the programmer
==================

The object internalEdges, is a method function (Macaulay2Doc).

internalVertices -- list the internal vertices of a tree
********************************************************

Synopsis
========

  * Usage:
        internalVertices T
  * Inputs:
      * T, an instance of the type LeafTree,
  * Outputs:
      * a list (Macaulay2Doc), the internal vertices of T

Description
===========

An internal vertex of a tree is a vertex that is not a leaf, meaning it has
degree at least 2. This function lists such vertices. Each vertex is specified
by the partition of the set of leaves formed by removing the vertex.  Each
partition is given as a list of sets.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}});                                                |
+-----------------------------------------------------------------------------+
|i2 : internalVertices T                                                      |
|                                                                             |
|o2 = {set {set {3}, set {2}, set {0, 1}}, set {set {1}, set {2, 3}, set {0}}}|
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : #(internalVertices T)                                                   |
|                                                                             |
|o3 = 2                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * vertices(LeafTree) -- list the vertices of a
    tree

Ways to use internalVertices:
=============================

  * "internalVertices(LeafTree)"

For the programmer
==================

The object internalVertices, is a method function (Macaulay2Doc).

isIsomorphic -- check isomorphism of two tree
*********************************************

Synopsis
========

  * Usage:
        isIsomorphic(T,U)
  * Inputs:
      * T, an instance of the type LeafTree,
      * U, an instance of the type LeafTree,
  * Outputs:
      * a Boolean value (Macaulay2Doc), if U and T are
        isomorphic

Description
===========

This function checks if two objects of class LeafTree, are
isomorphic to each other as unlabeled graphs. This is in contrast to equality
of two objects of class LeafTree, which also checks whether
they have the same leaf labeling.

+-----------------------------+
|i1 : T = leafTree(4,{{0,1}});|
+-----------------------------+
|i2 : U = leafTree(4,{{1,2}});|
+-----------------------------+
|i3 : isIsomorphic(T,U)       |
|                             |
|o3 = true                    |
+-----------------------------+

Ways to use isIsomorphic:
=========================

  * "isIsomorphic(LeafTree,LeafTree)"

For the programmer
==================

The object isIsomorphic, is a method function (Macaulay2Doc).

JCmodel -- the model corresponding to the Jukes Cantor model
************************************************************

Description
===========

The Jukes-Cantor (JK) Model is a Markov model of base substitution. It assumes
the root distribution vectors describe all bases occurring uniformly in the
ancestral sequence. It also assumes that the rate of all specific base changes
is the same. Thus the rates of bases changes A-G, A-T and A-C are the same.

The transition matrix has the form $$\begin{pmatrix} \alpha&\beta&\beta&\beta\\
\beta&\alpha&\beta&\beta\\ \beta&\beta&\alpha&\beta\\ \beta&\beta&\beta&\alpha
\end{pmatrix}$$

See also
========

  * Model -- a group-based model
  * CFNmodel -- the model corresponding to the
    Cavender-Farris-Neyman model or binary Jukes Cantor
  * K2Pmodel -- the model corresponding to the Kimura
    2-parameter model
  * K3Pmodel -- the model corresponding to the Kimura
    3-parameter model

For the programmer
==================

The object JCmodel, is an instance of the type Model.

joinIdeal -- compute the join of several ideals
***********************************************

Synopsis
========

  * Usage:
        joinIdeal(I,J)
        joinIdeal L
  * Inputs:
      * I, an ideal (Macaulay2Doc),
      * J, an ideal (Macaulay2Doc),
      * L, a list (Macaulay2Doc), of ideals in the same ring
  * Optional inputs (Macaulay2Doc),:
      * DegreeLimit => ..., default value {}
  * Outputs:
      * an ideal (Macaulay2Doc), the join of the input ideals

Description
===========

This function computes the ideal of the join by constructing the abstract join
and then projecting with elimination.

Setting the optional argument DegreeLimit (Macaulay2Doc), to
\{d\}  will produce only the generators of the join ideal up to degree d.

This method is general and will work for arbitrary polynomial ideals, not just
phylogenetic ideals.

+----------------------------+
|i1 : R = QQ[a,b,c,d]        |
|                            |
|o1 = R                      |
|                            |
|o1 : PolynomialRing         |
+----------------------------+
|i2 : I = ideal {a-d,b^2-c*d}|
|                            |
|                    2       |
|o2 = ideal (a - d, b  - c*d)|
|                            |
|o2 : Ideal of R             |
+----------------------------+
|i3 : J = ideal {a,b,c}      |
|                            |
|o3 = ideal (a, b, c)        |
|                            |
|o3 : Ideal of R             |
+----------------------------+
|i4 : joinIdeal(I,J)         |
|                            |
|            2               |
|o4 = ideal(b  - a*c)        |
|                            |
|o4 : Ideal of R             |
+----------------------------+

See also
========

  * secant -- compute the secant of an ideal

Ways to use joinIdeal:
======================

  * "joinIdeal(Ideal,Ideal)"
  * "joinIdeal(List)"

For the programmer
==================

The object joinIdeal, is a method function with options (Macaulay2Doc).

K2Pmodel -- the model corresponding to the Kimura 2-parameter model
*******************************************************************

Description
===========

The Kimura 2-parameter (K2P) Model is a Markov model of base substitution. It
assumes the root distribution vectors describe all bases occurring uniformly in
the ancestral sequence. It allows different probabilities of transitions and
transversions. This means that the rate of base changes A-C and A-T are the
same (transversions), and the rate of base change A-G can differ from the other
two (transitions).

The transition matrix has the form $$\begin{pmatrix}
\alpha&\gamma&\beta&\beta\\ \gamma&\alpha&\beta&\beta\\
\beta&\beta&\alpha&\gamma\\ \beta&\beta&\gamma&\alpha \end{pmatrix}$$

See also
========

  * Model -- a group-based model
  * CFNmodel -- the model corresponding to the
    Cavender-Farris-Neyman model or binary Jukes Cantor
  * JCmodel -- the model corresponding to the Jukes Cantor
    model
  * K3Pmodel -- the model corresponding to the Kimura
    3-parameter model

For the programmer
==================

The object K2Pmodel, is an instance of the type Model.

K3Pmodel -- the model corresponding to the Kimura 3-parameter model
*******************************************************************

Description
===========

The Kimura 3-parameter (K3P) Model is a Markov model of base substitution. It
assumes the root distribution vectors describe all bases occurring uniformly in
the ancestral sequence. It allows different probabilities of the base changes
A-G, A-C and A-T. This is the most general group based model on group
$(\mathbb{Z}/2\mathbb{Z})^2$.

The transition matrix has the form $$\begin{pmatrix}
\alpha&\gamma&\beta&\delta\\ \gamma&\alpha&\delta&\beta\\
\beta&\delta&\alpha&\gamma\\ \delta&\beta&\gamma&\alpha \end{pmatrix}$$

See also
========

  * Model -- a group-based model
  * CFNmodel -- the model corresponding to the
    Cavender-Farris-Neyman model or binary Jukes Cantor
  * JCmodel -- the model corresponding to the Jukes Cantor
    model
  * K2Pmodel -- the model corresponding to the Kimura
    2-parameter model

For the programmer
==================

The object K3Pmodel, is an instance of the type Model.

labeledBinaryTrees -- enumerate all binary labeled trees
********************************************************

Synopsis
========

  * Usage:
        labeledTrees n
  * Inputs:
      * n, an integer (Macaulay2Doc), the number of leaves
  * Outputs:
      * a list (Macaulay2Doc), of all binary trees with n leaves

Description
===========

This function enumerates all possible binary trees with n leaves labeled by
$0,\ldots, n-1$, including all possible labelings. The trees are represented as
an object of class LeafTree.

+-----------------------------------------------------------------------------+
|i1 : L = labeledBinaryTrees 4                                                |
|                                                                             |
|o1 = {{{0, 1, 2, 3}, {set {1, 3}, set {0}, set {1}, set {2}, set {3}}}, {{0, |
|     ------------------------------------------------------------------------|
|     1, 2, 3}, {set {1, 2}, set {0}, set {1}, set {2}, set {3}}}, {{0, 1, 2, |
|     ------------------------------------------------------------------------|
|     3}, {set {2, 3}, set {0}, set {1}, set {2}, set {3}}}}                  |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * labeledTrees -- enumerate all labeled trees
  * rootedTrees -- enumerate all rooted trees
  * rootedBinaryTrees -- enumerate all rooted binary
    trees
  * unlabeledTrees -- enumerate all unlabeled trees

Ways to use labeledBinaryTrees:
===============================

  * "labeledBinaryTrees(ZZ)"

For the programmer
==================

The object labeledBinaryTrees, is a method function (Macaulay2Doc).

labeledTrees -- enumerate all labeled trees
*******************************************

Synopsis
========

  * Usage:
        labeledTrees n
  * Inputs:
      * n, an integer (Macaulay2Doc), the number of leaves
  * Outputs:
      * a list (Macaulay2Doc), of all trees with n leaves

Description
===========

This function enumerates all possible homeomorphically-reduced trees (no
degree-2 vertices) with n leaves labeled by $0,\ldots, n-1$, including all
possible labelings.  The trees are represented as objects of class
LeafTree.

+-----------------------------------------------------------------------------+
|i1 : L = labeledTrees 4                                                      |
|                                                                             |
|o1 = {{{0, 1, 2, 3}, {set {1, 2}, set {0}, set {1}, set {2}, set {3}}}, {{0, |
|     ------------------------------------------------------------------------|
|     1, 2, 3}, {set {1, 3}, set {0}, set {1}, set {2}, set {3}}}, {{0, 1, 2, |
|     ------------------------------------------------------------------------|
|     3}, {set {2, 3}, set {0}, set {1}, set {2}, set {3}}}, {{0, 1, 2, 3},   |
|     ------------------------------------------------------------------------|
|     {set {0}, set {1}, set {2}, set {3}}}}                                  |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * labeledBinaryTrees -- enumerate all binary
    labeled trees
  * rootedTrees -- enumerate all rooted trees
  * rootedBinaryTrees -- enumerate all rooted binary
    trees
  * unlabeledTrees -- enumerate all unlabeled trees

Ways to use labeledTrees:
=========================

  * "labeledTrees(ZZ)"

For the programmer
==================

The object labeledTrees, is a method function (Macaulay2Doc).

leafColorings -- list the consistent colorings of a tree
********************************************************

Synopsis
========

  * Usage:
        leafColorings(T,M)
        leafColorings(n,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * M, an instance of the type Model,
  * Outputs:
      * a list (Macaulay2Doc), the consistent colorings of the tree

Description
===========

This function outputs a list of all consistent colorings of the leaves of tree
T. That is all sequences $(g_1,\ldots,g_n)$ such that $g_1+\cdots +g_n = 0$
where each $g_i$ is an element of the group associated to the model M, and n is
the number of leaves of the tree.

These correspond the set of subscripts of the variables in the ring output by
qRing, and appear in the same order.

+-----------------------------------------------------------------------------+
|i1 : leafColorings(4,CFNmodel)                                               |
|                                                                             |
|o1 = {(0, 0, 0, 0), (0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 0), (1, 0, 0, 1),  |
|     ------------------------------------------------------------------------|
|     (1, 0, 1, 0), (1, 1, 0, 0), (1, 1, 1, 1)}                               |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+
|i2 : leafColorings(3,JCmodel)                                                |
|                                                                             |
|o2 = {({0, 0}, {0, 0}, {0, 0}), ({0, 0}, {0, 1}, {0, 1}), ({0, 0}, {1, 0},   |
|     ------------------------------------------------------------------------|
|     {1, 0}), ({0, 0}, {1, 1}, {1, 1}), ({0, 1}, {0, 0}, {0, 1}), ({0, 1},   |
|     ------------------------------------------------------------------------|
|     {0, 1}, {0, 0}), ({0, 1}, {1, 0}, {1, 1}), ({0, 1}, {1, 1}, {1, 0}),    |
|     ------------------------------------------------------------------------|
|     ({1, 0}, {0, 0}, {1, 0}), ({1, 0}, {0, 1}, {1, 1}), ({1, 0}, {1, 0}, {0,|
|     ------------------------------------------------------------------------|
|     0}), ({1, 0}, {1, 1}, {0, 1}), ({1, 1}, {0, 0}, {1, 1}), ({1, 1}, {0,   |
|     ------------------------------------------------------------------------|
|     1}, {1, 0}), ({1, 1}, {1, 0}, {0, 1}), ({1, 1}, {1, 1}, {0, 0})}        |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * qRing -- construct the ring of Fourier coordinates

Ways to use leafColorings:
==========================

  * "leafColorings(LeafTree,Model)"
  * "leafColorings(ZZ,Model)"

For the programmer
==================

The object leafColorings, is a method function (Macaulay2Doc).

LeafTree -- a tree described in terms of its leaves
***************************************************

Description
===========

A tree can be described in terms of its leaves by specifying a leaf set and
specifying the edges as partitions of the leaf set. This leaf centric
description is particularly useful for phylogenetic trees.

The main constructor method is leafTree.

+---------------------------------------------------------------------+
|i1 : T = leafTree({a,b,c,d},{{a,b}})                                 |
|                                                                     |
|o1 = {{a, b, c, d}, {set {a, b}, set {a}, set {b}, set {c}, set {d}}}|
|                                                                     |
|o1 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i2 : leaves T                                                        |
|                                                                     |
|o2 = set {c, d, a, b}                                                |
|                                                                     |
|o2 : Set                                                             |
+---------------------------------------------------------------------+
|i3 : edges T                                                         |
|                                                                     |
|o3 = {set {a, b}, set {a}, set {b}, set {c}, set {d}}                |
|                                                                     |
|o3 : List                                                            |
+---------------------------------------------------------------------+
|i4 : G = graph{{a,e},{b,e},{e,f},{c,f},{d,f}}                        |
|                                                                     |
|o4 = Graph{a => {e}      }                                           |
|           b => {e}                                                  |
|           c => {f}                                                  |
|           d => {f}                                                  |
|           e => {a, b, f}                                            |
|           f => {e, c, d}                                            |
|                                                                     |
|o4 : Graph                                                           |
+---------------------------------------------------------------------+
|i5 : leafTree G                                                      |
|                                                                     |
|o5 = {{a, b, c, d}, {set {a, b}, set {a}, set {b}, set {c}, set {d}}}|
|                                                                     |
|o5 : LeafTree                                                        |
+---------------------------------------------------------------------+

See also
========

  * leafTree -- construct a LeafTree

Methods that use an object of class LeafTree:
=============================================

  * digraph(LeafTree,List) -- convert a
    LeafTree to a Digraph
  * "digraph(LeafTree,Set)" -- see digraph(LeafTree,List),
    -- convert a LeafTree to a Digraph
  * "edgeContract(LeafTree,List)" -- see edgeContract, --
    contract an edge of a tree
  * "edgeContract(LeafTree,Set)" -- see edgeContract, --
    contract an edge of a tree
  * "edgeCut(LeafTree,List,Thing)" -- see edgeCut, -- break up a
    tree at an edge
  * "edgeCut(LeafTree,Set,Thing)" -- see edgeCut, -- break up a
    tree at an edge
  * edges(LeafTree) -- list the edges of a tree
  * graph(LeafTree) -- convert a LeafTree to Graph
  * "internalEdges(LeafTree)" -- see internalEdges, --
    list the internal edges of a tree
  * "internalVertices(LeafTree)" -- see internalVertices,
    -- list the internal vertices of a tree
  * "isIsomorphic(LeafTree,LeafTree)" -- see isIsomorphic,
    -- check isomorphism of two tree
  * "leafColorings(LeafTree,Model)" -- see leafColorings,
    -- list the consistent colorings of a tree
  * "LeafTree == LeafTree"
  * leaves(LeafTree) -- list the leaves of a tree
  * "phyloToric42(LeafTree,Model)" -- see phyloToric42, --
    compute the invariants of a group-based phylogenetic model with 4ti2
  * "phyloToricAMatrix(LeafTree,Model)" -- see phyloToricAMatrix,
    -- construct the design matrix of a group-based
    phylogenetic model
  * "phyloToricFP(LeafTree,Model)" -- see phyloToricFP, --
    compute the invariants of a group-based phylogenetic model with toric fiber
    products
  * "phyloToricLinears(LeafTree,Model)" -- see phyloToricLinears,
    -- compute the linear invariants of a group-based
    phylogenetic model
  * "phyloToricQuads(LeafTree,Model)" -- see phyloToricQuads,
    -- compute the quadratic invariants of a group-based
    phylogenetic model
  * "phyloToricRandom(LeafTree,Model)" -- see phyloToricRandom,
    -- compute a random invariant of a group-based
    phylogenetic model
  * "pRing(LeafTree,Model)" -- see pRing, -- construct the ring of
    probability coordinates
  * "qRing(LeafTree,Model)" -- see qRing, -- construct the ring of
    Fourier coordinates
  * "vertexCut(LeafTree,List,Thing,Thing)" -- see vertexCut,
    -- break up a tree at a vertex
  * "vertexCut(LeafTree,Set,Thing,Thing)" -- see vertexCut, --
    break up a tree at a vertex
  * vertices(LeafTree) -- list the vertices of a
    tree

For the programmer
==================

The object LeafTree, is a type (Macaulay2Doc), with
ancestor classes List (Macaulay2Doc), < VisibleList (Macaulay2Doc)
< BasicList (Macaulay2Doc) <
Thing (Macaulay2Doc).

leafTree -- construct a LeafTree
********************************

Synopsis
========

  * Usage:
        leafTree(n,E)
        leafTree(L,E)
        leafTree(G)
  * Inputs:
      * n, an integer (Macaulay2Doc), the number of leaves
      * L, a list (Macaulay2Doc), of leaves
      * E, a list (Macaulay2Doc), of lists or sets specifying the
        internal edges
      * G, a graph (Graphs), a tree
  * Outputs:
      * an instance of the type LeafTree,

Description
===========

An object of class LeafTree, is specified by listing its
leaves, and for each internal edge, the partition the edge induces on the set
of leaves. L is the set of leaves, or if an integer n is input then the leaves
will be named $0,\ldots,n-1$. E is a list with one entry for each internal
edge. Each entry is a partition specified as a list or set of the leaves in one
side of the partition. Thus each edge can be specified in two possible ways.

An object of class LeafTree, can also be constructed from a
Graph (Graphs), provided the graph has no cycles.

Here we construct the quartet tree, which is the tree with 4 leaves and one
internal edge.

+---------------------------------------------------------------------+
|i1 : T = leafTree({a,b,c,d},{{a,b}})                                 |
|                                                                     |
|o1 = {{a, b, c, d}, {set {a, b}, set {a}, set {b}, set {c}, set {d}}}|
|                                                                     |
|o1 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i2 : leaves T                                                        |
|                                                                     |
|o2 = set {c, d, a, b}                                                |
|                                                                     |
|o2 : Set                                                             |
+---------------------------------------------------------------------+
|i3 : edges T                                                         |
|                                                                     |
|o3 = {set {a, b}, set {a}, set {b}, set {c}, set {d}}                |
|                                                                     |
|o3 : List                                                            |
+---------------------------------------------------------------------+

Here is a tree with 5 leaves given as a Graph (Graphs).

+-----------------------------------------------------------------------------+
|i4 : G = graph{{a,b},{c,b},{b,d},{d,e},{d,f},{f,g},{f,h}}                    |
|                                                                             |
|o4 = Graph{a => {b}      }                                                   |
|           b => {a, c, d}                                                    |
|           c => {b}                                                          |
|           d => {b, e, f}                                                    |
|           e => {d}                                                          |
|           f => {d, g, h}                                                    |
|           g => {f}                                                          |
|           h => {f}                                                          |
|                                                                             |
|o4 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i5 : T = leafTree G                                                          |
|                                                                             |
|o5 = {{a, c, e, g, h}, {set {c, a}, set {c, e, a}, set {a}, set {c}, set {e},|
|     ------------------------------------------------------------------------|
|     set {g}, set {h}}}                                                      |
|                                                                             |
|o5 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i6 : leaves T                                                                |
|                                                                             |
|o6 = set {c, e, g, h, a}                                                     |
|                                                                             |
|o6 : Set                                                                     |
+-----------------------------------------------------------------------------+
|i7 : internalEdges T                                                         |
|                                                                             |
|o7 = {set {c, a}, set {c, e, a}}                                             |
|                                                                             |
|o7 : List                                                                    |
+-----------------------------------------------------------------------------+

Ways to use leafTree:
=====================

  * "leafTree(Graph)"
  * "leafTree(List,List)"
  * "leafTree(ZZ,List)"

For the programmer
==================

The object leafTree, is a method function (Macaulay2Doc).

leaves(LeafTree) -- list the leaves of a tree
*********************************************

Synopsis
========

  * Function: leaves (Graphs),
  * Usage:
        leaves T
  * Inputs:
      * T, an instance of the type LeafTree,
  * Outputs:
      * a set (Macaulay2Doc), the leaves of T

Description
===========

This function outputs the leaves of the tree as an object of class Set (Macaulay2Doc).

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}});                                                |
+-----------------------------------------------------------------------------+
|i2 : vertices T                                                              |
|                                                                             |
|o2 = {set {set {3}, set {2}, set {0, 1}}, set {set {0, 1, 2}}, set {set {0,  |
|     ------------------------------------------------------------------------|
|     1, 3}}, set {set {1}, set {2, 3}, set {0}}, set {set {0, 2, 3}}, set    |
|     ------------------------------------------------------------------------|
|     {set {1, 2, 3}}}                                                        |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : #(vertices T)                                                           |
|                                                                             |
|o3 = 6                                                                       |
+-----------------------------------------------------------------------------+

Caveat
======

The leaves have a different representation from the one in the output of
vertices(LeafTree).

See also
========

  * vertices(LeafTree) -- list the vertices of a
    tree

Ways to use this method:
========================

  * leaves(LeafTree) -- list the leaves of a tree

Model -- a group-based model
****************************

Description
===========

A phylogenetic tree model on tree $T$ has outcomes that are described by
assigning each leaf of the tree any label from a particular set (typically the
label set is the set of DNA bases, \{A,T,C,G\}). The probability of a certain
assignment of labels depends on transition probabilities between each ordered
pair of labels. These transition probabilities are the parameters of the model.

In a group based model, the label set is a group $G$ (typically $\mathbb{Z}/2$
or $(\mathbb{Z}/2)^2$), and the transition probability for a pair $(g,h)$
depends only on $h-g$. This reduces the number of parameters from $|G|^2$ to
$|G|$. Depending on the model, further identifications of parameters are
imposed.

An object of class Model, stores the information about a
group-based model required to compute phylogenetic invariants. This information
includes the elements of the group, how those elements are partitioned, and a
set of automorphisms of the group that preserve the partitions.

There are four built-in models: Cavender-Farris-Neyman or binary model (see
CFNmodel); Jukes-Cantor model (see JCmodel); Kimura
2-parameter model (see K2Pmodel); and Kimura 3-parameter model
(see K3Pmodel).  Other models can be constructed with model.

+---------------------------------------------+
|i1 : M = CFNmodel                            |
|                                             |
|o1 = Model{AList => HashTable{0 => {1, 0}}}  |
|                              1 => {0, 1}    |
|           Automorphisms => HashTable{}      |
|           Buckets => {{0}, {1}}             |
|           Group => {0, 1}                   |
|                                             |
|o1 : Model                                   |
+---------------------------------------------+
|i2 : T = leafTree(3,{})                      |
|                                             |
|o2 = {{0, 1, 2}, {set {0}, set {1}, set {2}}}|
|                                             |
|o2 : LeafTree                                |
+---------------------------------------------+
|i3 : phyloToricAMatrix(T,M)                  |
|                                             |
|o3 = | 1 1 0 0 |                             |
|     | 0 0 1 1 |                             |
|     | 1 0 1 0 |                             |
|     | 0 1 0 1 |                             |
|     | 1 0 0 1 |                             |
|     | 0 1 1 0 |                             |
|                                             |
|              6       4                      |
|o3 : Matrix ZZ  <-- ZZ                       |
+---------------------------------------------+

See also
========

  * model -- construct a Model

Methods that use an object of class Model:
==========================================

  * "buckets(Model)" -- see buckets, -- the equivalence classes
    of group elements of a Model
  * "fourierToProbability(Ring,Ring,ZZ,Model)" -- see
    fourierToProbability, -- map from Fourier coordinates
    to probability coordinates
  * "group(Model)" -- see group, -- the group of a Model
  * "leafColorings(LeafTree,Model)" -- see leafColorings,
    -- list the consistent colorings of a tree
  * "leafColorings(ZZ,Model)" -- see leafColorings, --
    list the consistent colorings of a tree
  * "phyloToric42(Graph,Model)" -- see phyloToric42, --
    compute the invariants of a group-based phylogenetic model with 4ti2
  * "phyloToric42(LeafTree,Model)" -- see phyloToric42, --
    compute the invariants of a group-based phylogenetic model with 4ti2
  * "phyloToric42(ZZ,List,Model)" -- see phyloToric42, --
    compute the invariants of a group-based phylogenetic model with 4ti2
  * "phyloToricAMatrix(Graph,Model)" -- see phyloToricAMatrix,
    -- construct the design matrix of a group-based
    phylogenetic model
  * "phyloToricAMatrix(LeafTree,Model)" -- see phyloToricAMatrix,
    -- construct the design matrix of a group-based
    phylogenetic model
  * "phyloToricAMatrix(ZZ,List,Model)" -- see phyloToricAMatrix,
    -- construct the design matrix of a group-based
    phylogenetic model
  * "phyloToricFP(LeafTree,Model)" -- see phyloToricFP, --
    compute the invariants of a group-based phylogenetic model with toric fiber
    products
  * "phyloToricFP(ZZ,List,Model)" -- see phyloToricFP, --
    compute the invariants of a group-based phylogenetic model with toric fiber
    products
  * "phyloToricLinears(LeafTree,Model)" -- see phyloToricLinears,
    -- compute the linear invariants of a group-based
    phylogenetic model
  * "phyloToricLinears(ZZ,List,Model)" -- see phyloToricLinears,
    -- compute the linear invariants of a group-based
    phylogenetic model
  * "phyloToricQuads(LeafTree,Model)" -- see phyloToricQuads,
    -- compute the quadratic invariants of a group-based
    phylogenetic model
  * "phyloToricQuads(ZZ,List,Model)" -- see phyloToricQuads,
    -- compute the quadratic invariants of a group-based
    phylogenetic model
  * "phyloToricRandom(LeafTree,Model)" -- see phyloToricRandom,
    -- compute a random invariant of a group-based
    phylogenetic model
  * "phyloToricRandom(ZZ,List,Model)" -- see phyloToricRandom,
    -- compute a random invariant of a group-based
    phylogenetic model
  * "pRing(LeafTree,Model)" -- see pRing, -- construct the ring of
    probability coordinates
  * "pRing(ZZ,Model)" -- see pRing, -- construct the ring of
    probability coordinates
  * "qRing(LeafTree,Model)" -- see qRing, -- construct the ring of
    Fourier coordinates
  * "qRing(ZZ,Model)" -- see qRing, -- construct the ring of
    Fourier coordinates

For the programmer
==================

The object Model, is a type (Macaulay2Doc), with
ancestor classes HashTable (Macaulay2Doc), < Thing (Macaulay2Doc).

model -- construct a Model
**************************

Synopsis
========

  * Usage:
        model(G,B,aut)
  * Inputs:
      * G, a list (Macaulay2Doc), the group elements
      * B, a list (Macaulay2Doc), of lists of which group elements
        have identified parameters
      * aut, a list (Macaulay2Doc), of pairs, assigning pairs of
        identified group elements to automorphisms of the group that switch the
        pair
  * Outputs:
      * an instance of the type Model,

Description
===========

The elements of G must have an addition operation meaning that if two elements
$g, h \in G$, then $g+h$ must work.  The usual choices for G are the list of
elements of $\mathbb{Z}/2$ or $(\mathbb{Z}/2)^2$.

+-------------------------------------+
|i1 : (a,b) = (0_(ZZ/2),1_(ZZ/2))     |
|                                     |
|o1 = (0, 1)                          |
|                                     |
|o1 : Sequence                        |
+-------------------------------------+
|i2 : G = {{a,a}, {a,b}, {b,a}, {b,b}}|
|                                     |
|o2 = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}|
|                                     |
|o2 : List                            |
+-------------------------------------+

The elements of B are lists of the elements of G with the same parameter value.

In the following example, the first two elements of G receive distinct
parameters, while the last two share a parameter. This is precisely the Kimura
2-parameter model.

+-------------------------------------------+
|i3 : B = {{G#0}, {G#1}, {G#2,G#3}}         |
|                                           |
|o3 = {{{0, 0}}, {{0, 1}}, {{1, 0}, {1, 1}}}|
|                                           |
|o3 : List                                  |
+-------------------------------------------+

Finally, for every ordered pair of group elements sharing a parameter, aut must
provide an automorphism of the group that switches those two group elements.
In aut all of the group elements are identified by their index in $G$, and an
automorphism is given by a list of permuted index values.

In our example, the pairs requiring an automorphism are \{2,3\} and \{3,2\}.

+-----------------------------------------------------------------------------+
|i4 : aut = {({2,3}, {0,1,3,2}),                                              |
|            ({3,2}, {0,1,3,2})}                                              |
|                                                                             |
|o4 = {({2, 3}, {0, 1, 3, 2}), ({3, 2}, {0, 1, 3, 2})}                        |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+
|i5 : model(G,B,aut)                                                          |
|                                                                             |
|o5 = Model{AList => HashTable{{0, 0} => {1, 0, 0}}                          }|
|                              {0, 1} => {0, 1, 0}                            |
|                              {1, 0} => {0, 0, 1}                            |
|                              {1, 1} => {0, 0, 1}                            |
|           Automorphisms => HashTable{{2, 3} => HashTable{{0, 0} => {0, 0}}} |
|                                                          {0, 1} => {0, 1}   |
|                                                          {1, 0} => {1, 1}   |
|                                                          {1, 1} => {1, 0}   |
|                                      {3, 2} => HashTable{{0, 0} => {0, 0}}  |
|                                                          {0, 1} => {0, 1}   |
|                                                          {1, 0} => {1, 1}   |
|                                                          {1, 1} => {1, 0}   |
|           Buckets => {{{0, 0}}, {{0, 1}}, {{1, 0}, {1, 1}}}                 |
|           Group => {{0, 0}, {0, 1}, {1, 0}, {1, 1}}                         |
|                                                                             |
|o5 : Model                                                                   |
+-----------------------------------------------------------------------------+

See also
========

  * Model -- a group-based model

Ways to use model:
==================

  * "model(List,List,List)"

For the programmer
==================

The object model, is a method function (Macaulay2Doc).

phyloToric42 -- compute the invariants of a group-based phylogenetic model with 4ti2
************************************************************************************

Synopsis
========

  * Usage:
        phyloToric42(n,E,M)
        phyloToric42(G,M)
        phyloToric42(T,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * E, an instance of the type LeafTree, the internal
        edges of the tree, given by one part of the bipartition on leaves
      * G, a graph (Graphs), a tree
      * M, an instance of the type Model,
  * Optional inputs (Macaulay2Doc),:
      * QRing, => ..., default value null, optional argument to
        specify Fourier coordinate ring
  * Outputs:
      * an ideal (Macaulay2Doc),

Description
===========

This function computes the invariants of a group-based phylogenetic tree model
by computing the transpose of the matrix that encodes the defining monomial map
and then using the function toricMarkov of the FourTiTwo,
package.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4, {{0,1}})                                                |
|                                                                             |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}        |
|                                                                             |
|o1 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i2 : phyloToric42(T, CFNmodel)                                               |
|                                                                             |
|o2 = ideal (- q       q        + q       q       , - q       q        +      |
|               0,1,1,0 1,0,0,1    0,1,0,1 1,0,1,0     0,0,1,1 1,1,0,0        |
|     ------------------------------------------------------------------------|
|     q       q       )                                                       |
|      0,0,0,0 1,1,1,1                                                        |
|                                                                             |
|o2 : Ideal of QQ[q       , q       , q       , q       , q       , q       , |
|                  0,0,0,0   0,0,1,1   0,1,0,1   0,1,1,0   1,0,0,1   1,0,1,0  |
|-----------------------------------------------------------------------------|
|q       , q       ]                                                          |
| 1,1,0,0   1,1,1,1                                                           |
+-----------------------------------------------------------------------------+

See also
========

  * phyloToricFP -- compute the invariants of a
    group-based phylogenetic model with toric fiber products

Ways to use phyloToric42:
=========================

  * "phyloToric42(Graph,Model)"
  * "phyloToric42(LeafTree,Model)"
  * "phyloToric42(ZZ,List,Model)"

For the programmer
==================

The object phyloToric42, is a method function with options (Macaulay2Doc).

phyloToricAMatrix -- construct the design matrix of a group-based phylogenetic model
************************************************************************************

Synopsis
========

  * Usage:
        phyloToricAMatrix(T,M)
        phyloToricAmatrix(G,M)
        phyloToricAMatrix(n,E,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * G, a graph (Graphs), a tree
      * n, an integer (Macaulay2Doc), the number of leaves
      * E, a list (Macaulay2Doc), the internal edges of the tree,
        given by the half the partition on leaves
      * M, an instance of the type Model,
  * Outputs:
      * a matrix (Macaulay2Doc), whose columns parametrize the
        toric variety

Description
===========

+--------------------------------------------+
|i1 : phyloToricAMatrix(4, {{1, 2}},CFNmodel)|
|                                            |
|o1 = | 1 0 0 1 1 0 0 1 |                    |
|     | 0 1 1 0 0 1 1 0 |                    |
|     | 1 1 1 1 0 0 0 0 |                    |
|     | 0 0 0 0 1 1 1 1 |                    |
|     | 1 1 0 0 1 1 0 0 |                    |
|     | 0 0 1 1 0 0 1 1 |                    |
|     | 1 0 1 0 1 0 1 0 |                    |
|     | 0 1 0 1 0 1 0 1 |                    |
|     | 1 0 0 1 0 1 1 0 |                    |
|     | 0 1 1 0 1 0 0 1 |                    |
|                                            |
|              10       8                    |
|o1 : Matrix ZZ   <-- ZZ                     |
+--------------------------------------------+

Ways to use phyloToricAMatrix:
==============================

  * "phyloToricAMatrix(Graph,Model)"
  * "phyloToricAMatrix(LeafTree,Model)"
  * "phyloToricAMatrix(ZZ,List,Model)"

For the programmer
==================

The object phyloToricAMatrix, is a method function (Macaulay2Doc).

phyloToricFP -- compute the invariants of a group-based phylogenetic model with toric fiber products
****************************************************************************************************

Synopsis
========

  * Usage:
        phyloToricFP(T,M)
        phyloToricFP(n,E,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * E, an instance of the type LeafTree, the internal
        edges of the tree, given by one part of the bipartition on leaves
      * M, an instance of the type Model,
  * Optional inputs (Macaulay2Doc),:
      * QRing, => ..., default value null, optional argument to
        specify Fourier coordinate ring
  * Outputs:
      * an ideal (Macaulay2Doc),

Description
===========

This function computes the invariants of a group-based phylogenetic tree model
based on Theorem 24 of the paper Toric Ideals of Phylogenetic Invariants by
Sturmfels and Sullivant.

Invariants are formed in three different ways.  The linear and quadratic
invariants are computed as in phyloToricLinears, and
phyloToricQuads, respectively.  Finally higher degree
invariants are built using a toric fiber product construction from the
invariants of claw trees.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4, {{0,1}})                                                |
|                                                                             |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}        |
|                                                                             |
|o1 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i2 : phyloToricFP(T, CFNmodel)                                               |
|                                                                             |
|o2 = ideal (- q       q        + q       q       , q       q        -        |
|               0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1   0,0,1,1 1,1,0,0          |
|     ------------------------------------------------------------------------|
|     q       q       , q       q        - q       q       , -                |
|      0,0,0,0 1,1,1,1   0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1                   |
|     ------------------------------------------------------------------------|
|     q       q        + q       q       , - q       q        +               |
|      0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1     0,1,1,0 1,0,0,1                 |
|     ------------------------------------------------------------------------|
|     q       q       , q       q        - q       q       , q       q        |
|      0,1,0,1 1,0,1,0   0,1,1,0 1,0,0,1    0,1,0,1 1,0,1,0   0,1,1,0 1,0,0,1 |
|     ------------------------------------------------------------------------|
|     - q       q       , - q       q        + q       q       )              |
|        0,1,0,1 1,0,1,0     0,1,1,0 1,0,0,1    0,1,0,1 1,0,1,0               |
|                                                                             |
|o2 : Ideal of QQ[q       , q       , q       , q       , q       , q       , |
|                  0,0,0,0   0,0,1,1   0,1,0,1   0,1,1,0   1,0,0,1   1,0,1,0  |
|-----------------------------------------------------------------------------|
|q       , q       ]                                                          |
| 1,1,0,0   1,1,1,1                                                           |
+-----------------------------------------------------------------------------+

See also
========

  * phyloToric42 -- compute the invariants of a
    group-based phylogenetic model with 4ti2

Ways to use phyloToricFP:
=========================

  * "phyloToricFP(LeafTree,Model)"
  * "phyloToricFP(ZZ,List,Model)"

For the programmer
==================

The object phyloToricFP, is a method function with options (Macaulay2Doc).

phyloToricLinears -- compute the linear invariants of a group-based phylogenetic model
**************************************************************************************

Synopsis
========

  * Usage:
        phyloToricLinears(T,M)
        phyloToricLinears(n,E,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * E, a list (Macaulay2Doc), the internal edges of the tree,
        given by one part of the bipartition on leaves
      * M, an instance of the type Model,
  * Optional inputs (Macaulay2Doc),:
      * QRing, => ..., default value null, optional argument to
        specify Fourier coordinate ring
      * Random => ..., default value false
  * Outputs:
      * a list (Macaulay2Doc), a generating set of the linear
        invariants

Description
===========

For models such as Jukes-Cantor (see JCmodel) and Kimura
2-parameter (see K2Pmodel), multiple variables in the Fourier
coordinates may map to the same monomial under the monomial map that defines
the toric variety of the model.  These equivalencies give rise to linear
relations in the space of Fourier coordinates.

The number of linear invariants is the codimension of the smallest linear
subspace in which the toric variety of the model is contained.

The optional argument QRing, can be passed the ring of Fourier
coordinates.  Otherwise the function will create a new ring.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(3,{})                                                      |
|                                                                             |
|o1 = {{0, 1, 2}, {set {0}, set {1}, set {2}}}                                |
|                                                                             |
|o1 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i2 : S = qRing(T, K2Pmodel)                                                  |
|                                                                             |
|o2 = S                                                                       |
|                                                                             |
|o2 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i3 : phyloToricLinears(T, K2Pmodel, QRing=>S)                                |
|                                                                             |
|o3 = {q      - q     , q      - q     , q      - q     , q      - q     ,    |
|       1,2,3    1,3,2   2,1,3    3,1,2   2,3,1    3,2,1   2,2,0    3,3,0     |
|     ------------------------------------------------------------------------|
|     q      - q     , q      - q     }                                       |
|      2,0,2    3,0,3   0,2,2    0,3,3                                        |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * phyloToricFP -- compute the invariants of a
    group-based phylogenetic model with toric fiber products
  * phyloToric42 -- compute the invariants of a
    group-based phylogenetic model with 4ti2
  * phyloToricQuads -- compute the quadratic invariants
    of a group-based phylogenetic model

Ways to use phyloToricLinears:
==============================

  * "phyloToricLinears(LeafTree,Model)"
  * "phyloToricLinears(ZZ,List,Model)"

For the programmer
==================

The object phyloToricLinears, is a method function with options (Macaulay2Doc).

phyloToricQuads -- compute the quadratic invariants of a group-based phylogenetic model
***************************************************************************************

Synopsis
========

  * Usage:
        phyloToricQuads(T,M)
        phyloToricQuads(n,E,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * E, a list (Macaulay2Doc), the internal edges of the tree,
        given by one part of the bipartition on leaves
      * M, an instance of the type Model,
  * Optional inputs (Macaulay2Doc),:
      * QRing, => ..., default value null, optional argument to
        specify Fourier coordinate ring
      * Random => ..., default value false
  * Outputs:
      * a list (Macaulay2Doc), a generating set of the quadratic
        invariants

Description
===========

The quadratic invariants are also referred to as the edge invariants of the
model.

Each Fourier coordinate corresponds to a consistent coloring of the edges of
tree T. For any given internal edge e of T, the consistent colorings can be
obtained by coloring two smaller graphs and gluing them along e.  This
corresponds to a fiber product on the corresponding toric varieties. The
quadratic invariants naturally arise from this process by gluing a pair of
colorings of one small graph to a pair of colorings of the other small graph in
two different ways.

The optional argument QRing, can be passed the ring of Fourier
coordinates.  Otherwise the function will create a new ring.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}})                                                 |
|                                                                             |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}        |
|                                                                             |
|o1 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i2 : S = qRing(T, CFNmodel)                                                  |
|                                                                             |
|o2 = S                                                                       |
|                                                                             |
|o2 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i3 : phyloToricQuads(T, CFNmodel, QRing=>S)                                  |
|                                                                             |
|o3 = {- q       q        + q       q       , q       q        -              |
|         0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1   0,0,1,1 1,1,0,0                |
|     ------------------------------------------------------------------------|
|     q       q       , q       q        - q       q       , -                |
|      0,0,0,0 1,1,1,1   0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1                   |
|     ------------------------------------------------------------------------|
|     q       q        + q       q       , - q       q        +               |
|      0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1     0,1,1,0 1,0,0,1                 |
|     ------------------------------------------------------------------------|
|     q       q       , q       q        - q       q       , q       q        |
|      0,1,0,1 1,0,1,0   0,1,1,0 1,0,0,1    0,1,0,1 1,0,1,0   0,1,1,0 1,0,0,1 |
|     ------------------------------------------------------------------------|
|     - q       q       , - q       q        + q       q       }              |
|        0,1,0,1 1,0,1,0     0,1,1,0 1,0,0,1    0,1,0,1 1,0,1,0               |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * phyloToricFP -- compute the invariants of a
    group-based phylogenetic model with toric fiber products
  * phyloToric42 -- compute the invariants of a
    group-based phylogenetic model with 4ti2
  * phyloToricLinears -- compute the linear
    invariants of a group-based phylogenetic model

Ways to use phyloToricQuads:
============================

  * "phyloToricQuads(LeafTree,Model)"
  * "phyloToricQuads(ZZ,List,Model)"

For the programmer
==================

The object phyloToricQuads, is a method function with options (Macaulay2Doc).

phyloToricRandom -- compute a random invariant of a group-based phylogenetic model
**********************************************************************************

Synopsis
========

  * Usage:
        phyloToricRandom(T,M)
        phyloToricRandom(n,E,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * E, an instance of the type LeafTree, the internal
        edges of the tree, given by one part of the bipartition on leaves
      * M, an instance of the type Model,
  * Optional inputs (Macaulay2Doc),:
      * QRing, => ..., default value null, optional argument to
        specify Fourier coordinate ring
  * Outputs:
      * a ring element (Macaulay2Doc), a randomly selected
        binomial invariant

Description
===========

This function computes a random invariant of a group-based phylogenetic tree
model using the toric fiber product structure.

With equal probability the algorithm decides to return a linear, quadratic, or
higher degree binomial.  It then selects one of these at random (but uniformity
is not guaranteed).

This is a much more efficient way to produce a single generator than listing
all of them, which is useful for Monte Carlo random walk algorithms.

+-----------------------------------------------------------------------------+
|i1 : phyloToricRandom(4,{{0,1}},CFNmodel)                                    |
|                                                                             |
|o1 = - q       q        + q       q                                          |
|        0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1                                   |
|                                                                             |
|o1 : QQ[q       , q       , q       , q       , q       , q       , q       ,|
|         0,0,0,0   0,0,1,1   0,1,0,1   0,1,1,0   1,0,0,1   1,0,1,0   1,1,0,0 |
|-----------------------------------------------------------------------------|
|q       ]                                                                    |
| 1,1,1,1                                                                     |
+-----------------------------------------------------------------------------+

Caveat
======

We currently do not guarantee a uniform distribution on the generators, even
after the choice of linear, quadratic or higher degree.

See also
========

  * phyloToricFP -- compute the invariants of a
    group-based phylogenetic model with toric fiber products

Ways to use phyloToricRandom:
=============================

  * "phyloToricRandom(LeafTree,Model)"
  * "phyloToricRandom(ZZ,List,Model)"

For the programmer
==================

The object phyloToricRandom, is a method function with options (Macaulay2Doc).

pRing -- construct the ring of probability coordinates
******************************************************

Synopsis
========

  * Usage:
        pRing(T,M)
        pRing(n,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * M, an instance of the type Model,
  * Optional inputs (Macaulay2Doc),:
      * Variable => ..., default value null
  * Outputs:
      * a ring (Macaulay2Doc), of probability coordinates

Description
===========

The probability coordinates for a phylogenetic tree model have one coordinate
for each possible outcome of the model. A possible outcome is any labeling of
the leaves of the tree by elements of the group $G$ of the model. Thus the
number of coordinates is $|G|^n$ where $n$ is the number of leaves.

A variable name for the ring can be passed using the optional argument
Variable. Otherwise the symbol p is used.

+---------------------------+
|i1 : pRing(4,CFNmodel)     |
|                           |
|o1 = QQ[p       ..p       ]|
|         0,0,0,0   1,1,1,1 |
|                           |
|o1 : PolynomialRing        |
+---------------------------+
|i2 : pRing(3,JCmodel)      |
|                           |
|o2 = QQ[p     ..p     ]    |
|         0,0,0   3,3,3     |
|                           |
|o2 : PolynomialRing        |
+---------------------------+

See also
========

  * qRing -- construct the ring of Fourier coordinates

Ways to use pRing:
==================

  * "pRing(LeafTree,Model)"
  * "pRing(ZZ,Model)"

For the programmer
==================

The object pRing, is a method function with options (Macaulay2Doc).

QRing -- optional argument to specify Fourier coordinate ring
*************************************************************

Description
===========

For any of the functions that produce phylogenetic invariants in the ring of
Fourier coordinates, the ring can be specified with this optional argument. If
null is passed then a new ring of Fourier coordinates will be created.

The ring passed can be any polynomial ring with sufficiently many variables.
The sufficient number is $k = |G|^{n-1}$ where $G$ is the group of labels used
by the model, and $n$ is the number of leaves of the phylogenetic tree. The
ring may have more than $k$ variables, in which case only the first $k$ will be
used.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}})                                                 |
|                                                                             |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}        |
|                                                                             |
|o1 : LeafTree                                                                |
+-----------------------------------------------------------------------------+
|i2 : phyloToricFP(T,CFNmodel)                                                |
|                                                                             |
|o2 = ideal (- q       q        + q       q       , q       q        -        |
|               0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1   0,0,1,1 1,1,0,0          |
|     ------------------------------------------------------------------------|
|     q       q       , q       q        - q       q       , -                |
|      0,0,0,0 1,1,1,1   0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1                   |
|     ------------------------------------------------------------------------|
|     q       q        + q       q       , - q       q        +               |
|      0,0,1,1 1,1,0,0    0,0,0,0 1,1,1,1     0,1,1,0 1,0,0,1                 |
|     ------------------------------------------------------------------------|
|     q       q       , q       q        - q       q       , q       q        |
|      0,1,0,1 1,0,1,0   0,1,1,0 1,0,0,1    0,1,0,1 1,0,1,0   0,1,1,0 1,0,0,1 |
|     ------------------------------------------------------------------------|
|     - q       q       , - q       q        + q       q       )              |
|        0,1,0,1 1,0,1,0     0,1,1,0 1,0,0,1    0,1,0,1 1,0,1,0               |
|                                                                             |
|o2 : Ideal of QQ[q       , q       , q       , q       , q       , q       , |
|                  0,0,0,0   0,0,1,1   0,1,0,1   0,1,1,0   1,0,0,1   1,0,1,0  |
|-----------------------------------------------------------------------------|
|q       , q       ]                                                          |
| 1,1,0,0   1,1,1,1                                                           |
+-----------------------------------------------------------------------------+
|i3 : S = QQ[a..h]                                                            |
|                                                                             |
|o3 = S                                                                       |
|                                                                             |
|o3 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i4 : phyloToricFP(T,CFNmodel,QRing=>S)                                       |
|                                                                             |
|o4 = ideal (- b*g + a*h, b*g - a*h, b*g - a*h, - b*g + a*h, - d*e + c*f, d*e |
|     ------------------------------------------------------------------------|
|     - c*f, d*e - c*f, - d*e + c*f)                                          |
|                                                                             |
|o4 : Ideal of S                                                              |
+-----------------------------------------------------------------------------+

Functions with optional argument named QRing:
=============================================

  * "phyloToric42(...,QRing=>...)"
  * "phyloToricFP(...,QRing=>...)"
  * "phyloToricLinears(...,QRing=>...)"
  * "phyloToricQuads(...,QRing=>...)"
  * "phyloToricRandom(...,QRing=>...)"

For the programmer
==================

The object QRing, is a symbol (Macaulay2Doc).

qRing -- construct the ring of Fourier coordinates
**************************************************

Synopsis
========

  * Usage:
        qRing(T,M)
        qRing(n,M)
  * Inputs:
      * T, an instance of the type LeafTree,
      * n, an integer (Macaulay2Doc), the number of leaves
      * M, an instance of the type Model,
  * Optional inputs (Macaulay2Doc),:
      * Variable => ..., default value null
  * Outputs:
      * a ring (Macaulay2Doc), of Fourier coordinates

Description
===========

The Fourier coordinates for a phylogenetic tree model have one coordinate for
each consistent coloring of the tree T.  A consistent coloring is an assignment
of one of the group elements of the model M to each of the leaves of T such
that the sum of all the group elements assigned is $0$.

Each variable of the ring is indexed by a sequence representing a consistent
coloring with each element of the group represented by an integer between $0$
and $m-1$ where $m$ is the order of the group.

A variable name for the ring can be passed using the optional argument
Variable. Otherwise the symbol q is used.

+-----------------------------------------------------------------------------+
|i1 : qRing(4,CFNmodel)                                                       |
|                                                                             |
|o1 = QQ[q       , q       , q       , q       , q       , q       , q       ,|
|         0,0,0,0   0,0,1,1   0,1,0,1   0,1,1,0   1,0,0,1   1,0,1,0   1,1,0,0 |
|                                                                             |
|o1 : PolynomialRing                                                          |
|-----------------------------------------------------------------------------|
|q       ]                                                                    |
| 1,1,1,1                                                                     |
+-----------------------------------------------------------------------------+
|i2 : qRing(3,JCmodel)                                                        |
|                                                                             |
|o2 = QQ[q     , q     , q     , q     , q     , q     , q     , q     ,      |
|         0,0,0   0,1,1   0,2,2   0,3,3   1,0,1   1,1,0   1,2,3   1,3,2       |
|                                                                             |
|o2 : PolynomialRing                                                          |
|-----------------------------------------------------------------------------|
|q     , q     , q     , q     , q     , q     , q     , q     ]              |
| 2,0,2   2,1,3   2,2,0   2,3,1   3,0,3   3,1,2   3,2,1   3,3,0               |
+-----------------------------------------------------------------------------+

See also
========

  * pRing -- construct the ring of probability coordinates
  * leafColorings -- list the consistent colorings of a
    tree

Ways to use qRing:
==================

  * "qRing(LeafTree,Model)"
  * "qRing(ZZ,Model)"

For the programmer
==================

The object qRing, is a method function with options (Macaulay2Doc).

rootedBinaryTrees -- enumerate all rooted binary trees
******************************************************

Synopsis
========

  * Usage:
        rootedBinaryTrees n
  * Inputs:
      * n, an integer (Macaulay2Doc), the number of leaves
  * Outputs:
      * a list (Macaulay2Doc), of all rooted binary LeafTree,
        s with n leaves

Description
===========

This function enumerates all possible binary trees with a distinguished root
and n-1 unlabeled leaves. Each tree is an object of class LeafTree.
For the purposes of representation, the root is named $0$ and the
unlabeled leaves are named $1,\ldots,n-1$.  In other words each class of
unlabeled rooted tree is represented once by a particular labeling of that
tree.

+-----------------------------------------------------------------------------+
|i1 : L = rootedBinaryTrees 5                                                 |
|                                                                             |
|o1 = {{{0, 1, 2, 3, 4}, {set {4, 2, 3}, set {4, 3}, set {0}, set {1}, set    |
|     ------------------------------------------------------------------------|
|     {2}, set {3}, set {4}}}, {{0, 1, 2, 3, 4}, {set {1, 2}, set {4, 3}, set |
|     ------------------------------------------------------------------------|
|     {0}, set {1}, set {2}, set {3}, set {4}}}}                              |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * labeledTrees -- enumerate all labeled trees
  * labeledBinaryTrees -- enumerate all binary
    labeled trees
  * rootedTrees -- enumerate all rooted trees
  * unlabeledTrees -- enumerate all unlabeled trees

Ways to use rootedBinaryTrees:
==============================

  * "rootedBinaryTrees(ZZ)"

For the programmer
==================

The object rootedBinaryTrees, is a method function (Macaulay2Doc).

rootedTrees -- enumerate all rooted trees
*****************************************

Synopsis
========

  * Usage:
        rootedTrees n
  * Inputs:
      * n, an integer (Macaulay2Doc), the number of leaves
  * Outputs:
      * a list (Macaulay2Doc), of all rooted trees with $n$ leaves

Description
===========

This function enumerates all possible homeomorphically-reduced trees (no
degree-2 vertices) with a distinguished root and n-1 unlabeled leaves. Each
tree is an object of class LeafTree.  For the purposes of
representation, the root is named 0 and the unlabeled leaves are named
$1,\ldots,n-1$. In other words each class of unlabeled rooted tree is
represented once by a particular labeling of that tree.

+-----------------------------------------------------------------------------+
|i1 : L = rootedTrees 4                                                       |
|                                                                             |
|o1 = {{{0, 1, 2, 3}, {set {1, 2}, set {0}, set {1}, set {2}, set {3}}}, {{0, |
|     ------------------------------------------------------------------------|
|     1, 2, 3}, {set {0}, set {1}, set {2}, set {3}}}}                        |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * labeledTrees -- enumerate all labeled trees
  * labeledBinaryTrees -- enumerate all binary
    labeled trees
  * rootedBinaryTrees -- enumerate all rooted binary
    trees
  * unlabeledTrees -- enumerate all unlabeled trees

Ways to use rootedTrees:
========================

  * "rootedTrees(ZZ)"

For the programmer
==================

The object rootedTrees, is a method function (Macaulay2Doc).

secant -- compute the secant of an ideal
****************************************

Synopsis
========

  * Usage:
        secant(I,n)
  * Inputs:
      * I, an ideal (Macaulay2Doc),
      * k, an integer (Macaulay2Doc), order of the secant
  * Optional inputs (Macaulay2Doc),:
      * DegreeLimit => ..., default value {}
  * Outputs:
      * an ideal (Macaulay2Doc), the kth secant of I

Description
===========

This function computes the kth secant of I by constructing the abstract secant
and then projecting with elimination.

Here the kth secant means the join of k copies of I. Setting k to 1 gives the
dimension of the ideal, while 2 is the usual secant, and higher values
correspond to higher order secants.

Setting the optional argument DegreeLimit (Macaulay2Doc), to
\{d\}  will produce only the generators of the secant ideal up to degree d.

This method is general and will work for arbitrary polynomial ideals, not just
phylogenetic ideals.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..d]                                                            |
|                                                                             |
|o1 = R                                                                       |
|                                                                             |
|o1 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i2 : I = ideal {a^2-b,a^3-c,a^4-d}                                           |
|                                                                             |
|             2       3       4                                               |
|o2 = ideal (a  - b, a  - c, a  - d)                                          |
|                                                                             |
|o2 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i3 : secant(I,2)                                                             |
|                                                                             |
|             3             2      2            2    2                2     2 |
|o3 = ideal (b  - 2a*b*c + a d + 2c  - 2b*d, a*b  - a c - b*c + a*d, a b - b  |
|     ------------------------------------------------------------------------|
|                   3                                                         |
|     - 2a*c + 2d, a  - 3a*b + 2c)                                            |
|                                                                             |
|o3 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

See also
========

  * joinIdeal -- compute the join of several ideals

Ways to use secant:
===================

  * "secant(Ideal,ZZ)"

For the programmer
==================

The object secant, is a method function with options (Macaulay2Doc).

toricJoinDim -- dimension of a join of toric varieties
******************************************************

Synopsis
========

  * Usage:
        toricJoinDim(A,B)
        toricJoinDim L
  * Inputs:
      * A, a matrix (Macaulay2Doc), the A-matrix of a toric
        variety
      * B, a matrix (Macaulay2Doc), the A-matrix of a toric
        variety
      * L, a list (Macaulay2Doc), of A-matrices of toric varieties
  * Outputs:
      * an integer (Macaulay2Doc), the dimension of the join of the
        toric varieties defined by the matrices

Description
===========

A randomized algorithm for computing the affine dimension of a join of toric
varieties using Terracini's Lemma.

Each input matrix defines a parameterization of the variety.  For each variety,
a vector of parameter values is chosen at random from a large finite field.
The dimension of the sum of the tangent spaces at those points is computed.

This algorithm is much much faster than computing the join variety.

+----------------------------------------+
|i1 : A = matrix{{4,3,2,1,0},{0,1,2,3,4}}|
|                                        |
|o1 = | 4 3 2 1 0 |                      |
|     | 0 1 2 3 4 |                      |
|                                        |
|              2       5                 |
|o1 : Matrix ZZ  <-- ZZ                  |
+----------------------------------------+
|i2 : B = matrix{{1,1,1,1,1}}            |
|                                        |
|o2 = | 1 1 1 1 1 |                      |
|                                        |
|              1       5                 |
|o2 : Matrix ZZ  <-- ZZ                  |
+----------------------------------------+
|i3 : toricJoinDim(A,B)                  |
|                                        |
|o3 = 3                                  |
+----------------------------------------+
|i4 : toricJoinDim(B,B)                  |
|                                        |
|o4 = 1                                  |
+----------------------------------------+

Caveat
======

All input matrices must have the same number of columns.

See also
========

  * toricSecantDim -- dimension of a secant of a toric
    variety
  * joinIdeal -- compute the join of several ideals

Ways to use toricJoinDim:
=========================

  * "toricJoinDim(List)"
  * "toricJoinDim(Matrix,Matrix)"

For the programmer
==================

The object toricJoinDim, is a method function (Macaulay2Doc).

toricSecantDim -- dimension of a secant of a toric variety
**********************************************************

Synopsis
========

  * Usage:
        toricSecantDim(A,k)
  * Inputs:
      * A, a matrix (Macaulay2Doc), the A-matrix of a toric
        variety
      * k, an integer (Macaulay2Doc), order of the secant
  * Outputs:
      * an integer (Macaulay2Doc), the dimension of the kth secant of
        variety defined by matrix A

Description
===========

A randomized algorithm for computing the affine dimension of a secant of a
toric variety using Terracini's Lemma.

Here the kth secant means the join of k copies of I. Setting k to 1 gives the
dimension of the ideal, while 2 is the usual secant, and higher values
correspond to higher order secants.

The matrix A defines a parameterization of the variety.  The algorithm chooses
k vectors of parameter values at random from a large finite field.  The
dimension of the sum of the tangent spaces at those points is computed.

This algorithm is much much faster than computing the secant variety.

+----------------------------------------+
|i1 : A = matrix{{4,3,2,1,0},{0,1,2,3,4}}|
|                                        |
|o1 = | 4 3 2 1 0 |                      |
|     | 0 1 2 3 4 |                      |
|                                        |
|              2       5                 |
|o1 : Matrix ZZ  <-- ZZ                  |
+----------------------------------------+
|i2 : toricSecantDim(A,1)                |
|                                        |
|o2 = 2                                  |
+----------------------------------------+
|i3 : toricSecantDim(A,2)                |
|                                        |
|o3 = 4                                  |
+----------------------------------------+
|i4 : toricSecantDim(A,3)                |
|                                        |
|o4 = 5                                  |
+----------------------------------------+
|i5 : toricSecantDim(A,4)                |
|                                        |
|o5 = 5                                  |
+----------------------------------------+

See also
========

  * toricJoinDim -- dimension of a join of toric varieties
  * secant -- compute the secant of an ideal

Ways to use toricSecantDim:
===========================

  * "toricSecantDim(Matrix,ZZ)"

For the programmer
==================

The object toricSecantDim, is a method function (Macaulay2Doc).

unlabeledTrees -- enumerate all unlabeled trees
***********************************************

Synopsis
========

  * Usage:
        unlabeledTrees n
  * Inputs:
      * n, an integer (Macaulay2Doc), the number of leaves
  * Outputs:
      * a list (Macaulay2Doc), of all binary unlabeled trees with n
        leaves

Description
===========

This function enumerates all possible binary trees with n unlabeled leaves.
Each tree is an object of class LeafTree. Each class of
unlabeled tree is represented by a particular labeling of that tree. Some
duplicates may appear in the list, but each equivalence class is guaranteed to
appear at least once.

+-----------------------------------------------------------------------------+
|i1 : L = unlabeledTrees 5                                                    |
|                                                                             |
|o1 = {{{0, 1, 2, 3, 4}, {set {1, 2, 3}, set {1, 2}, set {0}, set {1}, set    |
|     ------------------------------------------------------------------------|
|     {2}, set {3}, set {4}}}, {{0, 1, 2, 3, 4}, {set {1, 2, 3}, set {0}, set |
|     ------------------------------------------------------------------------|
|     {1}, set {2}, set {3}, set {4}}}, {{0, 1, 2, 3, 4}, {set {0}, set {1},  |
|     ------------------------------------------------------------------------|
|     set {2}, set {3}, set {4}}}}                                            |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+

Caveat
======

For n larger than 5, some equivalence classes of trees may appear more than
once.

See also
========

  * labeledTrees -- enumerate all labeled trees
  * labeledBinaryTrees -- enumerate all binary
    labeled trees
  * rootedTrees -- enumerate all rooted trees
  * rootedBinaryTrees -- enumerate all rooted binary
    trees

Ways to use unlabeledTrees:
===========================

  * "unlabeledTrees(ZZ)"

For the programmer
==================

The object unlabeledTrees, is a method function (Macaulay2Doc).

vertexCut -- break up a tree at a vertex
****************************************

Synopsis
========

  * Usage:
        vertexCut(T,e,l,newl)
        vertexCut(T,E,l,newl)
  * Inputs:
      * T, an instance of the type LeafTree,
      * e, a set (Macaulay2Doc), an edge specified by the set of
        leaves on one side of it
      * E, a list (Macaulay2Doc), an edge specified by a list of
        the leaves on one side of it
      * l, a thing (Macaulay2Doc), a leaf of the tree
      * newl, a thing (Macaulay2Doc), the label for a new leaf
  * Outputs:
      * a list (Macaulay2Doc), of LeafTree,s that
        are subtrees of T

Description
===========

Vertices of a tree of class LeafTree, do not have explicit
names.  Therefore a vertex v is specified by naming an edge e incident to v,
and leaf l on the opposite side of the edge as v.

The function outputs the subtrees of T obtained by deleting the vertex v from T
and then re-adding v to each of the resulting subtrees as a new leaf. The new
leaf on each subtree is adjacent to the edge previously adjacent to v on T.
Each subtree has a copy of the vertex labeled newl, but their edge sets form a
partition of the edge set of T.

Each subtree in P has one leaf that was not a leaf of T, and therefore
previously unlabeled. The label for this new leaf is input as newl.

+---------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}})                                         |
|                                                                     |
|o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}}|
|                                                                     |
|o1 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i2 : P = vertexCut(T, set {0,1}, 0, 4);                              |
+---------------------------------------------------------------------+
|i3 : P#0                                                             |
|                                                                     |
|o3 = {{3, 4}, {set {3}}}                                             |
|                                                                     |
|o3 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i4 : P#1                                                             |
|                                                                     |
|o4 = {{2, 4}, {set {2}}}                                             |
|                                                                     |
|o4 : LeafTree                                                        |
+---------------------------------------------------------------------+
|i5 : P#2                                                             |
|                                                                     |
|o5 = {{0, 1, 4}, {set {0}, set {1}, set {4}}}                        |
|                                                                     |
|o5 : LeafTree                                                        |
+---------------------------------------------------------------------+

See also
========

  * edgeCut -- break up a tree at an edge

Ways to use vertexCut:
======================

  * "vertexCut(LeafTree,List,Thing,Thing)"
  * "vertexCut(LeafTree,Set,Thing,Thing)"

For the programmer
==================

The object vertexCut, is a method function (Macaulay2Doc).

vertices(LeafTree) -- list the vertices of a tree
*************************************************

Synopsis
========

  * Function: vertices (Polyhedra),
  * Usage:
        vertices T
  * Inputs:
      * T, an instance of the type LeafTree,
  * Outputs:
      * a list (Macaulay2Doc), the vertices of T

Description
===========

This function lists all vertices of a tree.  Each vertex is specified by the
partition of the set of leaves formed by removing the vertex.  Each partition
is given as a list of sets.

+-----------------------------------------------------------------------------+
|i1 : T = leafTree(4,{{0,1}});                                                |
+-----------------------------------------------------------------------------+
|i2 : vertices T                                                              |
|                                                                             |
|o2 = {set {set {3}, set {2}, set {0, 1}}, set {set {0, 1, 2}}, set {set {0,  |
|     ------------------------------------------------------------------------|
|     1, 3}}, set {set {1}, set {2, 3}, set {0}}, set {set {0, 2, 3}}, set    |
|     ------------------------------------------------------------------------|
|     {set {1, 2, 3}}}                                                        |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : #(vertices T)                                                           |
|                                                                             |
|o3 = 6                                                                       |
+-----------------------------------------------------------------------------+

Caveat
======

The leaves of T in the output of vertices have a different representation from
the one in the output of leaves(LeafTree).

See also
========

  * internalVertices -- list the internal vertices of
    a tree
  * leaves(LeafTree) -- list the leaves of a tree

Ways to use this method:
========================

  * vertices(LeafTree) -- list the vertices of a
    tree