Graphoon (Now with online demo)

[rmcode]

A force directed graph algorithm written in Lua.



Graphoon emerged from the graph calculation code used in both LoGiVi and LoFiVi.

A force directed graph layout is achieved by simulating physical forces, which push and pull each node in the graph until a nice layout is found.

The code lives on github.

A demo .love can be found here (requires LÖVE 0.10.0).

The same demo can also be found online here.

[riidom]

Looks awesome, you just wiped out the main reason why I didnt start to check out this 4X-idea I am having

[rmcode]

Looks awesome, you just wiped out the main reason why I didnt start to check out this 4X-idea I am having

Thank you

I'm always open for suggestions.

[Katamori]

Holy shit, it's beautiful!

Was it as painful to create as painful I think it was?

[rmcode]

Was it as painful to create as painful I think it was?

I wouldn't call it painful. I learned a lot while working on the graph code, but it definitely took some time

It's not perfect either: First of all the runtime increases exponentially with each added node (I have an idea how to break it down using a spatial index, but haven't tried implementing one yet) and there still are some cases where the graph will "explode" or not form a nice layout.

All in all I am quite happy with the current version though

[Xugro]

It's not perfect either: First of all the runtime increases exponentially with each added node (I have an idea how to break it down using a spatial index, but haven't tried implementing one yet) and there still are some cases where the graph will "explode" or not form a nice layout.

I have the same problems, but I did not work any further on my code (see attachment).

What could work is using a global potential of all nodes instead of using forces between each node-pair. But thats something I have not tried.

[rmcode]

It's not perfect either: First of all the runtime increases exponentially with each added node (I have an idea how to break it down using a spatial index, but haven't tried implementing one yet) and there still are some cases where the graph will "explode" or not form a nice layout.

I have the same problems, but I did not work any further on my code (see attachment).

What could work is using a global potential of all nodes instead of using forces between each node-pair. But thats something I have not tried.

Hehe when I started messing around with this whole force-directed layout stuff I wrote a program quite similar to yours. It basically attracts all nodes towards the center and adds repulsion forces between them (so no extra attraction force between connected nodes).

I then started connecting nodes at random, but it quickly turned out that with a global attraction point the nodes won't get close to the nodes they are connected to, which leads to a messy layout. It's because of the attraction forces between connected nodes that a nice layout is formed (aka connected nodes are close to each other).

One idea I wanted to try out uses a spatial index. You could iterate over all edges and attract nodes along their connections regardless of where they are, but use a quadtree to only repel nodes which are close to each other. Depending on the distance between nodes, a lot of the repulsion forces are small enough to be negligible. (I actually tried this with LoGiVi about a year ago, but didn't manage to get a nice layout: https://twitter.com/rm_code/status/579957755613745152).

[rmcode]

Added an online demo (using love.js): http://rm-code.github.io/Graphoon/

[Ref]

Thought I might have an application so diddled with the code.
Your comment:

Code: Select all

DISCLAIMER: Don't scroll down if you can't stand ugly code.

Don't mind ugly code (produce a lot of it myself) but semicolons - UG!
Moved all of the constants up front for easy adjustments (rather than having them distributed in the modules).

Code: Select all

-- ------------------------------------------------
-- Constants
-- ------------------------------------------------

local color = {
	background = { 204, 224, 232 },
	node		 = { 130, 190, 238 },
	edge		 = { 100, 100, 100 },
	text		= {  30, 100, 256 },
	cursor	= { 234, 49,  110 }
	}

local sprite	= { image = love.graphics.newImage( 'file.png' ), size = 16 }
	sprite.ht	= sprite.image:getHeight()
	sprite.scale= sprite.size/sprite.ht
	sprite.offset= sprite.ht/2

force = { spring = 0.005, change  = 20,   max  = 4 }
param = { speed  = 128,   damping = 0.95, mass = 3 }

local data		= { sets = { 'GraphoonData', 'program', 'EvilDead' }, selected = 1 }
local screen	= { wd = 1200, ht = 700 }

and added ability to switch data sets on the fly ('N' key).
Conclusion: Very interesting but really don't know what to do with it.

[Ref]

Really surprised as to how easy it was to add rotation (just press 'R')
Really a neat script.
Good job.
Edit: My bad! Forgot to include the license!
Reloaded love with license.