On Fri, Sep 19, 2003 at 04:43:18PM +0200, Samir Saidani wrote:
> Hello
> 
> I've just made a monticello version of Collection-Graphs and
> Morphic-Graphs...
> Luciano, could you try this version and tell me if it seems ok to put
> it on squeakmap  ? Maybe could we find an ftp site or http/webdav somewhere ??
> Joshua, I took a quick look on your version, and your package seems
> quite different from the collection-graphs package. For instance,
> consider the creation of a graph in collection-graphs:
> 
> 	"Graph exampleGraph."
> 	| d |
> 	d _ self ordered.
> 	d addEdge: #r1 -> #n1.
> 	d addEdge: #r1 -> #n2.
> 	d addEdge: #r2 -> #n2.
> 	d addEdge: #n1 -> #n3.
> 	d addEdge: #n2 -> #n3.
> 	d addEdge: #n3 -> #r1.
> 	^ d

The 'nodes' and 'edges' variables below are not necessary for creating
the graph; they're used for my test cases.  The simplest way to create 
the graph similar to the one above is:

       | g1 r1 r2 n1 n2 n3 nodes edges |

       g1 _ KGraph new.
       
       "Create nodes - automatically added to graph"
       r1 := g1 newNode.
       r2 := g1 newNode.
       n1 := g1 newNode.
       n2 := g1 newNode.
       n3 := g1 newNode.

       "Create edges - automatically added to graph"
       r1 ==> n1.
       r1 ==> n2.
       r2 ==> n2.
       n1 ==> n3.
       n2 ==> n3.
       n3 ==> r1.

       ^ g1

As you can see, the syntax is not as bad as you first thought.  It
wouldn't be hard to allow edge creation to use keys instead of actual
node references.  Graph>>newEdgeFrom:to: could check if the arguments
are nodes, and if not, treat them as keys to look up the corresponding
nodes (creating nodes if necessary).  Or we could make a Graph method
that takes either a KGraphEdge or an Association as an argument. Or...


I'm looking through the other graph package right now, and here
are some comments:

- my package allows direct access to the edges from the graph, whereas
the other package stores them as neighbors of each node.  I was originally
envisioning situations where you would want to apply different connectivity
to the same vertices; my approach would make this easier to support (not 
implemented yet... I decided to not get *too* sidetracked from the reason
I wrote this in the first place)

- in my package, edges and nodes maintain an index for O(1)
access. This is helpful for creating graph algorithms.  For example,
Dijkstra's algorithm maintains arrays with visit status, distances,
and precessors.  These indices allow the algorithm to maintain it's
own arrays, instead of attaching labels for these values directly to
node/edge objects.  (I can't really comment on how this compares to
the other package, because their Dijkstra implementation doesn't seem
to be finished)

- both packages use the Factory pattern for node creation.  Mine also does
this for edge creation.

- I haven't used the other package enough to really understand it, but
it seems like a good start, and is probably farther along then my
package, overall.

Joshua


> 
> and in kgraph :
> 
> 	| nodes edges |
> 
> 	g1 _ KGraph new.
> 	nodes _ OrderedCollection new.
> 	edges _ OrderedCollection new.
> 	g1 setProperty: #createdNodes toValue: nodes.
> 	g1 setProperty: #createdEdges toValue: edges.
> 
> 	nodes add: (g1 newNode name: 'g1-1').
> 	nodes add: (g1 newNode name: 'g1-2').
> 	nodes add: (g1 newNode name: 'g1-3').
> 
> 	edges add: (nodes first ==> nodes second).
> 	edges add: (nodes second <== nodes third).
> 
> 
> It's not very intuitive ?? Do you think possible to merge this two
> project while keeping the intuitive graph creation in
> collections-graphs ?




> 
> 
> "Joshua 'Schwa' Gargus" <schwa at cc.gatech.edu> writes:
> 
> > Ok, my KGraph package is now on SqueakMap.  Most of the classes have
> > comments.  My approach to graph algorithms was inspired by the Boost
> > graph library, and defines hooks for specific events in each algorithm
> > that allow you to customize usage for your application.
> >
> > Joshua
> 



>