Plotting a graph using an array of relatively linked nodes

[i]

Hi,

I'm working with an array of nodes, numbering roughly in the thousands.
Each node has at least one, but up to four, references to another node
- North, South, East, or West. I'm trying to get my program to take
these nodes and plot them on a graph, represented by a two-dimensional
array.

Right now I'm having some trouble with the recursive method I've set
up, which does not seem to be efficient enough to get the job done. I
keep getting a StackOverflowException, and I'm wondering if there's a
better way to graph.

Right now every node the method encounters is plotted, and then the
method calls itself for every other node the original was linked to:

public static void buildGraph(Node rm, string dirFrom, int X, int Y)
{
graph[Y, X] = 1; // '1' indicates a plotted node on the
graph

switch (dirFrom)
{
case "n":
if (rm.s != 0) // if a direction is 0, that
means no node exists
buildGraph(southOf(rm), "n", X, Y++);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
case "s":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
case "e":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.s != 0)
buildGraph(southOf(rm), "n", X, Y++);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
case "w":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.s != 0)
buildGraph(southOf(rm), "n", X, Y++);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
break;
case "startpoint":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.s != 0)
buildGraph(southOf(rm), "n", X, Y++);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
}
}

Maybe I'm completely missing the concept. What's the correct way to do
this?

Thanks.

 

[Fred Mellender]

The solution is to use your own stack. Something like (syntax not checked):
Class MyNode
{
MyNode east;
MyNode west;
MyNode south;
MyNode north;
}

Stack <MyNode> stack = new Stack<MyNode>(10);

stack.Push(rootNode); //first node, whose east node is to be plotted...

while (stack.Count > 0)
{
MyNode node = stack.Pop();
node.Plot(node.east); //plot a single number

node.Push(node.west); //check to these are not null, before you
Push!
node.Push(node.north);
node.Push(node.south);
}

 

[Marc Gravell]

Given that you are getting a stack overflow, could this simply be that you
are going around in circles? Even the trival example of node "A" with "B" to
the east, and "B" with "A" to the west will (if incorrectly coded) loop
indefinitely. Are you discounting nodes that have already been plotted once?

Using your existing code, you could possibly (not tested) do this by simply
checking before you plot:

if(graph[Y,X] == 0) { // not already plotted, so plot it
graph[Y,X] = 1; // '1' indicates a plotted node on the graph
// ... the rest of your code
}

I'm assuming "0" means "not plotted" (would a boolean be better?)

Marc

 

[Marc Gravell]

Agree that this is a vast improvement on iteration (for large arrays); note
that you'd still need to avoid going in circles, and that since each node
does not know its own location, it would be necessary to include this in the
pushed object i.e.

// represents a node (in a known location) on the stack
public class QueueItem {
public readonly int X, Y; // quick'n'dirty for demo
public readonly MyNode Node;
public QueueItem(MyNode node, int x, int y) {
Node = node;
X = x;
Y = y;
}
}

and then:

Stack <QueueItem> stack = new Stack<QueueItem>(10);

stack.Push(new QueueItem(rootNode, 0, 0)); //first node, whose east node is
to be plotted...

while (stack.Count > 0)
{
QueueItem item = stack.Pop();
MyNode node = item.Node;
int x = item.X, y = item.Y;
if(!graph[y,x]) { // note: treating as a bool
graph[y,x] = true;
if(node.east!=null) stack.Push(new QueueItem(node.east, x+1,y));
if(node.east!=null) stack.Push(new QueueItem(node.east, x+1,y));
if(node.east!=null) stack.Push(new QueueItem(node.east, x+1,y));
}
node.Plot(node.east); //plot a single number

node.Push(node.west); //check to these are not null, before you
Push!
node.Push(node.north);
node.Push(node.south);
}

The solution is to use your own stack. Something like (syntax not
checked):
Class MyNode
{
MyNode east;
MyNode west;
MyNode south;
MyNode north;
}

Stack <MyNode> stack = new Stack<MyNode>(10);

stack.Push(rootNode); //first node, whose east node is to be plotted...

while (stack.Count > 0)
{
MyNode node = stack.Pop();
node.Plot(node.east); //plot a single number

node.Push(node.west); //check to these are not null, before you
Push!
node.Push(node.north);
node.Push(node.south);
}

Hi,

I'm working with an array of nodes, numbering roughly in the thousands.
Each node has at least one, but up to four, references to another node
- North, South, East, or West. I'm trying to get my program to take
these nodes and plot them on a graph, represented by a two-dimensional
array.

Right now I'm having some trouble with the recursive method I've set
up, which does not seem to be efficient enough to get the job done. I
keep getting a StackOverflowException, and I'm wondering if there's a
better way to graph.

Right now every node the method encounters is plotted, and then the
method calls itself for every other node the original was linked to:

public static void buildGraph(Node rm, string dirFrom, int X, int Y)
{
graph[Y, X] = 1; // '1' indicates a plotted node on the
graph

switch (dirFrom)
{
case "n":
if (rm.s != 0) // if a direction is 0, that
means no node exists
buildGraph(southOf(rm), "n", X, Y++);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
case "s":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
case "e":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.s != 0)
buildGraph(southOf(rm), "n", X, Y++);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
case "w":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.s != 0)
buildGraph(southOf(rm), "n", X, Y++);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
break;
case "startpoint":
if (rm.n != 0)
buildGraph(northOf(rm), "s", X, Y--);
if (rm.s != 0)
buildGraph(southOf(rm), "n", X, Y++);
if (rm.e != 0)
buildGraph(eastOf(rm), "w", X--, Y);
if (rm.w != 0)
buildGraph(westOf(rm), "e", X++, Y);
break;
}
}

Maybe I'm completely missing the concept. What's the correct way to do
this?

Thanks.