Graph - node - transpose

[VisionSet]

I have a graph of cells that build a simple 2D grid.
Each node is associated with its north, south, east, west neighbour.
In the problem I have, I need to traverse the nodes in either north/south or
east/west directions.
But I realsise I can split my problem in half by just going along one axis
and then doing a transpose for the other.
What is the best way of implementing the transpose? At present I have all
my nodes collected in a Node[][].
Do I really want to travserse the array and call transpose on every node,
since I do this regularly?
I naturally don't want to optimise prematurely, but is there a better
approach?

TIA
Mike W.

 

[Chris Uppal]

What is the best way of implementing the transpose? At present I have all
my nodes collected in a Node[][].
Do I really want to travserse the array and call transpose on every node,
since I do this regularly?

If iterating:

int col = 4;
for (int row = 0; row < rowMax; row++)
Node node = nodes[col][row];

vs:

int row = 4;
for (int col = 0; col < colMax; col++)
Node node = nodes[col][row];

doesn't suit your tastes, or is too slow, then why not build two arrays (of
arrays of) Nodes, one ordered in column-major order, the other in row-major
order ? You would then be able to iterate over either rows of columns
directly.

-- chris

 

[VisionSet]

If iterating: ....
doesn't suit your tastes, or is too slow, then why not build two arrays (of
arrays of) Nodes, one ordered in column-major order, the other in row-major
order ? You would then be able to iterate over either rows of columns
directly.

No, it is the nodes themselves that need transposing ie the nodes nodes.
transposing by +/- 90degs so that eg East and South nodes flip. The node
itself does not move.
ie the grids squares are fixed translationally but they can rotate +/-
90degs.

I think calling transpose on all nodes is not bad since I think I only need
to do it once per cpu intensive spell.

 

[iamfractal]

VisionSet skrev:

No, it is the nodes themselves that need transposing ie the nodes nodes.
transposing by +/- 90degs so that eg East and South nodes flip. The node
itself does not move.

Mike W

How about not transposing the nodes but instead having them aware of
the graph's orientation, and returning the neighbour node based on
that orientation?

For example,

class Node {
Node northNeighbour = null;
Node southNeighbour = null;
Node eastNeighbour = null;
Node westNeighbour = null;

Node(Node northNeighbour, Node southNeighbour,
Node eastNeighbour, Node westNeighbour) {
this.northNeighbour = northNeighbour;
this.southNeighbour = southNeighbour;
this.eastNeighbour = eastNeighbour;
this.westNeighbour = westNeighbour;
}

Node getNorthNeighbour() {
switch (graph.getOrientation()) {
case Graph.NORTH_SOUTH_DIRECTION:
return northNeighbour;
case Graph.EAST_WEST_ORIENTATION:
return eastNeighbour;
etc ....
}
}
}


Not particularly elegant, admittedly. If your scan always goes in one
direction, you could consider a row-based, orientation-aware Iterator
and have next() do the checking, a-la:
Iterator iterator = graph.getIterator(startNode);

..ed

 

[VisionSet]

...

direction, you could consider a row-based, orientation-aware Iterator
and have next() do the checking, a-la:
Iterator iterator = graph.getIterator(startNode);

.ed

Thanks, good thoughts!

Mike W