Add experimental (slow) force-directed graph layout to Ganv.

This continuously arranges the graph, and the user can drag around nodes to
influence the layout which is handy.

To try, configure with --no-graphviz --fdgl.

Still rough around the edges, in particular detached nodes will fly off into
space.  Also entirely too slow for production use, will need a more
sophisticated data structure for that, so the repel calculation isn't O(n^2).


git-svn-id: http://svn.drobilla.net/lad/trunk/ganv@5177 a436a847-0d15-0410-975c-d299462d15a1

3 files changed, 138 insertions, 0 deletions

diff --git a/src/Canvas.cpp b/src/Canvas.cpp
index 7111e1a..bcb4dd1 100644
--- a/src/Canvas.cpp
+++ b/src/Canvas.cpp
@@ -49,6 +49,9 @@
 #ifdef HAVE_AGRAPH
 #    include <gvc.h>
 #endif
+#ifdef GANV_FDGL
+#    include "./fdgl.hpp"
+#endif
 
 static guint signal_connect;
 static guint signal_disconnect;
@@ -145,6 +148,13 @@ struct GanvCanvasImpl {
 		g_signal_connect(G_OBJECT(ganv_canvas_base_root(GANV_CANVAS_BASE(_gcanvas))),
 		                 "event", G_CALLBACK(on_canvas_event), this);
 
+#ifdef GANV_FDGL
+		g_timeout_add_full(G_PRIORITY_DEFAULT_IDLE,
+		                   100,
+		                   on_timeout,
+		                   this,
+		                   NULL);
+#endif
 	}
 
 	~GanvCanvasImpl()
@@ -160,6 +170,16 @@ struct GanvCanvasImpl {
 		return ((GanvCanvasImpl*)impl)->on_event(ev);
 	}
 
+#ifdef GANV_FDGL
+	static gboolean
+	on_timeout(gpointer impl)
+	{
+		return ((GanvCanvasImpl*)impl)->layout_iteration();
+	}	
+
+	gboolean layout_iteration();
+#endif
+
 	GanvItem* root() {
 		return ganv_canvas_base_root(GANV_CANVAS_BASE(_gcanvas));
 	}
@@ -686,6 +706,110 @@ GanvCanvasImpl::layout_dot(const std::string& filename)
 }
 #endif
 
+#ifdef GANV_FDGL
+
+static void
+get_pos_area(const GanvNode* node, Vector* pos, Vector* area)
+{
+	double x1, y1, x2, y2;
+	ganv_item_get_bounds(GANV_ITEM(node), &x1, &y1, &x2, &y2);
+
+	area->x = x2 - x1;
+	area->y = y2 - y1;
+	pos->x  = x1 + (area->x / 2.0);
+	pos->y  = y1 + (area->y / 2.0);
+
+	ganv_item_i2w(GANV_ITEM(node), &pos->x, &pos->y);
+}
+
+gboolean
+GanvCanvasImpl::layout_iteration()
+{
+	// Calculate repelling forces between nodes
+	FOREACH_ITEM(_items, i) {
+		if (!GANV_IS_MODULE(*i) && !GANV_IS_CIRCLE(*i)) {
+			continue;
+		}
+
+		GanvNode* const node = GANV_NODE(*i);
+		Vector          pos;
+		Vector          area;
+		get_pos_area(node, &pos, &area);
+
+		FOREACH_ITEM(_items, j) {
+			if (i == j || !GANV_IS_NODE(*j)) {
+				continue;
+			}
+
+			GanvNode* const node2 = GANV_NODE(*j);
+			Vector          pos2;
+			Vector          area2;
+			get_pos_area(node2, &pos2, &area2);
+
+			const Vector f = repel_force(pos, area, pos2, area2);
+
+			node->impl->force  = vec_add(node->impl->force, f);
+			node2->impl->force = vec_add(node2->impl->force, vec_mult(f, -1.0));
+		}
+	}
+
+	// Calculate attractive spring forces for edges
+	FOREACH_EDGE(_edges, i) {
+		const GanvEdge* const edge = *i;
+		GanvNode*             tail = ganv_edge_get_tail(edge);
+		GanvNode*             head = ganv_edge_get_head(edge);
+		if (GANV_IS_PORT(tail)) {
+			tail = GANV_NODE(ganv_port_get_module(GANV_PORT(tail)));
+		}
+		if (GANV_IS_PORT(head)) {
+			head = GANV_NODE(ganv_port_get_module(GANV_PORT(head)));
+		}
+		if (tail == head) {
+			continue;
+		}
+
+		const Vector tail_pos = { edge->impl->coords.x1, edge->impl->coords.y1 };
+		const Vector head_pos = { edge->impl->coords.x2, edge->impl->coords.y2 };
+		const Vector f        = spring_force(head_pos, tail_pos);
+
+		tail->impl->force = vec_add(tail->impl->force, f);
+		head->impl->force = vec_add(head->impl->force, vec_mult(f, -1.0));
+	}
+
+	// Update positions based on calculated forces
+	FOREACH_ITEM(_items, i) {
+		if (!GANV_IS_MODULE(*i) && !GANV_IS_CIRCLE(*i)) {
+			continue;
+		}
+
+		GanvNode* const node = GANV_NODE(*i);
+
+		static const float dur  = 0.1;  // Time duration
+		static const float damp = 0.5;  // Velocity damping (momentum loss)
+
+		if (node->impl->grabbed) {
+			node->impl->vel.x = 0.0;
+			node->impl->vel.y = 0.0;
+		} else {
+			node->impl->vel = vec_add(node->impl->vel,
+			                          vec_mult(node->impl->force, dur));
+			node->impl->vel = vec_mult(node->impl->vel, damp);
+
+			// Update position
+			const Vector dpos = vec_mult(node->impl->vel, dur);
+			ganv_node_move(node, dpos.x, dpos.y);
+		}
+
+		// Reset forces for next time
+		node->impl->force.x = 0.0;
+		node->impl->force.y = 0.0;
+	}
+
+	return TRUE;
+}
+
+#endif // GANV_FDGL
+
 void
 GanvCanvasImpl::remove_edge(GanvEdge* edge)
 {
diff --git a/src/ganv-private.h b/src/ganv-private.h
index 9b10a47..bc09505 100644
--- a/src/ganv-private.h
+++ b/src/ganv-private.h
@@ -112,6 +112,11 @@ struct _GanvNodeImpl {
 	gboolean          highlighted;
 	gboolean          draggable;
 	gboolean          show_label;
+	gboolean          grabbed;
+#ifdef GANV_FDGL
+	Vector            force;
+	Vector            vel;
+#endif
 };
 
 /* Port */
diff --git a/src/node.c b/src/node.c
index 4b4a72d..77791ba 100644
--- a/src/node.c
+++ b/src/node.c
@@ -68,6 +68,13 @@ ganv_node_init(GanvNode* node)
 	impl->highlighted  = FALSE;
 	impl->draggable    = FALSE;
 	impl->show_label   = TRUE;
+	impl->grabbed      = FALSE;
+#ifdef GANV_FDGL
+	impl->force.x      = 0.0;
+	impl->force.y      = 0.0;
+	impl->vel.x        = 0.0;
+	impl->vel.y        = 0.0;
+#endif
 }
 
 static void
@@ -442,6 +449,7 @@ ganv_node_default_event(GanvItem* item,
 				GDK_POINTER_MOTION_MASK|GDK_BUTTON_RELEASE_MASK|GDK_BUTTON_PRESS_MASK,
 				ganv_canvas_get_move_cursor(canvas),
 				event->button.time);
+			node->impl->grabbed = TRUE;
 			dragging = TRUE;
 			return TRUE;
 		}
@@ -452,6 +460,7 @@ ganv_node_default_event(GanvItem* item,
 			gboolean selected;
 			g_object_get(G_OBJECT(node), "selected", &selected, NULL);
 			ganv_item_ungrab(GANV_ITEM(node), event->button.time);
+			node->impl->grabbed = FALSE;
 			dragging = FALSE;
 			if (event->button.x != drag_start_x || event->button.y != drag_start_y) {
 				if (selected) {