Experimental Graph Library

Some work done ...

Hi, you might have a look at

http://se.inf.ethz.ch/projects/olivier_jeger/index.html

which includes the design of a graph library for Eiffel. From my experience: do not underestimate the complexity and problems you might encounter. ;)

Thank you very much Prof. Shroeller!

I had already encountered the possibility of a combinatorial explosion in the number of classes necessary, already. I had subclassed the GRAPH class with DIRECTED_GRAPH, UNDIRECTED_GRAPH, WEIGHTED_GRAPH, LABELED_GRAPH and so on for each property but I realized that the only one that is truly important is the fact that the graph is directed or not. So now, I have a generic parameter for vertices and I'm about to introduce another for edges. The edges would have to inherit from an EDGE class which has a cost query which returns 1.0 by default. This way, if we run, say, Dijkstra on a graph that is unweighted, it will only consider the number of edge as a distance.

Another difficulty is specifying precisely the algorithms, I'm not sure yet how it will be done.

Also, for the implementation part, I was mostly concentrating on adjacency lists implemented as arrays of arrays. This way, I have a linear time (in function of the number of neighbors, that we may call k) iterating through the neighborhood of a vertex. When we check if two vertices are connected, though instead of having a constant time, we may have a O (log k) access at best if we are willing to get O (k) time in edge insertion. This is a trade off that the user can easily choose, I think.

I may post what I already accomplished soon.

I have:

• the great part of the specifications and implementation of the adjacency list for directed graphs
• the associated cursors
• a beginning for a depth-first cursor.

Cheers,

Simon

Progress and name search

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

Name ideas

Looking for a name, I told myself that looking for differences and originalities could help find qualifiers for the library name since GraphLibrary seems a little naked. I thought that marking especially differences from the EiffelGraph library would help distinguish them.

I don't know much about the former and I haven't found any documentation on the main Eiffel related development sites. The description provided on EiffelRoom leads me to think that it's much more a UI related library so there is no overlap between the two and they might even complement one another very well. In this line of idea, I note that a binding between the two would be interesting.

So here are the adjectives I thought of to distinguish from EiffelGraph in particular and qualify the library:

• Algorithmic, rather than graphic or UI oriented;
• Model driven (we could also say `formal'), which doesn't seem to be very wide spread;
• Finally, it's made in Eiffel (obviously!).

Something like Eiffel Algorithmic and Model Driven Graph Library seems a little overkill even if we only call it EAMDGL. We could strip the library part and maybe the model driven part since it doesn't really cover the features of the library. We would be left with Eiffel Algorithmic Graph or EAG (which somewhat resembles the cry of someone tripping on a root) but it's not that bad either. We could also make some kind of mix like Eiffel AlGraph or Eiffel AlgoGraph.

If someone has better ideas or a preference among the names I listed, please speak up!

Simon

Look at existing library

I am seeing this discussion just now and don't know if it went anywhere, but should point out that an ETH student project by Olivier Jeger 3 years ago produced a carefully considered design. The result should be integrated into EiffelBase, after re-examination and possible improvements. This is in my opinion the place to restart from. See http://se.inf.ethz.ch/projects/olivier_jeger/index.html.

-- Bertrand Meyer