Experimental Graph Library

by Simon Hudon (modified: 2007 Jun 01)

I'm currently building an experimental library to deal with graphs. Its main features are:

  • It's general;
  • It provides a flexible adjacency list implementation for both directed and non-directed graphs;
  • The specifications of the classes are precise (they expressed as mathematical models using the EiffelSpec library);
  • It's extensible (new implementation of graph or special search cursors can be added);

It implements basic graph algorithms such as:

  • Searches (depth-first, breadth-first, uniform cost, A*);
  • Topological sort;
  • Shortest-path (Bellman, Dijkstra, Floyd);
  • Minimum Spanning Tree (Kruskal and two versions of Prim);
  • Maybe some AI algorithms (like graph algorithms for constraint solving problems).

I would like to know if there is an actual interest exists for such a library and if people would be interested in commenting it as I progress.

It is not under any license yet and I'm still searching which type would best suit my needs.

I welcome every (constructive) comments.

Cheers,

Simon

Comments
  • Bernd Schoeller (9 years ago 30/5/2007)

    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. ;)

  • Simon Hudon (9 years ago 30/5/2007)

    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

    • Simon Hudon (9 years ago 30/5/2007)

      Typo

      Sorry, I meant Prof. Schoeller, not Shroeller, my bad!

      • Andreas Leitner (9 years ago 31/5/2007)

        Don't worry, he is not a Prof. either (;

        • Simon Hudon (9 years ago 31/5/2007)

          Error

          Next thing I'll know will be that I'm not even be on an Eiffel related page!

          • Martin Seiler (9 years ago 31/5/2007)

            Perfect place

            I think you are at the right place to do something like this.

            I am very interested in seeing your progress and the design of the library. It is in fact one of the first things I pushed on my to-do-stack. It's a pity that I decided to use a stack and not a FIFO queue in the first place. But the stack has the advantage that I can to whatever I want ;-)

            Back to business: Is there already source code somewhere? Did you consider Origo to host your project?

            -- mTn-_-|

            • Simon Hudon (9 years ago 31/5/2007)

              Hosting

              I did not consider any hosting yet but it would be interesting. I do not know particularly origo hosting services apart from the fact that EiffelStudio is hosted there. I would have to check it out.

              The source is already well in progress and hosted on my own hard drive and I'm thinking of showing it off as I progress to collect comments. I'm not very familiar with the licensing issue though so I'll have to check what suits my needs best.

              I am happy to see that it rises some interest and I'm looking forward to showing it to you guys.

              I will post soon to show what I already have and what I'm planning to do on the short term.

              Cheers!

              Simon

  • Simon Hudon (9 years ago 31/5/2007)

    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

  • Simon Hudon (9 years ago 1/6/2007)

    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

    • Benoit Alain (9 years ago 4/6/2007)

      project name

      It seems important to the personality of a project to get it a good name. It raises interest, makes it half real before it has even started. I don't pretend following are good names. I just give them as suggestions to give you ideas. Probably you'll find best to take parts of one and add it to one of yours.

      • Eiffel Formal Graphs
      • Math2Eiffel
      • Eiffel Graph Theory Port
      • Eiffel Graph Intelligence
      • Graphormalgorithms ! (Graph Formal Algorithms)
      • Eiffel Applied Graphs
  • Bertrand Meyer (9 years ago 28/12/2007)

    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

    • Simon Hudon (9 years ago 29/12/2007)

      Thank you very much but Bernd Schoeller has already sent it to me. I've read the thesis and I found it very interesting. Is it possible to get access to Olivier Jeger's graph library? I think it may be useful to continue my own work.

      As for where it went, I have not updated my Origo page (or my svn repository, for that matter) during this fall but the project is still alive. For the moment, I'm exploring the possibility to use refinement calculus to help me in my development.

      Simon Hudon