## SOCNET@LISTS.UFL.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Monospaced Font

Subject:

Re: A computational problem with triangular grids

From:

Date:

Thu, 5 Nov 2009 18:27:02 +0100

Content-Type:

text/plain

Parts/Attachments:

 text/plain (108 lines)
 ***** 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.