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 !
On Wednesday 04 December 2002 07:02 am, Samir Saidani wrote:
- Connector-Morph (It's not truly an implementation of
Collection-Graph, but it can be use to display a Graph, with MorphicWrapper).
Connectors may be helpful for allowing interaction and editing with graphs (as well as visualization). You can query the connected components and get notifications upon connection changes.
Hi, I have some very basic work on graphs for Slate, though none of the interesting algorithms have been done. Arrow's Graphs are just the relational kind of graphs. And I *really* need to update that code. This is what happens when your research projects are hobbies. :P
Anyway, I am also interested in the subject. One thing you might distinguish is the manner of the implementation, in other words, what objects are used, whether the "contents" of the graph have to be the nodes themselves, how neighborhood is annotated, etc. These things actually determine the behavioral type of the graph. I'm discovering this, since I'm trying to write interchangeable implementations for common collection concepts.
Anyway, I would like to contribute if it's necessary. I don't know when I'll have the need for great graph support in Slate, and need is driving the implementation direction at the moment.
Good luck!
On Wed, 4 Dec 2002, 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 :
- 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 !
Hello Brian,
I'm interested by your basic work, maybe can I find some inspirations for the implementation I plan to do. Could you send me it ? I looked to your articles on Arrow, and specially by ArrowTechnical.ps, but it is almost empty :-( Do you have some materials explaining clearly your Arrow Architecture ?
Thanks !
Samir
Brian T Rice water@tunes.org writes:
Hi, I have some very basic work on graphs for Slate, though none of the interesting algorithms have been done. Arrow's Graphs are just the relational kind of graphs. And I *really* need to update that code. This is what happens when your research projects are hobbies. :P
Anyway, I am also interested in the subject. One thing you might distinguish is the manner of the implementation, in other words, what objects are used, whether the "contents" of the graph have to be the nodes themselves, how neighborhood is annotated, etc. These things actually determine the behavioral type of the graph. I'm discovering this, since I'm trying to write interchangeable implementations for common collection concepts.
Anyway, I would like to contribute if it's necessary. I don't know when I'll have the need for great graph support in Slate, and need is driving the implementation direction at the moment.
Good luck!
On Wed, 4 Dec 2002, Samir Saidani wrote:
Hello Brian,
I'm interested by your basic work, maybe can I find some inspirations for the implementation I plan to do. Could you send me it ? I looked to your articles on Arrow, and specially by ArrowTechnical.ps, but it is almost empty :-( Do you have some materials explaining clearly your Arrow Architecture ?
Thanks !
Samir
Actually, I have learned quite a bit since I last published on it 2 years ago. There's so much information that I need to start mostly from scratch, thankfully with very concrete ideas. The Squeak implementation basically ran out of steam because Squeak didn't support declarativeness well enough. The eventual idea was to make a network of implementations each running in a different programming language, so that the information would be transferred to and handled by the appropriate semantics per language. Of course, I need *time* and preferrably funding to get this somewhere, so don't hold your breath. But enough people have bothered me recently about it that I have done some initial work to set up a separate page and develop the explanations more extensively. Contact me off the list for further details, please, though.
Thanks.
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/manchest....
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 !
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/manchest....
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
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/manchest....
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
Daniel Vainsencher wrote:
Also, in the Spaghetti Tracer, I implemented a couple of algorithms (transcribed into Smalltalk from material on the web) that are interesting - linear algorithms for detecting weakly connected and strongly connected components. Note that Aglo graph layout (also on SM) is a (quite alpha) tool for laying out graphs - I got good results for laying out not-too-big DAGs.
It seems that there are many projects doing something with graphs. Perhaps we could work in a common codebase, or at least reuse some code or ideas. I'll see if I can use the algorithms from the Spaghetti Tracer. I should try to use Connectors and Aglo.
Joshua 'Schwa' Gargus wrote:
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.
It would be great to have a common codebase for graphs. Is you code published somewhere?
Luciano.-
On Tue, Mar 11, 2003 at 09:53:25PM -0800, Luciano Notarfrancesco wrote:
Joshua 'Schwa' Gargus wrote:
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.
It would be great to have a common codebase for graphs. Is you code published somewhere?
Not yet. I'll try to get from pre-alpha to alpha by the end of the weekend.
Joshua
Luciano.-
On Tue, Mar 11, 2003 at 09:53:25PM -0800, Luciano Notarfrancesco wrote:
Joshua 'Schwa' Gargus wrote:
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.
It would be great to have a common codebase for graphs. Is you code published somewhere?
I'm attaching it to this email. File in Propertied first, HeapIndexCallback second, and Graph third. I'd recommend starting with the examples in the KDijkstra class.
Joshua
Luciano.-
squeak-dev@lists.squeakfoundation.org
-
Brian T Rice -
Joshua 'Schwa' Gargus -
Luciano Notarfrancesco -
Ned Konz -
Samir Saidani