Recursive function..

[DrJones]

I am at moment trying create a function which take a node, and transverse through the adjacent .

Such that

if Root node A(0,0) has two adjacent nodes B(1,0) and C(0,1).

The function has to traverse the graph in a manner such that the next position of the node will be like this

A(0,0) -> B(1,0) -> B1(2,0) ->.. until a certain condition is fulfilled.

Each node is defined using this struct

struc vertex
{
Node * me;
Node * adjacent;
}

struct Node
{
  pair<int,int> position;
  vector<vertex> adjacent; 

}

The condition mentioned above is the size of next node adjacent. When the size becomes above either 2 or 4 it has to stop traversing, and continue traversing to the next node when size of the adjacent it three.

The same thing has to be done in the who direction.

I am pretty sure that this can be done in a recursive function.. I just don't know how..

[Kevin C]

a) Ok, so, for starters, can you write a header (i.e. prototype i.e. declaration) of the mentioned recursive function?

b) Your structure 'Node' has a member which is a vector of 'Nodes'. Could you post a definition of type 'Nodes', too?

[DrJones]

Copy paste error .. I am not sure with the prototype declaration though..

Is it not clear how the function should work?

void function(root)

move = root + (1,0)

If move.adjacent.size()  == 3
   function(move)

If move.adjacent.size() == 2
  exit() with list of previous visited nodes

if move.adjacent.size() == 4
  exit() with move node

[Kevin C]

1) Your structure 'Node' can not describe a full graph, it can be at most a tree

2) I'm trying to make you write it instead of me writing it, and also to figure out your level of knowledge. So for starters, can you attempt to write a header of this function, with a better name at least and to give parameter types also.

3) Which node is a 'move node'?

4) If the function needs to traverse the graph in an essentially linear fashion, as you are describing, then I can't figure out why is recursion needed. A loop would be sufficient instead.

[DrJones]

1 . Each node is defined as such and saved in a vector<node> graph.


3. Move node is the next node which is adjacent to previous node with a position increase in position.first.


4.
yeah that would be a solution.. But would I not still need some form recursion as I need to check each adjacent node i the next node, to which fulfill the criteria of having position. first being incremented from the previous one...

[Kevin C]

2. Can you make an attempt at making a function header/prototype? As you describe, the mentioned function should result in some value, so returning void does not make sense

4. Ok, we can just try to write it and then see whether we need recursion or not.

[DrJones]

I see..
It would be nice..

It would be nice if the function could output a vector of the positions of the nodes it had traversed..

so something like

vector<pair<int,int>>  function(root)
vector<pair<int,int>> result;
move = root + (1,0)
result.push_back(move.position);

If move.adjacent.size()  == 3
   function(move)

If move.adjacent.size() == 2
  exit() with list of previous visited nodes
  return result;

if move.adjacent.size() == 4
  exit() with move node
 return result;

I am not sure if understand what you mean by header/prototype

[Kevin C]

So, the header / prototype / declaration could perhaps be:

vector<Node> PathThroughNodesSized3(Node start)

Now try to write the rest of the function. Use C++ code, not pseudocode.

[DrJones]

I tried to write it down on a piece of paper, and implement in code which ended up being something like this.

http://pastebin.com/RP7bKKsn

I had to do it like this, or it wouldn't be able to be posted.

The problem here is that it gets stuck at the first node being the case where i cout << "neighbor direction is third" << endl;

The function keep looping the neighbor vector of that node.
And couts´s this message.

position before: 21 now position: 31 now positions neighbour: 21 change is: 1 0
position before: 21 now position: 31 now positions neighbour: 32 change is: 0 -1

It seems like that it has reached a node which is a corner => 2 neighbour, but is still capable of entering the while loop..