[squeak-dev] Re: [Pharo-project] Graph library in Smalltalk - Need
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  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 ?
> 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
> * 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.
> 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