471,605 Members | 1,609 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,605 software developers and data experts.

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.

Jan 4 '06 #1
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 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.

Jan 4 '06 #2
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 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.

Jan 4 '06 #3
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 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.


Jan 4 '06 #4

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
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
1 post views Thread by XIAOLAOHU | last post: by
reply views Thread by leo001 | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.