By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 429,101 Members | 1,340 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,101 IT Pros & Developers. It's quick & easy.

# Plotting a graph using an array of relatively linked nodes

 P: n/a 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
Share this Question
3 Replies

 P: n/a The solution is to use your own stack. Something like (syntax not checked): Class MyNode { MyNode east; MyNode west; MyNode south; MyNode north; } Stack stack = new Stack(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" 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

 P: n/a 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" 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

 P: n/a 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 stack = new Stack(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" 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 stack = new Stack(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" 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. 