flipGraph -- bistellar-flip graph of a point or vector configuration

Usage:

G = flipGraph T

G = flipGraph A

G = flipGraph(A, tri)
Inputs:
- T, an instance of the type Triangulation,
- A, a matrix, whose columns are the points (or vectors) to triangulate
- tri, a list, a triangulation of the columns of $A$
Optional inputs:
- Limit => an integer, default value infinity, stop after this many triangulations have been visited
- RegularOnly => a Boolean value, default value false, restrict the graph to regular triangulations
- Fine => a Boolean value, default value true, if true (default), restrict to support-preserving flips
- Homogenize => a Boolean value, default value true, used only by the Matrix and (Matrix, List) forms; see triangulation
- Strategy => ..., default value Topcom
Outputs:
- G, a hash table, with keys Triangulations and Edges: G.Triangulations is the list of Triangulation's reached, and G.Edges is a list of triples $(i, j, c)$ with $i < j$, where $i$ and $j$ index into G.Triangulations and $c$ is the affine circuit of the flip between them

Description

Performs a breadth-first search over the bistellar-flip graph starting at $T$ (or at a regular fine triangulation of $A$ if no triangulation is given), recording both the triangulations reached and the edges between them. Each undirected edge is recorded once, when discovered from its lower-indexed endpoint.

This is the edge-aware companion of generateTriangulations, which returns the same triangulations but discards the connectivity.

i1 : A = transpose matrix {{0,3},{0,1},{-1,-1},{1,-1},{-4,-2},{4,-2}}

o1 = | 0 0 -1 1  -4 4  |
     | 3 1 -1 -1 -2 -2 |

              2       6
o1 : Matrix ZZ  <-- ZZ

i2 : T = regularFineTriangulation A

o2 = triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}}

o2 : Triangulation

i3 : G = flipGraph T

o3 = HashTable{Edges => {(0, 1, {{1, 4}, {0, 2}}), (0, 2, {{1, 5}, {0, 3}}), (0, 3, {{3, 4}, {2, 5}}), (1, 4, {{1, 5}, {0, 3}}), (1, 5, {{3, 4}, {2, 5}}), (2, 4, {{1, 4}, {0, 2}}), (2, 6, {{3, 4}, {2, 5}}), (3, 5, {{1, 4}, {0, 2}}), (3, 6, {{1, 5}, {0, 3}}), (4, 7, {{3, 4}, {2, 5}}), (5, 7, {{1, 5}, {0, 3}}), (6, 7, {{1, 4}, {0, 2}})}                                                                                                                                                                                                                                                                                                                                                                                                                                                         }
               Triangulations => {triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}}

o3 : HashTable

i4 : #G.Triangulations

o4 = 8

i5 : #G.Edges

o5 = 12

i6 : first G.Edges

o6 = (0, 1, {{1, 4}, {0, 2}})

o6 : Sequence

Caveat

Like generateTriangulations, this function is implemented in the top-level Macaulay2 language and is much slower than the topcom-based allTriangulations. It does, however, expose the flip-graph structure that allTriangulations discards, and it accepts a Limit for incremental exploration.

Ways to use flipGraph:

flipGraph(Matrix)
flipGraph(Matrix,List)
flipGraph(Triangulation)

For the programmer

The object flipGraph is a method function with options.

The source of this document is in Triangulations.m2:2488:0.

flipGraph -- bistellar-flip graph of a point or vector configuration

Description

Caveat

See also

Ways to use flipGraph:

For the programmer