Page 1 of 2
Graphoon (Now with online demo)
Posted: Thu Jan 14, 2016 1:50 am
by 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.
Re: Graphoon
Posted: Fri Jan 15, 2016 12:05 pm
by riidom
Looks awesome, you just wiped out the main reason why I didnt start to check out this 4X-idea I am having
Re: Graphoon
Posted: Fri Jan 15, 2016 12:30 pm
by rmcode
riidom wrote: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.
Re: Graphoon
Posted: Fri Jan 15, 2016 3:56 pm
by Katamori
Holy shit, it's beautiful!
Was it as painful to create as painful I think it was?
Re: Graphoon
Posted: Fri Jan 15, 2016 4:55 pm
by rmcode
Katamori wrote: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
Re: Graphoon
Posted: Fri Jan 15, 2016 9:05 pm
by Xugro
rmcode wrote: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.
Re: Graphoon
Posted: Sun Jan 17, 2016 12:48 pm
by rmcode
Xugro wrote:rmcode wrote: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).
Re: Graphoon (Now with online demo)
Posted: Mon Feb 08, 2016 7:17 pm
by rmcode
Added an online demo (using love.js):
http://rm-code.github.io/Graphoon/
Re: Graphoon (Now with online demo)
Posted: Thu Feb 11, 2016 5:22 pm
by 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.
Re: Graphoon (Now with online demo)
Posted: Thu Feb 11, 2016 6:32 pm
by 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.