[squeak-dev] Re: [Pharo-project] Graph library in Smalltalk - Need for advices

Cédrick Béler cdrick65 at gmail.com
Mon Dec 20 12:35:52 UTC 2010


Thanks all for valuable information given and sorry for answering late...

Personally, I also think we need a graph lib for small scale application (100 nodes maximum). This is actually my needs as our research model won't go beyond 50 nodes I guess (and around the same scale for edges). That being said, in an ideal world, we would have a nice designed library that could map/translate/primitivize to a more efficient lib / functions easily. 

I've started looking at the exemples YossiDM gave to me and in particular Lemon which was according to him his best experience. I found the model quite clear and covering all what I expect for a generic graph lib (directed, undirected, mapping concept, iterators, and algorithms of course). Moreover and contrary to Boost, it's still developed in 2010.

To be more precise, here's what I expect for a generic graph lib in smalltalk (note all in Lemon except visualization):

- data structure: directed graphs, undirected graphs, possible loop and parallel edged, ..., trees (?)
- mapping: easily map objects, informations on nodes and/or edges (here, don't know if I'd like subclassing nodes/eges instead...)
- iterators: efficient way to iterate over nodes and edges
- algorithms: basic algorithms implementation (bfs, dfs, ..., shortest paths, ...), and plug-ability for specific ones...
- visualization: having an interactive graph visualization web/SVG and eventually morphic (... graphviz, mondrian, .......)

then, I could use this for my research work...
- I need "belief" nodes with associated conditional beliefs tables
- I need to implement algorithms to propagate an information change (change of a node state) in any nodes... 
****mainly, I'd like to get junction trees from a graph [1] which are rely useful for several domains in machine learning field ***

Actually, I don't know if I really need a graph lib as a simple implementation directed to bayesian should be enough but it's the second time I need graphs (last time was for planification) and I think that would be great to have a nice and clean basic implementation.

Couldn't we start developing something similar to Lemon (regarding "API", enitites, etc...) that would work for small scale project project in smalltalk ?
Yossi, what were the limitations you found with Lemon ?



[1] http://en.wikipedia.org/wiki/Junction_tree

> JGraphT worked alright in what I tried against in the past, but it won't
> scale to huge heights like most libs without major tweaking or a graph DB
> backing it along with some serious threading.
> Just to throw in a few others I've used, but not with Smalltalk:
> *  https://software.sandia.gov/trac/mtgl MTGL 
> *  http://lemon.cs.elte.hu/trac/lemon LEMON 
> * .NET  http://quickgraph.codeplex.com/ Quickgraph /Graph#
> *  http://igraph.sourceforge.net/introduction.html iGraph 
> *  http://snap-graph.sourceforge.net/ SNAP 
> Of the above, I've had some of the best experience with LEMON in terms of
> scale and speed for real-world usage. Unfortunately, none of these libraries
> include everything you'd want, so at some point you will have to roll some
> stuff yourself. That's been my experience at least.
> Some Graph or Graph-like Databases (tend to have some algorithm libs as
> well):
> *  http://www.infinitegraph.com InfiniteGraph  (this runs on Objectivity
> underneath the covers which has a Smalltalk impl)
> *  http://www.neo4j.org neo4j 
> *  http://www.kobrix.com/hgdb.jsp HyperGraphDB 
> Some related useful items for dealing with large sets and graphs when you
> are thinking about performance and/or parallel processing:
> *  http://gauss.cs.ucsb.edu/~aydin/doc/html/index.html Combinatorial BLAS 
> *  http://www.semanticdesigns.com/Products/PARLANSE/ PARLANSE 
> *  http://research.microsoft.com/en-us/projects/dryadlinq/ DRYAD LINQ 
> FYI, I would strongly recommend against using Ruby for anything with graphs
> except as a simple client lib. I spent a lot of time on this before and it
> simply does not scale or perform to anything beyond very simple cases, and
> the memory footprint in a real app becomes horrendous. We had to tweak the
> hell out of some libs to get anything decent and even then we ended up
> writing stacks of C to compensate. If you're just dealing with 100 vertex
> undirected graphs, then it works great. It's honestly the fault of a lot of
> the libs rather than the language, but nonetheless be warned.

Thanks ;-)

> -- 
> View this message in context: http://forum.world.st/Graph-library-in-Smalltalk-Need-for-advices-tp3092747p3092943.html
> Sent from the Pharo Smalltalk mailing list archive at Nabble.com.

More information about the Squeak-dev mailing list