toroidalGrid Class Reference
[Graph series]

Place a regular grid on the surface of a torus. More...

#include <sparseGraph.h>

Inheritance diagram for toroidalGrid:

sparseGraph abstractGraph abstractMixedGraph managedObject goblinRootObject

Public Types

enum  TOptTorus {
  TORUS_TRIANGULAR = 1,
  TORUS_QUADRILATERAL = 2,
  TORUS_HEXAGONAL = 3
}

Public Member Functions

 toroidalGrid (unsigned short hSkew, unsigned short vSize, short vSkew, unsigned short hSize, TOptTorus facets, goblinController &_CT=goblinDefaultContext) throw (ERRejected)

Detailed Description

Place a regular grid on the surface of a torus.

Member Enumeration Documentation

enum TOptTorus
 

Toroidal grid type.

Enumerator:
TORUS_TRIANGULAR  Grid is formed of triangular regions.
TORUS_QUADRILATERAL  Grid is formed of quadrilateral regions.
TORUS_HEXAGONAL  Grid is formed of hexagonal regions.

Constructor & Destructor Documentation

toroidalGrid (  unsigned short  hSkew,
unsigned short  vSize,
short  vSkew,
unsigned short  hSize,
TOptTorus  facets,
goblinController &  _CT = goblinDefaultContext
)  throw (ERRejected)
 

Place a regular grid on the surface of a torus.

Parameters:
hSkew The slope of the first orbit
vSize A grid height such that hSkew <= vSize
vSkew The slope inverse of the second orbit
hSize A grid width
facets The type of facets
_CT The controller object to manage the created graph
This generates a node- and face-regular graph, and a quadrilateral torus map embedding. The horizontal [vertical] boundary is divided into hSize [vSize] portions. Two non-parallel straight lines (called the orbits) are placed, spanning a quadrilateral grid. Both orbits start at the upper left vertex, called the origin. The horizontal orbit meets the right-hand boundary at the vSize/hSkew fraction. Provided that vSkew > 0, the vertical orbit meets the bottom boundary at the hSize/vSkew fraction.

It is legal that vSkew < 0, in which case the origin might be considered upper right vertex. It is also legal that hSkew and / or vSkew are zero, telling that the horizontal [vertical] orbit is indeed a horizontal [vertical] line. It is even legal to let vSkew > hSize, but only as long as vSize*hSize - vSkew*hSkew is a positive number. And this turns out to be the number of graph nodes in the triangular and the quadrilateral case. This implies that both orbits are non-parallel.

If hSkew and vSize [vSkew and hSize] are not relatively prime - especially if hSkew [vSkew] is zero - gcd(hSkew,vSize) [gcd(vSkew,hSize)] parallels of the horizontal [vertical] orbit are added to complete the grid.

The graph nodes are just the cut points of the constructed straight lines, enumerated by the first orbit (and its parallels). The graph edges are the minimal orbit segments.

At this point, the construction in the TORUS_QUADRILATERAL case is complete. All nodes and all regions have degree 4, and the graphs are self-dual. If hSkew and hSize [vSkew and vSize] have the same residue modulo 2, the resulting graph is bipartite.

If TORUS_TRIANGULAR is specified, a third non-parallel orbit is added, splitting each of the regions so far into two triangles. All nodes now have degree 6.

If TORUS_HEXAGONAL is specified, there are some more restrictions on the numeric parameters: hSkew and hSize [vSkew and vSize] must have the same residue modulo 3. If not, hSkew and / or vSkew rounded up to meet this requirement. First, the triagonal grid is generated. Then, from the first generating line, every third node is eliminated. After that operation, all nodes have degree 3, and all regions are hexagons.

The constructor yields regular tessilations for several series of non-planar graphs (e.g. Moebius lattices, taking hSkew = 1,vSize = 2,vSkew = -1,facets = TORUS_QUADRILATERAL), but also for specific graph instances:

  • The tetrahedron (The complete graph on 4 nodes): hSkew = 0,vSize = 2,vSkew = -1,hSize = 3,facets = TORUS_HEXAGONAL
  • K_5 (The complete graph on 4 nodes): hSkew = 1,vSize = 2,vSkew = -1,hSize = 2,facets = TORUS_QUADRILATERAL
  • K_7 (The complete graph on 4 nodes): hSkew = 1,vSize = 3,vSkew = -1,hSize = 2,facets = TORUS_TRIANGULAR
  • K_3_3 (The complete bigraph with 3 nodes on each side): hSkew = 0,vSize = 3,vSkew = 0,hSize = 3,facets = TORUS_HEXAGONAL
  • K_4_4 (The complete bigraph with 4 nodes on each side): hSkew = 1,vSize = 3,vSkew = 1,hSize = 3,facets = TORUS_QUADRILATERAL
  • Heawood graph (The dual graph of K_7): hSkew = 1,vSize = 5,vSkew = -1,hSize = 4,facets = TORUS_HEXAGONAL
  • Moebius-Cantor graph (G(8,3) generalized Petersen graph): hSkew = 4,vSize = 5,vSkew = -1,hSize = 4,facets = TORUS_HEXAGONAL
  • Moebius-Cantor graph dual: hSkew = 0,vSize = 2,vSkew = 1,hSize = 4,facets = TORUS_TRIANGULAR
  • Shrikhande graph: hSkew = 0,vSize = 4,vSkew = 0,hSize = 4,facets = TORUS_TRIANGULAR

On the other hand, there are no representations of K_6 (nodes have degree 5) and the Petersen graph (would be hexagonal but non-bipartite).

Triangular and hexagonal torus grids are dual to each other. In terms of its construction, the dual graph of an hexagonal torus grid has consists of the nodes which have been ommitted from the original triangular grid.