Thread: advice on a data structure

Hi im doing some research into cell signalling in fly wings, and need to represent such cells in a hexagonal grid

now each hexagon (6 sides) has 6 neighbours, and these neighbours have 6 neighbours and so on...

ive began to design a class on paper to represent a Cell Wall, thus a class Cell will constitute 6 walls (the hexagon)

now comes the difficulty im having, i was trying to link cells into a linear data structure with corresponding pointers to all neighbours, and sofar i have something similar to below on paper:

key : cell = [X]
pointer ->

This seems to be the linear style data structure for 7 cells;

[0] <-> [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [6]

[6] <-> [0]
[5] <-> [0]
[4] <-> [0]
[3] <-> [0]
[2] <-> [0]
[1] <-> [0]

[7] <-> [6]
[7] <-> [1]

(think of a spiral to visualise what i mean)

This is quite overly complex and gets rather messy with 20+ cells, i was wondering if any1 has any ideas of arranging this sort of structure in a more simple way..?

it looks as if ill be dealing with a large number of pointers if i go this way .. which is quite daunting ... the only other way is if i come up with a complex algorithm to determine possible neighbours based upon the cell id number or something


Thanks in advance.

The best way that I can see it is to forgo making a separate class for a cell wall and instead just make it so that each cell object has six neighbor cell objects. Then you'll only have one pointer for each cell, shared amongst each other.

Think Graph data structures. a node in the graph can be connected to any number of nodes. so e.g.

Code:

class cell{
// your private data stuff

public:

class *side1, *sides2, *side3, *siden; //pointers to other cells that neighbour this one

//then create your functions here. 
};

you doing biochemistry or similar field??
Anyway I hope that helps though it may lead to headaches depending on your style of programming.

ok Thanks,

that seems to make sense, yea it may lead to headaches as this wont be the only pointers i need, ill need to keep track of 2 mechanisms, one which feedbacks concentrations of two proteins and the other which feeds them onto the corresponding cell wall

yea im in the computational biology field, doing work on Planar Cellular Polarity Signalling in fruit fly's

I am just taking a stab at the problem. I may be way off base but, if you want to reduce the number of pointers I think you might be able to just create a structure with six members of type int. If you number each cell (1-100 or something) ....... then you could try

Code:

struct Cell
{
    int side1;
    int side2;
    int side3;
    int side4;
    int side5;
    int side6;
};

now you could create an array of structures. IE however many cells you want and make its data members equal to the cell it is adjacent too.

Code:

Cell cells[100];

if side1 of cells[1] was adjacent to cell 40 then make it equal to 40. cells[1].side1=40; To access any adjacent cell just put its side as the index.

Code:

cells[1].side1=40;
 cells[ cells[1].side1  ];  //would give you cell #40

also you will notice that you have certain pairs. if you take the sides going clockwise side1 will always share side4 of that adjacent cell and side2 will always share side5 of that adjacent cell and 3 will always share side 6 of that adjacent cell. Basically just adding 3 to the appropriate side will give you the adjacent cells side for 1/2 of the cell then subtracting 3 will give you the other 1/2 of the cell.

OOhh Computational Biology. Thaat's gotta be a headache. If you want to propagate information between cells then you'll have to write some sort of cascading function that feeds values to the affected neighbouring cells You may want to work on your basic data structure(s) and their function(s) properly before you start coding this baby. I used to do some biochemistry but 's all past me now, but if ye need some help I'll quite happily lend a hand as I'm not entirely oblivious to the field of bio-sciences.

thanks for all the replys, ill consider each approach carefully before i decide on anything major, but i have been discussing this with a colleague and come up with some ideas which ill explain.

ill try to explain the situation in a little more detail for those of you who are interested.

The basic idea of the research is related to the position of the hair on a fruit fly wing which usually points in one direction (the distal corner of the hexagonal cell eg the far right). the two mechanisms mentioned propagate the proteins through the cell to form the concentration of protein at the distal edge to point the hair. sometimes the cell mutates, and causes different properties of the cell hair to change, but we are most concerned with not the local effect of this but the global effect of the direction of hairs, because if one points in the wrong direction then we get a similar effect to iron filings on paper and a magnet and the swirling motions u see, plus other distinct alginments of hairs which are not explained fully yet.

with regard to the model of the cell i have come up with the following outline of the problem.

An object of type CELL can point to its 6 neighbours (or 3 if at an edge).

This is comprised of 6 objects of type WALL.

The WALL object is comprised of 10 COMPONENT objects which constitute the concentrations of different proteins. (note increasing the resolution from 10 to 100 will most likely not increase accuracy - so 10 will suffice plus im keeping it simple to start with).

The equations dealing with the signalling will be dealt with within the WALL objects, and equations for the feedback in the CELL object. The COMPONENT objects contain the concentrations of proteins and various other things, like Inhibitor proteins to affect signalling.

The CELL's can be stored either as a 2D array of Cells or another data structure.

At the moment im trying to figure a simplistic method of doing this in a 2d array, so far this is on paper but ill try to explain the structure. We have a cell (n,m)

Code:

         n,m+1
 n-1 \_____/
 m-1/          \  n+1,m
  __/            \__
      \   n,m    /
 n-1 \          /  n+1,m-1
  m   /--------\
       /  n,m-1 \

From this we can see a simple method of a 2d array, ill have a look at this later and see if i can code up the basic classes.

If you get the data structure right let me know. I started something of my own a few months earlier but had to put it on hold trying to perfect the data structure. Basically I was trying to write a graph to contain information about the whole london underground.
I had a class and a structure which was to contain an interger to denote the weight of a pointer to a connected node in the graph and a template type pointer which. I ran into complications trying to implement this using the STL.
As for storing the cells as a two dimensional array of cells; I'd recommend you go for graph type implementation; this simplifies your visualisation of everything as opposed to trying to fit a hexa-structure into a quad one.
regarding the structure you have so far, you should consider defining a wall as a structure with a pointer to a cell.
But it seems pretty stable I don't know much about this fruit fly cell you're trying to mimick but I guess I could read up about it. Just to enlighten me.