We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
Index › Programming Questions & Help › Other Libraries › Graph layout for a large number of objects
‹ Previous Topic | Next Topic ›
Pages: 1 2 
Graph layout for a large number of objects (Read 15611 times)
jeffg
Graph layout for a large number of objects
Apr 2nd, 2009, 7:20am  
I'm struggling to find a library to use with Processing that could provide a force-directed (spring graph) layout for a large number (over 20,000, would like over 100,000) of points in 3d (x,y,z).  I've tried traer.physics but that will only scale to about 500-1000 nodes.  I can't seem to get the 3d components of JUNG to work.  Does anyone have a suggestion as to what I could use to plot the layout of a node/edge network?

Thanks,
Jeffg
Back to top
 
WWW  
PhiLho 
Re: Graph layout for a large number of objects
Reply #1 - Apr 2nd, 2009, 12:01pm  
I don't know how they perform, but JohnG used the JGraphT library which seem to do something similar.
[searching...] Oh, I see you are already aware of this library! Anyway, I leave the reference, which might be useful to somebody else.

I know also the yWorks library although it is partially () commercial.

There is JBox2D and its Processing wrapper, but I don't know if it will perform better than traer.
Back to top
 
WWW  
jeffg
Re: Graph layout for a large number of objects
Reply #2 - Apr 2nd, 2009, 12:18pm  
I'm trying to understand JGraphT as they don't provide enough information on their site and their forum is dead.  Not sure if it does layouts at all, from what I can gather, it just does algorithms like shortest path.  I think JGraph may be providing the layout.  Also not sure if it does 3d.

YWorks doesn't do 3d.  

JBox2D might be something.  I'm am interest if Jbox2D could do something like force directed layouts.  Toxi's physic library is another similar one that does some verlet physics.  However, I haven't seen these put into a graph form, they've usually just been trajectories and motion physics.  Let me know if I'm wrong here.
Back to top
 
WWW  
jeffg
Re: Graph layout for a large number of objects
Reply #3 - Apr 2nd, 2009, 12:50pm  
Walrus has a nice graph layout algorithm that handles a great many objects (I've seen it do 1,000,000 very quickly).  It is open source and written in Java.  I don't have the JavaFu to modify this as an API that processing could hook into, but I that would probably look cool.  It seems each component has it's own java file to include graph & layout.  I'm looking for something more in line with euclidean space but it would be neat to see it.

I'd really like to see a 3d API for LGL or DrL. Smiley
Back to top
 
WWW  
toxi
Re: Graph layout for a large number of objects
Reply #4 - Apr 28th, 2009, 7:15am  
jeffg wrote on Apr 2nd, 2009, 12:18pm:
Toxi's physic library is another similar one that does some verlet physics.  However, I haven't seen these put into a graph form, they've usually just been trajectories and motion physics.  Let me know if I'm wrong here.


One of the biggest drawbacks of my libraries so far seems lack of accessible documentation & examples. There's one current & freely available use case of force directed layouts over here:

http://fidgen.googlecode.com/

There it's used to automatically create fiducial markers, but could be easily adapted for other types of graph data. The magic is in this file:

http://code.google.com/p/fidgen/source/browse/trunk/FidGen/Fiducial.pde

Instead of a normal VerletSpring2D this is making use of the VerletMinDistanceSpring2D class (also exists for 3D)

http://dev.postspectacular.com/docs/verletphysics/toxi/physics2d/VerletMinDistanceSpring2D.html

Hope that helps!
Back to top
 
postspectacular.com | toxi.co.uk
WWW  
lo-fi
Re: Graph layout for a large number of objects
Reply #5 - May 2nd, 2009, 2:24pm  
Walrus is very interesting but use hyperbolic space projected in 3D, if you can live with it.

You don't only need good simulation algorithms. I've seen a couple of fd-graphs running very large networks that were using a lot of OpenGl optimization, not only for the display but for the computing also. I can send you some articles and authors e-mails if you want.

I made some cute modifications of fd-graphs codes that i found using Traer lib, if that can give you other ideas:
biodesigninc.net/portfolio3

I'm interested in working with large graphs in my PH.D. thesis if you want me to help building a graph library for Processing.
Back to top
 
 
jeffg
Re: Graph layout for a large number of objects
Reply #6 - May 2nd, 2009, 3:10pm  
I've been able to represent a very large data set using processing (1,000,000).  I've even got 500,000 objects performing very well including textures using OpenGL.  Problem is the physics end - I can't compute the layout for any large graph in real time (or even in some reasonable loading timeframe).  I have yet to try toxi's verlet library, which may do the trick.  At the moment, I have to precompute all the positions in the graph.  I'm currently doing this with a python package called NetworkX, but I'd like to build it into processing.  I'm using JgraphT for my algorithms at the moment.  JUNG seemed to have some promise and I did get it imported into processing, but didn't spend the time to figure it out.  Those guys expect you to know java and I don't have the background to completely figure out how to word the syntax for Processing.  JUNG is also lacking in the 3d area and large graph layouts.  iGraph has some nice layout options and a python package, which may somehow be linked.  It would seem to make sense to build on and integrate one of these packages, but either way, I would love an easy library for graphs.  Traer's works pretty well on small stuff, but will not do what I'm looking to do with it.  I'll take a look at you examples and would be happy to get any information you have to make this happen.
Back to top
 
WWW  
lo-fi
Re: Graph layout for a large number of objects
Reply #7 - May 8th, 2009, 8:58am  
I made a 10 000 nodes graph based on http://rui-m.com/p5/particulas220000/ and on Toxi's verlet physics. I disabled VerletMinDistanceSpring2D between each node because the loading time was to high. I just kept a spring between each linked nodes. When it's loaded, it run smoothly.

Some to do's:
-The graph is rotating unless i write something to make it stop when it's in a near optimal layout (when the energy is minimal).
-There is a couple of way of adding repulsion between some element of the graph without having to set repulsion between all nodes.

http://www.biodesigninc.net/var/bigfdgraph/
Back to top
 
 
lo-fi
Re: Graph layout for a large number of objects
Reply #8 - May 8th, 2009, 1:48pm  
I made an update in 3D.
This ToxicLib is awesome.
http://www.biodesigninc.net/var/bigfdgraph2/
Back to top
 
 
toxi
Re: Graph layout for a large number of objects
Reply #9 - Jun 4th, 2009, 4:55pm  
Thank you sire! Smiley

Makes me ++happy to see it in action like that & am quite surprised about the performance myself... Applications like that were the main cause for me to build a system which allows custom spring types. That way you can build & optimize your spring behaviour independently and I don't have to worry about it... Wink
Back to top
 
postspectacular.com | toxi.co.uk
WWW  
cosmin
Re: Graph layout for a large number of objects
Reply #10 - Sep 21st, 2009, 11:57am  
I'm working on something similar and I need to make all the particles repel each other.

How can I achieve that, preferably without making springs between all the paricles? I couldn't find repulsion in Toxi's verlet library, but I'm not great with javadocs.
Back to top
 
http://10megatons.com
WWW  
jeffg
Re: Graph layout for a large number of objects
Reply #11 - Sep 21st, 2009, 12:03pm  
The Traer Physics library does a good job up to a couple thousand.  I ended up having to go to some unique measures to process a very large layout fast - using a 3d space filling curve.
Back to top
 
WWW  
cosmin
Re: Graph layout for a large number of objects
Reply #12 - Sep 21st, 2009, 2:06pm  
Yea, I put my sketch together using traer and it's good up to about 800 particles. screenshots
Now I want to convert it to toxi's verlet lib, seeing how it's much faster, and I got stuck not finding an obvious repulsion method.
Back to top
 
http://10megatons.com
WWW  
cosmin
Re: Graph layout for a large number of objects
Reply #13 - Sep 21st, 2009, 2:11pm  
space filling curve ...
That would be a 3d array that holds a sort of low res version of the "magnetic field" in every point ? (for a lack of a better explanation of my understanding)
Back to top
 
http://10megatons.com
WWW  
jeffg
Re: Graph layout for a large number of objects
Reply #14 - Sep 21st, 2009, 2:19pm  
See this paper from UCDavis
http://vis.cs.ucdavis.edu/~muelder/papers/2008-infovis-sfclayout-final.pdf

I'm doing a fast community analysis and then placing it on a 3d Hilbert curve, looks pretty good and it's blazing fast.  Can do 20,000 nodes in under a minute.  It's not as pretty as a spring layout but it's significantly faster.

http://www.math.uwaterloo.ca/~wgilbert/Research/HilbertCurve/HilbertCurve.html

They have another paper out that combines the two methods but I haven't tried it myself.
Back to top
 
WWW  
Pages: 1 2 
‹ Previous Topic | Next Topic ›