JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
Will this dfs work? | Reply
The article gives an iterative dfs using stack (code from article given below). I believe marking "visited" and "not visited" is not doing any help here. As a result all the neighbours of a node will always be reported as unvisited.

Correct me if I am wrong?

dfs(node start) {
 stack s;
 s.push(start);
 while (s.empty() == false) {
  top = s.top();
  s.pop();
  mark top as visited;
 
  check for termination condition
 
  add all of top's unvisited neighbors to the stack.
  mark top as not visited;
 }
}
Re: Will this dfs work? (response to post by therealsachin) | Reply
[Edit, never mind]
Re: Will this dfs work? (response to post by therealsachin) | Reply
I don't think adding top as unvisited after pushing it's unvisited neighbors onto the stack really helps at all. If start is vertex V, and it's only neighbor is vertex U, your algorithm would mark U as visited, push V onto the stack, and mark U as unvisited. Then top would be vertex V, which is marked as visited. Then vertex U is pushed onto the stack, and vertex V is marked as unvisited. This would result in an infinite loop.
Re: Will this dfs work? (response to post by therealsachin) | Reply
Ugh. I only read the article now and IMHO this part is pretty messed up. The author tries to explain two somewhat different concepts at once... (DFS and backtracking) and all he managed is to confuse the hell out of me.

I'll try to explain:

First thing we can do: generate all possible paths from a given vertex.
Second thing we can do: mark all vertices reachable from a given vertex.

Fact 1: It is possible to implement both of these in a similar way.
Fact 2: As eleusive noted already, the non-recursive code in the article is just plain wrong.

First of all, consider the correct recursive implementation from the article:
dfs(node current) {
 mark current as visited;
 visit all of current's unvisited neighbors by calling dfs(neighbor)
 // if we want backtracking instead of dfs, mark current as not visited;
}

There's one thing to note. The "visit all" part requires a local variable that loops over all neighbors. When we return from dfs(some neighbor), we don't start from the beginning but continue with the next neighbor.

If we want to use our own stack we have to store not only the vertices, but also the current value of these local variables.

Note that at any moment the vertices in the stack ("read bottom up") correspond to a valid path in the graph. (If we are generating all paths, the vertices currently in the stack are marked as visited, the others are unvisited.) The code from the article fails to achieve this.

A proper implementation (untested) would look as follows:
int G[N][N]; // adjacency matrix
int visited[N];
 
dfs(int start) {
  stack<int> S;
  S.push(start);
  S.push(0);
  visited[start]=1;
  while (!S.empty()) {
    int neighbor = S.top(); S.pop();
    int current = S.top(); S.pop();
    if (neighbor == N) {
      // if backtracking, visited[current]=0;
      continue; // we already processed all neighbors
    } else {
      S.push(current); S.push(neighbor+1); 
      if (G[current][neighbor] && (!visited[neighbor])) {
        // we can go this way, and this vertex is (currently) not visited
        S.push(neighbor); S.push(0); visited[neighbor]=1;
      }
    }
  }
}
Re: Will this dfs work? (response to post by misof) | Reply
Great explanation!
I was breaking my head trying to write the iterative version (without any success).
Thanks!
Re: Will this dfs work? (response to post by misof) | Reply
Absolutely right, I have no idea why I was trying to explain backtracking at the same time as the DFS. I think that got added in after I wrote the initial part, or it was just poorly done. It's probably best to remove the backtracking explanation and those two naughty lines (mark top as not visited).

After all, when was the last time you need an iterative backtracking implementation on Topcoder :). Iterative DFS on the other hand is quite useful.

Anybody spotted any other glaring issues?
Re: Will this dfs work? (response to post by misof) | Reply
watz the purpose S.push(0); why 0? i noticed u used it at the start n and the bottom of the while loom as well.

also i wanted to say i looked at snapdragon's code for the solution of a pathfinding problem that was discussed in the tutorial.
loo and behold! i m can't get a thing from snappy,yes the structure is the same but the code is frequanted wit a lot bit-wise operations which makes me wonder if the way put there deliberately to obscure the code against challenges or wat? if tatz not the case, why he is "messing" wit those bits?
Re: Will this dfs work? (response to post by mafoko) | Reply
What he's doing with the bitwise operations is encoding a player's position into one integer. Since the coordinates are at most 20, then you can represent each by 5 bits, hence the <<5 and &31 in the code. Then, he takes the first player's position and shifts it left by 10 bits to get a number of 20 bits, which he then checks if he's seen. All this makes it more efficient to store and probably faster, too.
Re: Will this dfs work? (response to post by mafoko) | Reply
The "0" is to indicate which is the first vertex that has not yet been processed -- note the part that says
int neighbor = S.top(); S.pop();
. That is, the top of the stack is being used to denote how many vertices you have already checked for being neighbours of current, so that the program can continue checking from there the next time.

As for SnapDragon's code, the bitwise operations have nothing to do with the pathfinding itself, he is merely using them to encode two numbers into a single int. He encodes i and j as (i<<5)+j. This works because i and j are both less than 25 (they are in fact less than 20), and the encoding works in pretty much the same way as you can encode two numbers a and b less than 10 as 10a+b. And just as you can retrieve a and b from their encoding (say c) by taking c/10 and c%10, you can retrieve i and j from their encoding (say k) by taking k>>5 and k&31.

Also, I don't intend offence, but I think you should pay more heed to your own excellent quote, which says "Thought is simply a manipulation of symbols; so be careful with your symbolism, for if it [symbolism] is chaotic, so is your thinking"! It would not take much extra effort on your part to say "What's" instead of "watz", "you" instead of "u", "I" instead of "i", "and" instead of "n", "what" instead of "wat", "that's" instead of "tatz" and "with" instead of "wit" (and in general try to use correct spelling and grammar), but it would save a lot of readers a lot of effort collectively in deciphering what you mean.
Re: Will this dfs work? (response to post by antimatter) | Reply
Finally understood how/why the bitwise ops were used,but i cannot see how that increases inficiency in space. I did a little bit of calculations,such that,in snap's code, 20 bits are being used for the visited/seen states which has a capacity of 2^20=1,048,576 array slots,

If we don't use encoding(i<<5+j),I found out that we use less memory,such that, if we rep visited states using a 4x4 matrix, a[20][20][20][20]), like its done in da tutorial(bottom of page) we use only 20x20x20x20=160,000 slots. Which is more efficient? Unless I am comparing "diamond" with "gold".
Re: Will this dfs work? (response to post by aboyner) | Reply
Fanx man, your post clarified encoding stuff for me,appreached. I still don't get why the zero is used at the beginning,I thought pushing the "start" position into the stack/queue waz enough. Maybe I need to spend more time understanding the code. The original code is more clear than watz being presented here.I also wondered a bit about the trailing "setting of current state to unvisited".

I m new to this site, so i guess I may take a while before I adopt to the ways of doing things down here.Neways,Fanx once again.
Re: Will this dfs work? (response to post by mafoko) | Reply
Yeah, sorry - I was thinking wrong when I said more efficient in space, but it is probably still more efficient in time. (one array dereferencing versus four) Also, if you know what you're doing, it's somewhat easier to code, because you can use pair<int> instead of your own struct or a pair of pairs (disgusting).
Re: Will this dfs work? (response to post by antimatter) | Reply
I get your point NOW, so it boils down to aesthetics? I can't agree less,the fact that one pair is used to rep the states is quite resplendent.
Re: Will this dfs work? (response to post by mafoko) | Reply
Jus wondering how I may map a nxn matrix onto 1xn matrix,

More formally,

Given a[i][j] and b[k] find f,such that k=f(i,j);
Re: Will this dfs work? (response to post by mafoko) | Reply
ok i got it! [reference]

if A and B are declared as

int A[n][m]; int B[n*m], then k=m*i+j, (tatz why i<<5+j!)
[ 1 2 ]    NEXT >

RSS