Hi!
Please give me ideas and hints on how to represent a dynamic tree of nodes in 3D.
The tree can have any number of nodes and each node’s purpose is to coalesce connections from and to other nodes. A node can have multiple arrows coming from and going to other nodes, in a sense it can have any number of parents and children. I’d need a way to visualize these without storing their coords anywhere, but instead calculating the coords on the fly, also not necessarily showing the full tree especially if it’s out of frustrum range.
Dynamic in the sense that I can add a parent or child to a node(while the tree is already being displayed in 3D ie. tree is live) and it has to show it and shift all necessary other nodes in view so that the new node can be shown. I imagine this can cause a wave of updates and I’m not sure if simply redisplaying(ie. clear and show from beginning) the entire tree is better or not.
I don’t know for now, how would I go about keeping the same space between nodes, and inserting a new one in between would have to basically shift probably most nodes in the tree (in 3D)
At the beginning I would have only one Node, and will have to being showing the tree from there, and I would dynamically find out it’s parents and children and try to represent them(ie. they are stored in a database), I can know the number of children and parents.
Are you asking for layout algorithms? Or just how to architect a jme application presuming you already have node positions?
For sure, don’t get too wrapped around trying to treat your data nodes like scene graph nodes. It is almost certainly better to batch the geometry for JME and otherwise do positioning and collision detection on your own data.
There are a variety of ways to layout graphs. Is it mostly tree? Are you using a standard graph API or something home-grown?
I have some pedigree in this area so it piqued my interest. 
i think i remember seeing something like a dynamic tree with nodes in this youtube video:
7 years of jMonkeyEngine History
although i dont think it was actually done with jME, it may help get you started.
@Decoy wow that video is amazing! thanks for that! Comments say it was done with Gource, I really like the plasticity of that tree!
@pspeed I don’t have the node positions, I guess I’m asking how do I find them? but I also don’t want to store them, so I guess it’s the layout algorithm that I’m asking for, like how do I position the children so they are evenly spaced, or before we get there how do they look like? circles? spheres? They don’t have any text with them but maybe I want to add some later on, then BillboardControl maybe? so the text faces the camera from any angle, maybe put the text inside the spheres. Should it be based on some kind of physics? (just like the one in that video seems to be). I like the idea of addition or removal of nodes not happening in 1 frame (but instead like in that video, sort of animated)
This is a project that I’ve decided to come back to, of which I’ve written something vague here, was under a different nick hehe:
http://hub.jmonkeyengine.org/groups/free-announcements/forum/topic/seeking-entity-for-team-programming-and-brainstorming-on-a-new-project/
But due to getting too deep into details, I’ve lost it, code was too heavy to keep on going (also wasn’t anything 3D yet), anyways I’m kinda simplifying the code and I’m thinking to go 3D so it’d be more fun for the subconscious to work on this xD
I gotta say I want something similar to that Gource video, sort of nice and fluffy (like natural camera/other movements as seen in that video) even though it’s just going to be a bunch of trees, they can eventually evolve to ie. show a plane representing a picture…
@pspeed: I’m not yet sure how I can batch and what, for sure I know what you speak of though;
I’m only using jme3 for now, but it’s mostly going to be trees like that.
I think I told you once inside Mythruna that I wanted to do something with many objects like that but it’s not going to be like Mythruna or Minecraft.
I basically want to define links, pointers, sets, lists and so on, from the ground up, such that the most elemental of them is the link (a tuple between two symbols). Basically I want to be able to define systems on top of other systems and if I want to understand any of them I can do so by parsing, without requiring any 3rd party information about any of the systems (self consistent?)
Here’s like two graphs(from what I’m working on) about how very simple trees would look like:
this is potentially for a domain set (set that can choose values only from a certain domain):
----
this is for an ordered list:
http://i.imgur.com/T5nP2.png
That video looks like it uses a pretty standard springer-embedder sort of algorithm… though it appears mostly 2D. The algorithm is the same in any case.
I thought I’d done some open source work in this area but I guess I never released anything. I have my own graph API (http://fgraph.org) but I guess I never published any visualization stuff. I do graph layouts in my day job, though.
[for this conversation I’m going to mix terms because I’m used to it. Nodes are the ‘nodes’ (sometimes called vertices but you see why that would be confusing) and ‘edges’ link them together… I’m used to ‘edges’.)
Anyway, the spring algorithm is pretty straight forward. The simplest version goes something like:
-keep a position and a force vector for each node.
- all nodes repulse all other nodes based on inverse square of distance and their mass. Add each force to the node’s force vector.
- all edges act like springs so use them to pull the nodes together as a linear function of their length, maybe multiplied by a weight if you want to get fancy. This results in equal forces added to each endpoint’s force vector.
- add the force vector to the node’s position, and reset the force vector to zero.
- goto (1).
In reality, that will create a fairly chaotic system for most graphs. It’s usually also a good idea to keep a ‘temperature’ for each node and keep track of the last force vector. You can use this to cool nodes down that are oscillating or orbiting. The temperature is basically a multiplier for the force application in step (3). (This is called ‘simulated annealing’ by the way.) You can also increase the temperature for things that are moving in straight lines which can help come to a ‘solution’ faster. The dot product against the previous frame’s force vector if your friend to detect all of those cases.
That all works for 2D or 3D but if you really don’t mind laying things out in 2D like in the video then there are a few open source packages that you can tap. JGraph being the first that comes to mind… though I don’t recall how isolated their layout code is.
In any case, a physics-based layout like described above will give you the animations like in the video automatically. Just place any new nodes close to their neighbors and they will repel away to where they should go.
that is some heavy stuff Obviously I’m not very smart (lol, and we all know what this actually means)
and I’ve no idea how I’d batch those so they don’t get a render called for each node, not to mention I’ve no idea how to implement that kind of physics. Not to mention that I probably only understand a fraction of what you’ve said…
I like that “edge” naming.
They definitely seem to be using that multiply by a weight in Gource, for edges, as you say in step 2.
That filament thingy, Filament - Getting Started , seems pretty cool. I understand there is no visualization for it…
Maybe this is too tough for me to even begin to go into it… I’m a little lost to be honest, I’ve also looked at some stuff like skyrails (youtube videos) which seems to be mostly like what I’m aiming for, in terms of visualization.
I’ll be rereading your post about 20 times and see what I can squeeze out of it, thank you!
re: Terminology there are two schools of naming, it seems to me.
- goes for the mathematically pure graph description where you have vertices that are connected by edges. In this respect, even a mesh can be thought of as a graph… which it technically is.
- goes for a more “link analysis”/“networking” description where you have nodes connected by links.
Some things like neo4j call the ‘links’ ‘relationships’… but man that’s a pain to type all the time.
In my own experience, “link” makes people think of all kinds of non-graphy things and “vertex” will just outright confuse everyone who isn’t steeped in the graph mathematics. Plus, I’ve been using a graph API called plexus forever (http://plexus.sf.net/) and it uses “nodes” and “edges”… so that’s what I adopted as well when I created filament.
re: Visualization, don’t get wrapped around performance in the beginning. If the layout math sounds tricky to you then start small and get that right just letting every node be a scene graph node. Even better, just prototype it in swing with Java2D and draw all of the nodes as boxes and links as lines. I’ve written so many of those little programs that I think I could do it in my sleep at this point.
…if I ever finish Mythruna maybe I’ll circle back and write a kick-butt graph visualization for JME. heheh. If and when.
I like Nodes and Edges, tho I’ve been using Nodes and Links(or Vectors even, to make sure order is implied in the pair). I’ve renamed stuff in my local code to Edges, but Nodes are kinda tricky they are just long identifiers at this point heh
For me (in my project) Nodes don’t mean anything, though I’ve named them for identification purposes(in the above pics) and I even 1-to-1 mapped a String to them but only for when coding in java these names are relevant (so I won’t have to resort to using longs).
It’s the edges that are important, but then again an edge wouldn’t really exist without the nodes, in the sense that the nodes need to be uniquely identifiable ie. by an Id (in my case a long), Anyway…
Vertex totally confuses me, so I pretend I didn’t hear it :))
I was contemplating on using your Filament with jme3 (and also read up on jme3’s physics on how to use forces at least). Though this means I’d have to learn how to use Filament… though I’m not even sure how to pull it in eclipse hmm…
On that Java2D and swing idea, it may be harder for me to do that than letting every node be a jme3 scene graph Node, I think. So I’ll probably not go that way(java2d/swing that is).
First, I’ll read up some on jme3’s physics and Controls, that would teach me how to apply a force at least
And I wonder what could I use for edge, a line? a Cylinder? maybe something 2D but still while in 3D and mixed with BillboardControl so it always faces the camera? And the Node would be a simple 3D sphere …
It would be rather awesome when you’ll do a JME visualization 
(and not just because I’d be inspired from your code xD but most likely because others would feel attracted to jme because of it)
(anyways, I’ll still be rereading your posts several times as I gather the necessary background to understand them)
Much appreciated!
The “drawing an edge” issue is why Swing would be easier… but it depends on what you are used to I guess.
I wouldn’t use JME’s physics for the layout. It’s using a rigid body physics engine that’s bringing a lot of stuff you won’t need into play. The graph layout is closer to what’s sometimes called a “mass aggregate” system. The nodes don’t have any size, just mass and repulsion.
It sounds much trickier than it is. I’ll see if I can find a code sample somewhere.
Sounds like all I need to use is Control ? or maybe the global Control that is application states
to implement this partial physics that you speak of, I mean I wouldn’t know of another way to do it.
But as to how this physics would work, I don’t know yet (I’ll have to reread your posts and see what I can understand again)
I check out some texts about “mass aggregate” system, seems that even the rigid body physics is based on it…
Btw, don’t nodes need some kind of (an additional) force of attraction? I think I read somewhere saying that …, and thus I deduce that adding this may not require that temperature maybe, tho with temperature is probably less computationally intensive?(and I’m not even understanding that temperature fully)
The only thing that I did with swing is showing a Tree in a JFrame or something like that, and never used Java2D, so basically I’d have 0 ideas where to begin with swing, that’s why jme3 seemed better and since it’s also the end-target seems ok to go jme3.
I did pull that skyrails dist and I like the smoothness of camera movements and how their trees slowly expand, as if that “physics” is still working on it to spatialize it more,
If you cannot find a code sample somewhere then it’s ok, these talks are helping a lot actually.
Would you go about doing this physics system via app states or Controls? or somehow else? (I only ever used Controls and BillboardControl even)
In JME, I hadn’t thought deeply about how. The layout code should run on a separate thread but it can queue up a Callable to the JME render thread to “apply the position changes”. So whenever a layout iteration is done, you enqueue a Callable and wait for it. The Callable then applies each of the node positions to the JME nodes. I suppose you could do it as a control.
Mass aggregate systems usually don’t deal with rotation. Just fixed orientation 0-size point masses and springs, rods, etc. to hold them together. Rigid body physics has rotational momentum, tensor matrices, all kinds of tricky stuff.
The nodes don’t need to self-attract because the edges will hold them together. Even the repulsion eventually wears off with distance so isolated parts of the graph will never be too far away. I usually add some gravity to keep things centered around the origin.
I’m attaching some code but it’s pretty thread bare and the math is a little… messy. I had a filament graph that I wanted to quickly look at so I hand-rolled a visualization for it… this was probably a year ago or so. It doesn’t have simulated annealing at all so I’ve hard-coded an energy that is applied to all nodes and the edge weighting is also constant. But hopefully it illustrates what I’m talking about… I’ll also include the swing code so you can see what I mean about rendering.
Also, ignore my odd bracing style…
Here is the SpringLayout.java file:
[java]
/*
- $Id$
*
- Copyright © 2010, Paul Speed
- All rights reserved.
*
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
*
-
- Redistributions of source code must retain the above copyright notice,
- Redistributions of source code must retain the above copyright notice,
- this list of conditions and the following disclaimer.
-
- Redistributions in binary form must reproduce the above copyright
- Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-
- Neither the names "Progeeks", "Meta-JB", nor the names of its contributors
- Neither the names "Progeeks", "Meta-JB", nor the names of its contributors
- may be used to endorse or promote products derived from this software
- without specific prior written permission.
*
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
- LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- POSSIBILITY OF SUCH DAMAGE.
/
package org.fgraph.vis;
import java.util.;
import org.fgraph.*;
/**
*
-
@version $Revision$
-
@author Paul Speed
*/
public class SpringLayout
{
private FGraph graph;
private LayoutNode[] nodes;
private LayoutEdge[] edges;
private double gravityFactor = 0.01;
private SpringLayout( FGraph graph )
{
setup(graph);
}
protected LayoutNode cacheNode( Node n, Map<Node, LayoutNode> nodeMap )
{
LayoutNode ln = nodeMap.get(n);
if( ln == null )
{
ln = new LayoutNode( n );
nodeMap.put( n, ln );
}
return ln;
}
protected void setup( FGraph graph )
{
// For now we limit the results
//int nodeCount = graph.nodes().size();
//nodeCount = Math.min( 100, nodeCount );
int nodeCount = 100;
List<LayoutEdge> edgeList = new ArrayList<LayoutEdge>();
//List<Edge> edgeList = new ArrayList<Edge>();
Map<Node, LayoutNode> nodeMap = new HashMap<Node,LayoutNode>();
Set<Edge> visited = new HashSet<Edge>();
int index = 0;
for( Node n : graph.nodes() )
{
System.out.println( “index:” + index );
LayoutNode ln = cacheNode( n, nodeMap );
System.out.println( “Getting edges…” );
System.out.println( " degree:" + n.edges().size() );
// Since we limited the nodes we’re retrieving we need
// to also force cache the endpoints of the edges
// we’re adding
for( Edge e : n.edges() )
{
if( !visited.add(e) )
continue;
LayoutNode other = cacheNode( e.otherEnd(n), nodeMap );
LayoutEdge le;
if( n == e.getTail() )
le = new LayoutEdge( ln, other, e );
else
le = new LayoutEdge( other, ln, e );
edgeList.add( le );
}
if( index++ >= nodeCount )
break;
}
System.out.println( “layout node count:” + nodeMap.values().size() );
System.out.println( “layout edge count:” + edgeList.size() );
nodes = nodeMap.values().toArray( new LayoutNode[nodeMap.values().size()] );
edges = edgeList.toArray( new LayoutEdge[edgeList.size()] );
}
public static SpringLayout createLayout( FGraph graph )
{
return new SpringLayout(graph);
}
public LayoutNode[] nodes()
{
return nodes;
}
public LayoutEdge[] edges()
{
return edges;
}
protected void applyForce( LayoutNode n1, LayoutNode n2 )
{
double dx = n2.x - n1.x;
double dy = n2.y - n1.y;
double scale;
if( dx == 0 && dy == 0 )
{
// Infinite push, technically. We’ll give
// each point a small nudge in a random direction
scale = 0.1;
double randomRads = Math.random() * Math.PI * 2.0;
dx = Math.cos( randomRads );
dy = Math.sin( randomRads );
}
else
{
double dSq = dx * dx + dy * dy;
scale = (1.0 * n1.mass * n2.mass) / dSq;
}
dx *= scale;
dy *= scale;
n1.xDelta -= dx;
n1.yDelta -= dy;
n2.xDelta += dx;
n2.xDelta += dy;
}
protected void applyGravity( LayoutNode n )
{
double gravityScale = gravityFactor * n.mass;
n.xDelta -= n.x * gravityScale;
n.yDelta -= n.y * gravityScale;
}
protected void applySpring( LayoutEdge e )
{
LayoutNode n1 = e.tail;
LayoutNode n2 = e.head;
double dx = n2.x - n1.x;
double dy = n2.y - n1.y;
double strength = 0.1;
dx *= strength;
dy = strength;
n1.xDelta += dx;
n1.yDelta += dy;
n2.xDelta -= dx;
n2.yDelta -= dy;
}
public void doLayout()
{
for( int i = 0; i < nodes.length; i++ )
{
LayoutNode n1 = nodes;
for( int j = 0; j < i; j++ )
{
LayoutNode n2 = nodes[j];
if( n1 == n2 )
continue;
applyForce( n1, n2 );
}
applyGravity( n1 );
}
for( int i = 0; i < edges.length; i++ )
{
applySpring( edges );
}
// Now just cook in the deltas
double energy = 0.5;
for( int i = 0; i < nodes.length; i++ )
{
LayoutNode n = nodes;
n.x += n.xDelta * energy;
n.y += n.yDelta * energy;
n.xDelta = 0;
n.yDelta = 0;
}
}
public static class LayoutNode
{
public Node node;
public double x;
public double y;
public double xDelta;
public double yDelta;
public double mass = 1.0;
public LayoutNode( Node node )
{
this.node = node;
this.x = Math.random() * 800 - 400;
this.y = Math.random() * 600 - 300;
}
}
public static class LayoutEdge
{
public LayoutNode tail;
public LayoutNode head;
public Edge edge;
public LayoutEdge( LayoutNode tail, LayoutNode head, Edge e )
{
this.tail = tail;
this.head = head;
this.edge = e;
}
}
}
[/java]
And this is the simple swing app that calls it: (Don’t get to hung up in the fgraph setup… hopefully the code is readable around that.)
[java]
/
- $Id$
*
- Copyright © 2010, Paul Speed
- All rights reserved.
*
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
*
-
- Redistributions of source code must retain the above copyright notice,
- Redistributions of source code must retain the above copyright notice,
- this list of conditions and the following disclaimer.
-
- Redistributions in binary form must reproduce the above copyright
- Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-
- Neither the names "Progeeks", "Meta-JB", nor the names of its contributors
- Neither the names "Progeeks", "Meta-JB", nor the names of its contributors
- may be used to endorse or promote products derived from this software
- without specific prior written permission.
*
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
- LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- POSSIBILITY OF SUCH DAMAGE.
/
package org.fgraph.vis;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.sql.;
import java.util.;
import javax.swing.;
import org.progeeks.util.log.Log;
import org.fgraph.*;
import org.fgraph.base.DefaultGraph;
import org.fgraph.sql.SqlStoreFactory;
import org.fgraph.util.JdbcConnections;
import org.fgraph.vis.SpringLayout.LayoutNode;
import org.fgraph.vis.SpringLayout.LayoutEdge;
/**
- A test bootstrapper for testing the graph visualization
- components.
*
-
@version $Revision$
- @author Paul Speed
*/
public class Test extends JFrame
{
static Log log = Log.getLog();
private FGraph graph;
private SpringLayout layout;
private RenderPanel renderPanel = new RenderPanel();
private RenderThread renderThread = new RenderThread();
public Test( FGraph graph )
{
super( "FGraph Visualization Test" );
this.graph = graph;
setDefaultCloseOperation( DISPOSE_ON_CLOSE );
setSize( 800, 600 );
getContentPane().add( renderPanel, "Center" );
this.layout = SpringLayout.createLayout(graph);
renderThread.start();
}
public static void main( String… args ) throws Exception
{
Log.initialize();
if( args == null || args.length == 0 )
{
System.out.println( "Usage: GraphUsageDemo <jdbc info> <user> <password> [commands…]" );
return;
}
// Try to use the system look and feel.
try
{
UIManager.setLookAndFeel( UIManager.getSystemLookAndFeelClassName() );
}
catch( Exception e )
{
log.warn( "Error setting system look and feel.", e );
}
List<String> argList = new ArrayList<String>( Arrays.asList(args) );
Connection conn = JdbcConnections.getConnection(argList);
conn.setAutoCommit(false);
FGraph g = DefaultGraph.create( new SqlStoreFactory(conn) );
Test test = new Test( g );
test.setVisible( true );
}
private class RenderPanel extends JPanel
{
public void paint( Graphics g )
{
synchronized( layout )
{
int w = getWidth();
int h = getHeight();
g.clearRect( 0, 0, w, h );
g.translate( w / 2, h / 2 );
((Graphics2D)g).scale( 2.0, 2.0 );
g.setColor( Color.red );
for( LayoutNode n : layout.nodes() )
{
g.drawRect( (int)n.x - 2, (int)n.y - 2, 4, 4 );
}
g.setColor( Color.blue );
for( LayoutEdge e : layout.edges() )
{
g.drawLine( (int)e.tail.x, (int)e.tail.y, (int)e.head.x, (int)e.head.y );
}
}
}
}
private class RenderThread extends Thread
{
public RenderThread()
{
setDaemon( true );
}
public void run()
{
while( true )
{
synchronized( layout )
{
layout.doLayout();
}
renderPanel.repaint();
try
{
Thread.sleep( 100 );
}
catch( InterruptedException e )
{
e.printStackTrace();
}
}
}
}
}
[/java]
…though I will say… if the forum is going to eat up all of the whitespace anyway, maybe my bracing style isn’t so bad after all.
pspeed said:
maybe my bracing style isn't so bad after all. ;)
aaarrrgghhhh I'm meltiiiiing
:p
nehon said:
aaarrrgghhhh I'm meltiiiiing
:p
lol that reminded me of that game Nox (i think, unless the sound is in Majesty)
btw, I'm still trying to figure this out, though I failed to compile it and run it due to:
Exception in thread "main" java.lang.NoClassDefFoundError: org/apache/log4j/Appender
at org.fgraph.util.JdbcConnections.(JdbcConnections.java:55)
at org.some.Test.main(Test.java:91)
Caused by: java.lang.ClassNotFoundException: org.apache.log4j.Appender
at java.net.URLClassLoader$1.run(URLClassLoader.java:366)
at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
at java.lang.ClassLoader.loadClass(ClassLoader.java:423)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
at java.lang.ClassLoader.loadClass(ClassLoader.java:356)
... 2 more so I will try to add my own code to give it the graph data, else I will just try and read the code and make sense of it, it does seem simple, except the math :) but I kinda want to see it working first, then understand it heh
EDIT: I eventually added apache-log4j-1.2.16
but now I get:
Exception in thread "main" java.lang.NoClassDefFoundError: org/progeeks/util/TypeTransformer
at org.some2.Test.main(Test.java:96)
Caused by: java.lang.ClassNotFoundException: org.progeeks.util.TypeTransformer
at java.net.URLClassLoader$1.run(URLClassLoader.java:366)
at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
at java.lang.ClassLoader.loadClass(ClassLoader.java:423)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
at java.lang.ClassLoader.loadClass(ClassLoader.java:356)
... 1 more
oh yeah I forgot to say, that my graph cannot supply all Nodes and/or all edges in the graph, it can only identify a Node if you already know it’s ID and then know how many edges it has and each of that edges’ Nodes…
the code seems to need all nodes, and caches them as LayoutNode[], I’ll see what I can work around this and maybe drop the cache(?) and only process that node if it’s in view or something, so I wouldn’t have to pull all Nodes of the graph (imagine half a million xD)
The code requires log4j… among probably a few other things that would have also been dependencies in the fgraph poms.
You will want the cache, trust me. It gets iterated over thousands and thousands of times to do the layout.
…you just need to dynamically add things to it as you ‘discover’ more parts of the graph. So you could, for example, keep a list that you add things to and then if that list has changed since the list loop iteration, rebuild the arrays or something.
Oh, and I only provided that as a sample. I fully expected you to supply your own graph data. I have to leave some stuff for you to do, after all.
roger that, and it is much appreciated! I will try the
FGraph g = DefaultGraph.create( HashTripleStore.FACTORY );
(in memory)way, and leave the cache on and supply some data, and also see what other requirements are needed to make Filament work (aside from guava and meta-jb and log4j)
I can probably understand the code if I just read it, but I really want to see it working xD and then understand it. It seems to have a more impressionable effect that way.
Hooray, finally I made it work I need to buy a neew brain
when it begins it looks like this:
—
but after like 5-10 seconds looks like this (so tightly packed):
http://i.imgur.com/34zEt.png
anyway the code (in one file) is this:
[java]/*
- $Id$
*
- Copyright © 2010, Paul Speed
- All rights reserved.
*
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
*
-
- Redistributions of source code must retain the above copyright notice,
- Redistributions of source code must retain the above copyright notice,
- this list of conditions and the following disclaimer.
-
- Redistributions in binary form must reproduce the above copyright
- Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-
- Neither the names "Progeeks", "Meta-JB", nor the names of its contributors
- Neither the names "Progeeks", "Meta-JB", nor the names of its contributors
- may be used to endorse or promote products derived from this software
- without specific prior written permission.
*
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
- LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- POSSIBILITY OF SUCH DAMAGE.
/
package org.some3;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.util.;
import javax.swing.;
import org.progeeks.util.log.Log;
import org.some3.Test2.SpringLayout.LayoutEdge;
import org.some3.Test2.SpringLayout.LayoutNode;
import org.fgraph.;
import org.fgraph.base.DefaultGraph;
import org.fgraph.tstore.mem.HashTripleStore;
/**
- A test bootstrapper for testing the graph visualization
- components.
*
-
@version $Revision$
-
@author Paul Speed
*/
public class Test2 extends JFrame {
/
*
*/
private static final long serialVersionUID = 8550468491354320547L;
static Log log = Log.getLog();
private SpringLayout layout;
@SuppressWarnings( "synthetic-access" )
private RenderPanel renderPanel = new RenderPanel();
private RenderThread renderThread = new RenderThread();
public Test2( FGraph graph1 ) {
super( "FGraph Visualization Test" );
setDefaultCloseOperation( DISPOSE_ON_CLOSE );
setSize( 800, 600 );
getContentPane().add( renderPanel, "Center" );
this.layout = new SpringLayout( graph1 );
renderThread.start();
}
public static void main( String… args ) throws Exception {
Log.initialize();
// Try to use the system look and feel.
try {
UIManager.setLookAndFeel( UIManager.getSystemLookAndFeelClassName() );
} catch ( Exception e ) {
log.warn( "Error setting system look and feel.", e );
}
FGraph g = DefaultGraph.create( HashTripleStore.FACTORY );
Node allDomainsInADSets = g.newNode();
Node allDomainSets = g.newNode();
Node AllPtr2Set = g.newNode();
Node set2 = g.newNode();
Node set1 = g.newNode();
Node domain2Unique = g.newNode();
Node domain1Unique = g.newNode();
Node set1Unique = g.newNode();
Node set2Unique = g.newNode();
Node A = g.newNode();
Node C = g.newNode();
Node D = g.newNode();
Node E = g.newNode();
Node F = g.newNode();
Node H = g.newNode();
Node B = g.newNode();
g.addEdge( allDomainsInADSets, domain1Unique, "domain1" );
g.addEdge( allDomainsInADSets, domain2Unique, "domain2" );
g.addEdge( allDomainSets, set1, "set1" );
g.addEdge( allDomainSets, set2, "set2" );
g.addEdge( AllPtr2Set, set1Unique, "" );
g.addEdge( AllPtr2Set, set2Unique, "" );
g.addEdge( set1, domain1Unique,"");
g.addEdge( set1, set1Unique,"");
g.addEdge( set2, domain2Unique,"");
g.addEdge( set2, set2Unique,"");
g.addEdge( domain2Unique, A,"");
g.addEdge( set1Unique, A,"");
g.addEdge( domain1Unique, C,"");
g.addEdge( set2Unique, D,"");
g.addEdge( A, H,"");
g.addEdge( A, B,"");
g.addEdge( A, E,"");
g.addEdge( D, E,"");
g.addEdge( D, B,"");
g.addEdge( C, F,"");
g.addEdge( C, B,"");
g.addEdge( C, D,"");
g.addEdge( C, E,"");
g.addEdge( C, H,"");
Test2 test = new Test2( g );
test.setVisible( true );
}
private class RenderPanel extends JPanel {
/
*
*/
private static final long serialVersionUID = 7796645710560850386L;
@SuppressWarnings( "synthetic-access" )
@Override
public void paint( Graphics g ) {
synchronized ( layout ) {
int w = getWidth();
int h = getHeight();
g.clearRect( 0, 0, w, h );
g.translate( w / 2, h / 2 );
( (Graphics2D)g ).scale( 2.0, 2.0 );
g.setColor( Color.red );
for ( LayoutNode n : layout.nodes() ) {
g.drawRect( (int)n.x - 2, (int)n.y - 2, 4, 4 );
}
g.setColor( Color.blue );
for ( LayoutEdge e : layout.edges() ) {
g.drawLine( (int)e.tail.x, (int)e.tail.y, (int)e.head.x, (int)e.head.y );
}
}
}
}
private class RenderThread extends Thread {
public RenderThread() {
setDaemon( true );
}
@SuppressWarnings( "synthetic-access" )
@Override
public void run() {
while ( true ) {
synchronized ( layout ) {
layout.doLayout();
}
renderPanel.repaint();
try {
Thread.sleep( 100 );
} catch ( InterruptedException e ) {
e.printStackTrace();
}
}
}
}
/**
*
-
@version $Revision$
-
@author Paul Speed
*/
public class SpringLayout {
private LayoutNode[] nodes;
private LayoutEdge[] edges;
private double gravityFactor = 0.01;
SpringLayout( FGraph graph ) {
setup( graph );
}
protected LayoutNode cacheNode( Node n, Map<Node, LayoutNode> nodeMap ) {
LayoutNode ln = nodeMap.get( n );
if ( ln == null ) {
ln = new LayoutNode( n );
nodeMap.put( n, ln );
}
return ln;
}
protected void setup( FGraph graph ) {
// For now we limit the results
// int nodeCount = graph.nodes().size();
// nodeCount = Math.min( 100, nodeCount );
int nodeCount = 100;
List<LayoutEdge> edgeList = new ArrayList<LayoutEdge>();
// List<Edge> edgeList = new ArrayList<Edge>();
Map<Node, LayoutNode> nodeMap = new HashMap<Node, LayoutNode>();
Set<Edge> visited = new HashSet<Edge>();
int index = 0;
for ( Node n : graph.nodes() ) {
System.out.println( “index:” + index );
LayoutNode ln = cacheNode( n, nodeMap );
System.out.println( “Getting edges…” );
System.out.println( " degree:" + n.edges().size() );
// Since we limited the nodes we’re retrieving we need
// to also force cache the endpoints of the edges
// we’re adding
for ( Edge e : n.edges() ) {
if ( !visited.add( e ) )
continue;
LayoutNode other = cacheNode( e.otherEnd( n ), nodeMap );
LayoutEdge le;
if ( n == e.getTail() )
le = new LayoutEdge( ln, other, e );
else
le = new LayoutEdge( other, ln, e );
edgeList.add( le );
}
if ( index++ >= nodeCount )
break;
}
System.out.println( “layout node count:” + nodeMap.values().size() );
System.out.println( “layout edge count:” + edgeList.size() );
nodes = nodeMap.values().toArray( new LayoutNode[nodeMap.values().size()] );
edges = edgeList.toArray( new LayoutEdge[edgeList.size()] );
}
public LayoutNode[] nodes() {
return nodes;
}
public LayoutEdge[] edges() {
return edges;
}
protected void applyForce( LayoutNode n1, LayoutNode n2 ) {
double dx = n2.x - n1.x;
double dy = n2.y - n1.y;
double scale;
if ( dx == 0 && dy == 0 ) {
// Infinite push, technically. We’ll give
// each point a small nudge in a random direction
scale = 0.1;
double randomRads = Math.random() * Math.PI * 2.0;
dx = Math.cos( randomRads );
dy = Math.sin( randomRads );
} else {
double dSq = dx * dx + dy * dy;
scale = ( 1.0 * n1.mass * n2.mass ) / dSq;
}
dx *= scale;
dy *= scale;
n1.xDelta -= dx;
n1.yDelta -= dy;
n2.xDelta += dx;
n2.xDelta += dy;
}
protected void applyGravity( LayoutNode n ) {
double gravityScale = gravityFactor * n.mass;
n.xDelta -= n.x * gravityScale;
n.yDelta -= n.y * gravityScale;
}
protected void applySpring( LayoutEdge e ) {
LayoutNode n1 = e.tail;
LayoutNode n2 = e.head;
double dx = n2.x - n1.x;
double dy = n2.y - n1.y;
double strength = 0.1;
dx *= strength;
dy *= strength;
n1.xDelta += dx;
n1.yDelta += dy;
n2.xDelta -= dx;
n2.yDelta -= dy;
}
public void doLayout() {
for ( int i = 0; i < nodes.length; i++ ) {
LayoutNode n1 = nodes;
for ( int j = 0; j < i; j++ ) {
LayoutNode n2 = nodes[j];
if ( n1 == n2 )
continue;
applyForce( n1, n2 );
}
applyGravity( n1 );
}
for ( int i = 0; i < edges.length; i++ ) {
applySpring( edges );
}
// Now just cook in the deltas
double energy = 0.5;
for ( int i = 0; i < nodes.length; i++ ) {
LayoutNode n = nodes;
n.x += n.xDelta * energy;
n.y += n.yDelta * energy;
n.xDelta = 0;
n.yDelta = 0;
}
}
public class LayoutNode {
public Node node;
public double x;
public double y;
public double xDelta;
public double yDelta;
public double mass = 1.0;
public LayoutNode( Node node1 ) {
this.node = node1;
this.x = Math.random() * 800 - 400;
this.y = Math.random() * 600 - 300;
}
}
public class LayoutEdge {
public LayoutNode tail;
public LayoutNode head;
public Edge edge;
public LayoutEdge( LayoutNode tail1, LayoutNode head1, Edge e ) {
this.tail = tail1;
this.head = head1;
this.edge = e;
}
}
}
}
[/java]
This is the kind of place where endless tweaking begins.
You can increase the 1.0 in the scale calculation and the nodes will repel more. You can also lessen the effect of gravity. Or you can weaken the strength of the springs. One of those may help.
Normally you’d be able to zoom in on the data and so the tightness might matter. I don’t remember in what state I left the values when I stopped playing with this code but my graph was many thousands of nodes, so I’m sure the values are tweaked for that.