Plotting a graph using an array of relatively linked nodes

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • i

    #1

    Plotting a graph using an array of relatively linked nodes

    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 StackOverflowEx ception, 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(sout hOf(rm), "n", X, Y++);
    if (rm.e != 0)
    buildGraph(east Of(rm), "w", X--, Y);
    if (rm.w != 0)
    buildGraph(west Of(rm), "e", X++, Y);
    break;
    case "s":
    if (rm.n != 0)
    buildGraph(nort hOf(rm), "s", X, Y--);
    if (rm.e != 0)
    buildGraph(east Of(rm), "w", X--, Y);
    if (rm.w != 0)
    buildGraph(west Of(rm), "e", X++, Y);
    break;
    case "e":
    if (rm.n != 0)
    buildGraph(nort hOf(rm), "s", X, Y--);
    if (rm.s != 0)
    buildGraph(sout hOf(rm), "n", X, Y++);
    if (rm.w != 0)
    buildGraph(west Of(rm), "e", X++, Y);
    break;
    case "w":
    if (rm.n != 0)
    buildGraph(nort hOf(rm), "s", X, Y--);
    if (rm.s != 0)
    buildGraph(sout hOf(rm), "n", X, Y++);
    if (rm.e != 0)
    buildGraph(east Of(rm), "w", X--, Y);
    break;
    case "startpoint ":
    if (rm.n != 0)
    buildGraph(nort hOf(rm), "s", X, Y--);
    if (rm.s != 0)
    buildGraph(sout hOf(rm), "n", X, Y++);
    if (rm.e != 0)
    buildGraph(east Of(rm), "w", X--, Y);
    if (rm.w != 0)
    buildGraph(west Of(rm), "e", X++, Y);
    break;
    }
    }

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

    Thanks.

  • Fred Mellender

    #2
    Re: Plotting a graph using an array of relatively linked nodes

    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>(1 0);

    stack.Push(root Node); //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" <typppo@gmail.c om> wrote in message
    news:1136342030 .366360.194210@ z14g2000cwz.goo glegroups.com.. .[color=blue]
    > 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 StackOverflowEx ception, 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(sout hOf(rm), "n", X, Y++);
    > if (rm.e != 0)
    > buildGraph(east Of(rm), "w", X--, Y);
    > if (rm.w != 0)
    > buildGraph(west Of(rm), "e", X++, Y);
    > break;
    > case "s":
    > if (rm.n != 0)
    > buildGraph(nort hOf(rm), "s", X, Y--);
    > if (rm.e != 0)
    > buildGraph(east Of(rm), "w", X--, Y);
    > if (rm.w != 0)
    > buildGraph(west Of(rm), "e", X++, Y);
    > break;
    > case "e":
    > if (rm.n != 0)
    > buildGraph(nort hOf(rm), "s", X, Y--);
    > if (rm.s != 0)
    > buildGraph(sout hOf(rm), "n", X, Y++);
    > if (rm.w != 0)
    > buildGraph(west Of(rm), "e", X++, Y);
    > break;
    > case "w":
    > if (rm.n != 0)
    > buildGraph(nort hOf(rm), "s", X, Y--);
    > if (rm.s != 0)
    > buildGraph(sout hOf(rm), "n", X, Y++);
    > if (rm.e != 0)
    > buildGraph(east Of(rm), "w", X--, Y);
    > break;
    > case "startpoint ":
    > if (rm.n != 0)
    > buildGraph(nort hOf(rm), "s", X, Y--);
    > if (rm.s != 0)
    > buildGraph(sout hOf(rm), "n", X, Y++);
    > if (rm.e != 0)
    > buildGraph(east Of(rm), "w", X--, Y);
    > if (rm.w != 0)
    > buildGraph(west Of(rm), "e", X++, Y);
    > break;
    > }
    > }
    >
    > Maybe I'm completely missing the concept. What's the correct way to do
    > this?
    >
    > Thanks.
    >[/color]


    Comment

    • Marc Gravell

      #3
      Re: Plotting a graph using an array of relatively linked nodes

      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" <typppo@gmail.c om> wrote in message
      news:1136342030 .366360.194210@ z14g2000cwz.goo glegroups.com.. .[color=blue]
      > 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 StackOverflowEx ception, 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(sout hOf(rm), "n", X, Y++);
      > if (rm.e != 0)
      > buildGraph(east Of(rm), "w", X--, Y);
      > if (rm.w != 0)
      > buildGraph(west Of(rm), "e", X++, Y);
      > break;
      > case "s":
      > if (rm.n != 0)
      > buildGraph(nort hOf(rm), "s", X, Y--);
      > if (rm.e != 0)
      > buildGraph(east Of(rm), "w", X--, Y);
      > if (rm.w != 0)
      > buildGraph(west Of(rm), "e", X++, Y);
      > break;
      > case "e":
      > if (rm.n != 0)
      > buildGraph(nort hOf(rm), "s", X, Y--);
      > if (rm.s != 0)
      > buildGraph(sout hOf(rm), "n", X, Y++);
      > if (rm.w != 0)
      > buildGraph(west Of(rm), "e", X++, Y);
      > break;
      > case "w":
      > if (rm.n != 0)
      > buildGraph(nort hOf(rm), "s", X, Y--);
      > if (rm.s != 0)
      > buildGraph(sout hOf(rm), "n", X, Y++);
      > if (rm.e != 0)
      > buildGraph(east Of(rm), "w", X--, Y);
      > break;
      > case "startpoint ":
      > if (rm.n != 0)
      > buildGraph(nort hOf(rm), "s", X, Y--);
      > if (rm.s != 0)
      > buildGraph(sout hOf(rm), "n", X, Y++);
      > if (rm.e != 0)
      > buildGraph(east Of(rm), "w", X--, Y);
      > if (rm.w != 0)
      > buildGraph(west Of(rm), "e", X++, Y);
      > break;
      > }
      > }
      >
      > Maybe I'm completely missing the concept. What's the correct way to do
      > this?
      >
      > Thanks.
      >[/color]


      Comment

      • Marc Gravell

        #4
        Re: Plotting a graph using an array of relatively linked nodes

        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(MyNod e node, int x, int y) {
        Node = node;
        X = x;
        Y = y;
        }
        }

        and then:

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

        stack.Push(new QueueItem(rootN ode, 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!=n ull) stack.Push(new QueueItem(node. east, x+1,y));
        if(node.east!=n ull) stack.Push(new QueueItem(node. east, x+1,y));
        if(node.east!=n ull) 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" <nospamPlease_f redm@frontierne t.net> wrote in message
        news:KyNuf.1116 $qg.704@news02. roc.ny...[color=blue]
        > 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>(1 0);
        >
        > stack.Push(root Node); //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" <typppo@gmail.c om> wrote in message
        > news:1136342030 .366360.194210@ z14g2000cwz.goo glegroups.com.. .[color=green]
        >> 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 StackOverflowEx ception, 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(sout hOf(rm), "n", X, Y++);
        >> if (rm.e != 0)
        >> buildGraph(east Of(rm), "w", X--, Y);
        >> if (rm.w != 0)
        >> buildGraph(west Of(rm), "e", X++, Y);
        >> break;
        >> case "s":
        >> if (rm.n != 0)
        >> buildGraph(nort hOf(rm), "s", X, Y--);
        >> if (rm.e != 0)
        >> buildGraph(east Of(rm), "w", X--, Y);
        >> if (rm.w != 0)
        >> buildGraph(west Of(rm), "e", X++, Y);
        >> break;
        >> case "e":
        >> if (rm.n != 0)
        >> buildGraph(nort hOf(rm), "s", X, Y--);
        >> if (rm.s != 0)
        >> buildGraph(sout hOf(rm), "n", X, Y++);
        >> if (rm.w != 0)
        >> buildGraph(west Of(rm), "e", X++, Y);
        >> break;
        >> case "w":
        >> if (rm.n != 0)
        >> buildGraph(nort hOf(rm), "s", X, Y--);
        >> if (rm.s != 0)
        >> buildGraph(sout hOf(rm), "n", X, Y++);
        >> if (rm.e != 0)
        >> buildGraph(east Of(rm), "w", X--, Y);
        >> break;
        >> case "startpoint ":
        >> if (rm.n != 0)
        >> buildGraph(nort hOf(rm), "s", X, Y--);
        >> if (rm.s != 0)
        >> buildGraph(sout hOf(rm), "n", X, Y++);
        >> if (rm.e != 0)
        >> buildGraph(east Of(rm), "w", X--, Y);
        >> if (rm.w != 0)
        >> buildGraph(west Of(rm), "e", X++, Y);
        >> break;
        >> }
        >> }
        >>
        >> Maybe I'm completely missing the concept. What's the correct way to do
        >> this?
        >>
        >> Thanks.
        >>[/color]
        >
        >[/color]


        Comment

        Working...