From ef91731a480b79c96e10b2b5256a36407bb5ef6e Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 18 Dec 2013 00:31:20 +0000 Subject: 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 --- ganv/types.h | 7 +++ src/Canvas.cpp | 124 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/ganv-private.h | 5 +++ src/node.c | 9 ++++ wscript | 9 +++- 5 files changed, 152 insertions(+), 2 deletions(-) diff --git a/ganv/types.h b/ganv/types.h index 10b6a90..677cb06 100644 --- a/ganv/types.h +++ b/ganv/types.h @@ -23,5 +23,12 @@ typedef struct _GanvNode GanvNode; typedef struct _GanvPort GanvPort; typedef struct _GanvBox GanvBox; +#ifdef GANV_FDGL +typedef struct { + double x; + double y; +} Vector; +#endif // GANV_FDGL + #endif /* GANV_TYPES_H */ 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 #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) { diff --git a/wscript b/wscript index 0abb4a4..364c106 100644 --- a/wscript +++ b/wscript @@ -25,6 +25,8 @@ def options(opt): help='Build unit tests') opt.add_option('--no-graphviz', action='store_true', dest='no_graphviz', help='Do not compile with graphviz support') + opt.add_option('--fdgl', action='store_true', dest='fdgl', + help='Use experimental force-directed graph layout') opt.add_option('--no-nls', action='store_true', dest='no_nls', help='Disable i18n (native language support)') opt.add_option('--gir', action='store_true', dest='gir', @@ -54,6 +56,9 @@ def configure(conf): autowaf.check_pkg(conf, 'libgvc', uselib_store='AGRAPH', atleast_version='2.8', mandatory=False) + if Options.options.fdgl: + autowaf.define(conf, 'GANV_FDGL', 1) + if not Options.options.no_nls: autowaf.check_header(conf, 'c', 'libintl.h', 'ENABLE_NLS', mandatory=False) @@ -128,7 +133,7 @@ def build(bld): if bld.env.BUILD_TESTS: # Static library for test program - bld(features = 'c cstlib', + bld(features = 'c cstlib cxx cxxshlib', source = ganv_source, includes = ['.', './src'], name = 'libganv_profiled', @@ -138,7 +143,7 @@ def build(bld): cflags = [ '-fprofile-arcs', '-ftest-coverage' ]) # Test program (C) - bld(features = 'c cprogram', + bld(features = 'cxx cxxprogram', source = 'src/ganv_test.c', includes = ['.', './src'], use = 'libganv_profiled', -- cgit v1.2.1