breadth first search implementation

bahadur · 03-19-2005, 03:34 AM

ok now i am doing the assignment and i am stuck with a problem in which i have to do a breadth first search.

here is the problem statement

You are maintaining a website which undergoes frequent editing. You need to ensure that after changes have been made to the website or a backup/restore procedure has taken place that the files have the appropriate file permission that allow the web server to deliver the content (e.g. read and sometimes execute) while also ensuring security is maintained (e.g. prevent unauthorised access to files by restricting permissions to other users) To achieve this aim it has been decided to write some utility programs which will descend the directory tree of the website checking for the correct permissions of each directory and file and changing them if they are incorrect.

how do i keep track of which directory i have processed and which i havent?

like for example there are 4 directories in the root directory.
and each four directory have 2 directories on each level. that is every sub directory again have 2 directories. and this situation is a 4 levels "deep".

so once i have done a breadth first search and i have come back to the top how do i keep track that the i have processed the first directory and now it is turn to process the next.

i am asking for the trick.

like one way out is to keep on storing all the Inode values of the directories accessed and than comparing them to check whether this directory has been already processed or not.

is there another better option or not?

like a smarter way which wouldnt require me storing any thing but still letting me know that whether this directory has been processed or not?

one way i found out was to use the ls -F switch which marks a directory with a trailing (/)

so next time u come back to this directory u will know that this has been processed already.

any other ideas?

ksgill · 03-19-2005, 07:04 AM

Storing the visited nodes (directories) somewhere and then testing to see if they are visited or not everytime you try to do something is the easiest way. If you could flag them as visited by changing their names in a temporary tree, that could be other way.. but what you are doing sounds just about right. Or you could try something like this:

Code:

class Node {
    String name;        // name of the directory
     int node;             // 0 for not visited and 1 for visited
}

Change the values as you visit the nodes.. many different ways of doing it.. Choose one implementation and stick with it.