Nevermind, I had a closer look and realized that the Dijkstra class is not
finished.

I missed this thread back in December, but I'm working on a graph
package too.  I'm basing the algorithms on the approach used by the
Boost graph library (www.boost.org), as well as on the paper
"Object-Oriented Design of Graph Oriented Data Structures" by Pizzonia
and Battista.  This allows customization of standard algorithms to
specific applications.  

For example, the paper "Controlled Animation of Video Sprites" by
Shodl and Essa uses Dijkstra's algorithm to repeatedly search for the
k closest video frames (treated as graph nodes) out of a large video
database.  Most library implementations of Dijkstra's algorithm don't
allow you to exit early, and thus spend time finding the shortest path
to all of the nodes instead of the k closest.  With Pizzonia's
approach, you can quit when a certain number of nodes are checked, when
the next-shortest path exceeds a threshold length, or whatever.

I'm planning to do the minimum amount of work required to support my
research, but if others are interested on working on a common codebase
(not necessarily based on mine, which is pre-alpha), then I'm game.

Joshua




On Sat, Mar 08, 2003 at 11:21:56AM -0500, Joshua 'Schwa' Gargus wrote:
> I didn't get a chance to look at your package too closely, but does the
> implementation of Dijkstra's algorithm work?  It didn't look like the 
> heap gets updated when the best-known distance to a node gets changed;
> am I wrong?
> 
> Sorry for not looking more closely, but I'm heading out for several
> hours and thought I'd see if anyone can comment before I come back.
> 
> Thanks,
> Joshua
> 
> 
> On Sat, Mar 08, 2003 at 01:10:45AM -0800, Luciano Notarfrancesco wrote:
> > Hi Samir,
> > You might want to take a look at the Graphs package I just registered in 
> > SqueakMap. It's a port of Mario Wolczko's graphs.st goodie (*) with some 
> > additional funcionality. Look at the class side of Graph and RootedGraph 
> > for some examples.
> > There's also a Graph-Morphs package that does graph layout with two 
> > different methods: springs layout (like the original MathMorphs graphs 
> > implemented by Gerardo Richarte) and radial layout. You can see how it 
> > looks trying 'SpringsGraphMorph new graph: RootedGraph 
> > exampleMediumTree; openInWorld', or the same with RadialGraphMorph.
> > 
> > Luciano.-
> > (*) 
> > http://wuarchive.wustl.edu/languages/smalltalk/Smalltalk/MANCHESTER/manchester/4.0/graphs.st.
> > 
> > 
> > Samir Saidani wrote:
> > 
> > >Hi
> > >
> > >I'm planning building a Collection-Graph, for my
> > >research (phD). I would like to know if there is such a functional
> > >Graph classes ? 
> > >
> > >I know several implementations :
> > >
> > >- MathMorph (The GraphWrapper implementation seems not to work in 3.2, and http://mathmorphs.swiki.net/44 -
> > >GraphAlgorihtms.zip is unavailable :-()
> > >
> > >- Connector-Morph (It's not truly an implementation of
> > >Collection-Graph, but it can be use to display a Graph,
> > >with MorphicWrapper).
> > >
> > >- T-Gen implements a Collection-Graph too, but the implementation is
> > >oriented parsing...
> > >
> > >- Arrow implements a Graph, with a new and original manner,  I
> > >have to see if it's possible to encapsulate the common abstraction of graphs
> > >(I mean nodes, edges...).
> > >
> > >Do you know others implementations ?
> > >
> > >Thanks at all !
> > >
> > >  
> > >
> > 
> > 
> > -- 
> > http://community.corest.com/~luciano
> > CCB0 B2B0 BCCB 8178 CA8B  4C08 AE9B D2F2 E9CC E897
> > 
> >