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 twodimensional
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. 3 2944
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);
}
"i" <ty****@gmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com... 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 twodimensional 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.
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
"i" <ty****@gmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com... 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 twodimensional 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.
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);
}
"Fred Mellender" <no****************@frontiernet.net> wrote in message
news:Ky***************@news02.roc.ny... 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); }
"i" <ty****@gmail.com> wrote in message news:11**********************@z14g2000cwz.googlegr oups.com... 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 twodimensional 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.
This discussion thread is closed Replies have been disabled for this discussion. Similar topics
25 posts
views
Thread by Magnus Lie Hetland 
last post: by

6 posts
views
Thread by Ramon M. Felciano 
last post: by

2 posts
views
Thread by KevinGPO 
last post: by

3 posts
views
Thread by chellappa 
last post: by

1 post
views
Thread by wayne 
last post: by

3 posts
views
Thread by Amol 
last post: by

7 posts
views
Thread by diffuser78 
last post: by
 
5 posts
views
Thread by chrispoliquin 
last post: by
          