(* Copyright (c) 1992 The Geometry Center; University of Minnesota
   1300 South Second Street;  Minneapolis, MN  55454, USA;
   
This file is part of CirclePack. CirclePack is free software; you can
redistribute it and/or modify it only under the terms given in the
file COPYING, which you should have received along with this file.
This and other software may be obtained via anonymous ftp from
geom.umn.edu; email: software@geom.umn.edu. *)

(* Author: Oliver Goodman *)
(* $Id: Triangulation.m,v 1.3 1992/07/17 16:09:52 oag Exp $ *)

(* Mathematica package for working with triangulations. Contains a 
   function for creating triangulation objects and several functions
   which return information about a triangulation. For efficiency 
   reasons the information is computed only once then stored inside
   the triangulation object. No checking is done that the triangulation
   constructed is legal. (Eg does not have 3 faces bordering a single 
   edge.) 
*)

BeginPackage["Triangulation`"]

Triangulation::usage = "Triangulation[faces, glue] returns a
Triangulation object. Specify faces as a list of triples of integers
and glue as a list of pairs of edges to be identified (where an edge
is a pair of integers). The following functions are defined for a
triangulation object: faces, glue, vertices, edges, corners,
allvertices, alledges, nv, ne, nc, euler, vN, eN."

faces::usage = "faces[triangulation] returns a list containing each
face of the triangulation as a triple of integers."

glue::usage = "glue[triangulation] returns a list of pairs of edges 
which are identified in the triangulation."

vertices::usage = "vertices[triangulation] returns a list of integers
representing the vertices of the triangulation. In cases where 
several integers represent the same vertex only one representitive 
will be returned."

edges::usage = "edges[triangulation] returns a list of pairs of 
integers representing the edges of the triangulation. In cases where 
several possible pairs of integers represent the same edge only one 
pair will be returned."

corners::usage = "corners[triangulation] returns a list of triples 
of integers, each of which represents one corner of a face of the 
triangulation." 

allvertices::usage = "allvertices[triangulation] returns all representitives
of all vertices of the triangulation. See also vertices[]."

alledges::usage = "alledges[triangulation] returns a list of pairs of 
integers representing the edges of the triangulation. In cases where 
edges have been identified both representitives will be returned. See 
also edges[]."

nv::usage = "nv[triangulation] returns the number of vertices in the 
triangulation after any identifications have been performed."

ne::usage = "ne[triangulation] returns the number of edges in the 
triangulation after any identifications have been performed."

nc::usage = "nc[triangulation] returns the number of corners in the
triangulation (as returned by the corners[] function)."

euler::usage = "euler[triangulation] returns the Euler characteristic 
of the triangulation."

vN::usage = "vN[triangulation, v] returns the position of the vertex 
represented by v in the list vertices[triangulation]."

eN::usage = "eN[triangulation, e] returns the position of the edge
represented by e in the list edges[triangulation]."

Begin["`Private`"]

faces[t_Triangulation]:= t[[1]]
glue[t_Triangulation]:= t[[2]]
vertices[t_Triangulation]:= t[[3]]
edges[t_Triangulation]:= t[[4]]
corners[t_Triangulation]:= t[[5]]
allvertices[t_Triangulation]:= t[[6]]
alledges[t_Triangulation]:= t[[7]]
nv[t_Triangulation]:= t[[8]]
ne[t_Triangulation]:= t[[9]]
nc[t_Triangulation]:= t[[10]]
euler[t_Triangulation]:= t[[11]]
vN[t_Triangulation, v_]:= Position[vertices[t], t[[12]][v]][[1,1]];
eN[t_Triangulation, e_]:= Position[edges[t], t[[13]][Sort[e]]][[1,1]];

(* unionFind finds a function which maps each vertex of a graph to 
   a representitive vertex in the same connected component. The graph
   is given as a list of edges where each edge is a pair of vertices. 
   The representitive function r[x] gives the least y (in the canonical
   ordering of vertices) in the connected component of x. 
*)
unionFind[es_]:=Module[{r,p,x,j},
   p[_]=x;
   r[v_]:= If[p[v]===x, v, p[v]=r[p[v]]];
   j[{a_,b_}]:= Block[{u=r[a],v=r[b]}, If[u=!=v, p[v]=u]];
   Scan[j, Sort /@ es];
   r[v_]:= r[v] = If[p[v]===x, v, p[v]=r[p[v]]];
   r
]

Format[_Triangulation] = "Triangulation"

Triangulation[faces_,glue_]:= Module[{vr, er},
Block[{vertices, edges, corners, allvertices, alledges, nv, ne, nc, euler}, 
   allvertices = Union @@ faces;
   alledges = Union @@ ((Sort /@ faces) /. 
      {a_,b_,c_} :> {{a,b},{b,c},{a,c}});
   (* define representitive functions for vertices and edges *)
   vr = unionFind[Flatten[Transpose /@ glue,1]];
   er = unionFind[Map[Sort,glue,{2}]];
   (* list and count up vertices, edges and corners *)
   nv = Length[vertices = Union[vr /@ Flatten[faces,1]]];
   ne = Length[edges = Union[er /@ alledges]];
   nc = Length[corners = Flatten[faces /. 
      {a_,b_,c_} :> {{a,b,c},{b,c,a},{c,a,b}}, 1]];
   euler = Length[faces] - ne + nv;
   (* define numbering functions for the vertices and edges *)
   Triangulation[faces, glue, vertices, edges, corners, allvertices, alledges,
      nv, ne, nc, euler, vr, er]
]]

End[]
EndPackage[]
