Graph Library: Progress and Name Search

by Simon Hudon (modified: 2007 Jun 01)

NOTE: this entry has already been put in a comment about my first one on the subject but I've been pointed out that it's a poor usage of comments. Don't be surprised if it looks familiar to some of you. The next one will be a copy and paste too without this notice.

I finished yesterday the testing of the preorder side of DEPTH_FIRST_SEARCH_CURSOR and I almost finished the postorder side too.

The way I organized the class, the traversal order is an option that can be set. I'm not sure yet of the exact effect of changing the traversal order since it discards the validity of the content of the stack. The options are:

  • Put begining or off as precondition of each of the option setting commands and make them maintain the cursor position.
  • The option setting has the effect of putting the cursor off the sequence so a call to start is necessary after it.
  • Merge the option setting commands with the start command like start_preorder

Since I want precise specification, I was searching for a description that would not over specify a depth first traversal. Since the order of the vertices' neighbors is not defined a cannot tell that a precise order must be followed. What I decided is to add a path model to the cursor. It represents the path followed from root of the search to the current item of the cursor.

As an invariant, I can say that, in all time when working in preorder, all items in the path except for item must have been visited already. Also, when we move forth, either we add a vertex to the end of the path or we cut a certain length of the end off it and append one vertex. This was for the preorder case only. The postorder case resembles it. In either case, all vertex of the path must be adjacent to the next.

On another topic, I'm also looking for a name for the library since EiffelGraph is already taken. Suggestions are welcome!

Notice to the interested: the design details along with the code should be coming soon. I think I'd host it on origo, I'm thinking on it.

Cheers!

Simon