eiffelroom - generic - Comments

Thank you very much but

maverick — Sat, 29 Dec 2007 00:43:19 -0800

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

Look at existing library

bmeyer — Thu, 27 Dec 2007 15:56:22 -0800

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

Church numerals

colin-adams — Tue, 05 Jun 2007 07:28:54 -0700

Couldn't you make it more complicated by using Church numerals? Colin Adams

Fixed ...

schoelle — Tue, 05 Jun 2007 00:16:23 -0700

You are right, SET[G] would not type check. Was a typo. I have fixed it in the article.

Signature of i_th_power

doenniu — Mon, 04 Jun 2007 12:10:58 -0700

I think that the signature of i_th_power has to be:

i_th_power (i: INTEGER): SET [ANY]

I like NAT, that helps me on my endless quest to write a program that counts from 1 to 5 in the most complicated way:

(nat_to_integer (create {NAT [NAT [BOOLEAN]]}) |..| nat_to_integer (create {NAT [NAT [NAT [NAT [NAT [NAT [BOOLEAN]]]]]]})).do_all (agent (a_int: INTEGER) do print (a_int.out + "%N") end)

project name

Vcimdarf — Mon, 04 Jun 2007 08:34:09 -0700

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

Name ideas

maverick — Fri, 01 Jun 2007 06:56:26 -0700

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

Progress and name search

maverick — Thu, 31 May 2007 09:23:33 -0700

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

Hosting

maverick — Wed, 30 May 2007 13:16:33 -0700

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

Perfect place

mtn — Wed, 30 May 2007 12:28:21 -0700

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-_-|

Error

maverick — Wed, 30 May 2007 11:01:36 -0700

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

Don't worry, he is not a

aleitner — Wed, 30 May 2007 10:33:29 -0700

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

Typo

maverick — Wed, 30 May 2007 05:39:46 -0700

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

Thank you very much Prof.

maverick — Wed, 30 May 2007 05:26:10 -0700

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

Some work done ...

schoelle — Wed, 30 May 2007 00:15:42 -0700

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