*****  To join INSNA, visit http://www.insna.org  *****

It is also important to distinguish, whether, without loss of generality,
i is even or odd, i.e., whether connections go

|/
*-
|\

or

|\
*-
|/


The triangular grid has this structure (best viewed with
a fixed-width font):


  *-*-*-*-*-*-*-*-*-*-*  1
  |\|\|\|\|\|\|\|\|\|\|
  *-*-*-*-*-*-*-*-*-*-*
  |/|/|/|/|/|/|/|/|/|/|
  *-*-*-*-*-*-*-*-*-*-* 
  |\|\|\|\|\|\|\|\|\|\|
  *-*-*-*-*-*-*-*-*-*-*
  |/|/|/|/|/|/|/|/|/|/|
  *-*-*-*-*-*-*-*-*-*-*  n
  1                   m

The nice equilateral triangles are obtained by shifting every other
line slightly to the left.

If you want to generate a list representation of all the edges, it is
probably most convenient to index the nodes with their position in the
grid, ranging from [1,1] to [n,m].

Computationally, this grid is generated by something like

  for i=1..n-1 do
    for j=1..m-1 do
      connect [i,j] and [i+1,j]       // edge to the lower neighbor
      connect [i,j] and [i,j+1]       // edge to the right neighbor
    if i is odd then
      for j=1..m-1 do
        connect [i,j] and [i+1,j+1]   // edge to lower right neighbor
    else
      for j=2..m do
        connect [i,j] and [i+1,j-1]   // edge to lower left neighbor
  for i=1..n-1 do
    connect [i,m] and [i+1,m]         // complete right grid border
  for j=1..m-1 do
    connect [n,j] and [n,j+1]         // complete lower grid border


One-dimensional node indices, and thus an enumeration, are obtained by
evaulating  (i-1)*m + j  for every node [i,j].

More generally, you may think of a triangular grid in which,
additionally, the bottom layer is connected to the top layer and the
rightmost layer to the leftmost layer, related to what is often called
torus.  Then the structure may be described by a Cayley graph generated
by a discrete group, and the resulting adjacency matrix has a much more
convenient structure.

Christian



Mark Newman wrote:
> *****  To join INSNA, visit http://www.insna.org  *****
>
> The simplest representation uses a square grid, with additional diagonal
> edges one way across each square.  Thus for instance you could use a
> two-dimensional array in which element (i,j) is a neighbor of:
>
>   (i+1,j)
>   (i-1,j)
>   (i,j+1)
>   (i,j-1)
>   (i+1,j+1)
>   (i-1,j-1)
>
> This gives the topology of a triangular lattice.
>
> If you prefer to use a one-dimensional array, there is also a simple
> one-dimensional representation using helical boundary conditions.
>
> Mark
>
>
>
> On 11/05/2009 11:19 AM, Moses Boudourides wrote:
>>
>> Say we have a triangular grid (tiling) formed by nxm vertices (i.e., a
>> graph in which all internal vertices have degree 6). What I want to
>> obtain is the structure of the matrix (or list) representation of its
>> edges. Of course, this depends on the enumeration of vertices. Thus,
>> the question is what re-ordering gives the simplest general form of
>> such a matrix (or list) and what is exactly this form?
>

_____________________________________________________________________
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.