Flip Graphs of Convex Polygons
Flip Graphs, are obtained by considering triangulations on a fixed set of points as vertices, and connecting two vertices, if it is possible to get from one triangulation to the other by flipping a single edge.
Structures
The main structure for this part of the package is the FlipGraphPlanar
structure. This implements the AbstractGraph
interface from Graphs.jl. It is therefore possible to use it with other packages that work with Graphs.jl.
FlipGraphs.FlipGraphPlanar
— Typestruct FlipGraphPlanar <: AbstractGraph{Int32}
A Graph representing the flip graph of a convex polygon.
Vertices are different triangulations of the same convex polygon. Two vertices are linked by an edge, if the respective graphs differ only by a single flip.
Constructors
To construct the flip graph of a convex polygon, you can either start from a TriangulatedPolygon
or just set the number of vertices of the triangulated convex polygon.
FlipGraphs.flipgraph
— Methodflipgraph(g::TriangulatedPolygon; kwargs..)
Construct the FlipGraph
for the TriangulatedPolygon
g
.
Arguments
- 'modular::Bool = false' : by default, the whole flip graph is constructed. If
modular
is set totrue
, then only the modular flip graph is constructed.
In a modular flip graph, vertices of the flip graph are classes of isomorphisms up to renaming the vertices. Each class is then represented by one of its elements.
FlipGraphs.flipgraph_planar
— Functionflipgraph_planar(n::Integer; modular=false) :: FlipGraphPlanar
Construct the FlipGraphPlanar
of a convex n
-gon.
If modular=true
, the flip graph is reduced to its modular form.
Examples
julia> flipgraph_planar(6)
FlipGraphPlanar with 14 vertices and 21 edges
Graph methods
The following methods overload some of the main functions from the Graphs.jl package.
Graphs.nv
— Methodnv(G::FlipGraphPlanar)
Return the number of vertices in G
.
Graphs.ne
— Methodne(G::FlipGraphPlanar)
Return the number of edges in G
.
Graphs.vertices
— Methodvertices(G::FlipGraphPlanar)
Return the List of all vertices in G
.
Graphs.edges
— Methodedges(G::FlipGraphPlanar) ::Vector{Edge}
Construct an array containing all the edges in G
.
Graphs.has_vertex
— Methodhas_vertex(G::FlipGraphPlanar, g::TriangulatedPolygon) :: Bool
Return true
if g
is a vertex in G
.
If G
is a modular flip graph, this will only return true
if g
is the proper representant of the vertex.
Graphs.has_vertex
— Methodhas_vertex(G::FlipGraphPlanar, i::Integer) :: Bool
Return true
if i
is a valid index of a vertex in G
.
FlipGraphs.get_vertex
— Methodget_vertex(G::FlipGraphPlanar, i::Integer) :: TriangulatedPolygon
Return the i
-th vertex in the planar flip graph G
.
Graphs.has_edge
— Methodhas_edge(G::FlipGraphPlanar, s, d)
Return true
if there is an edge between s
and d
in G
.
Graphs.has_edge
— Methodhas_edge(G::FlipGraphPlanar, e::Edge)
Return true
if e
is an edge in G
.
FlipGraphs.degree
— Methoddegree(G::FlipGraphPlanar, v::Integer)
Return the degree of the v
-th vertex in the graph G
.
Graphs.neighbors
— Methodneighbors(G::FlipGraphPlanar, v::Integer) :: Vector{Int32}
Return a list of all the indices of vertices in G
, that are adjacent to v
.
FlipGraphs.diameter
— Methoddiameter(G::FlipGraphPlanar)
Compute the diameter of G
.
Comparing Triangulations
To compute the flip graph, one needs to be able to determine if two triangulations are identical (if the points are labeled) or isomorphic to each other (if the points are unlabeled).
The first case is fairly simple, as two triangulations are identical if their adjacency lists are. The only difficulty here is that the order in the list of neighbors is not fixed.
The second case is more challenging, as there are $n!$ different ways to label $n$ points. The way it is done in this package is to use a variation of McKay's canonical graph labeling algorithm[1] to rattle the number of possible labelings down to a relatively small number.
FlipGraphs.is_isomorphic
— Methodis_isomorphic(g1::TriangulatedPolygon, g2::TriangulatedPolygon)
Check if g1
and g2
are isomorphic up to a relabeling of the vertices.
FlipGraphs.is_isomorphic
— Methodis_isomorphic(g1::TriangulatedPolygon, g2::TriangulatedPolygon, permutations::Vector{Vector{T}}) where T<:Integer
Check if g2
is isomorphic to g1
up to a relabeling of the vertices by one of the permutations
.
The following methods are used to build the flip graph; However, they can also be useful elsewhere:
FlipGraphs.mcKay
— FunctionmcKay(g::TriangulatedPolygon) :: Vector{Vector{<:Integer}}
Apply McKay's canonical graph labeling algorithm to determine all possible permutations of the vertices, which give a canonical isomorphism class representant.
Return a list of all possible canonical point-relabeling permutations p
such that the i-th point should be relabeled as the p[i]
-th point
FlipGraphs.rename_vertices
— Methodrename_vertices(g::TriangulatedPolygon, p::Vector{<:Integer}) :: TriangulatedPolygon
Return the TriangulatedPolygon
obtained from renaming the vertices of the triangulated convex polygon g
by applying the permutation p
.
FlipGraphs.rename_vertices!
— Methodrename_vertices!(g::TriangulatedPolygon, p::Vector{<:Integer}) :: TriangulatedPolygon
Rename the vertices of the triangulated convex polygon g
by applying the permutation p
.
- 1Hartke, S.G., & Radcliffe, A.J. (2008). McKay ’ s Canonical Graph Labeling Algorithm.