Specification - GSoC Force-Directed Edge Bundling

From Gephi:Wiki

Jump to: navigation, search

GSoC Project Force-Directed Edge Bundling

Student: Christopher Kelvin Lee

Mentor: Jeremy Subtil


This article is work in progress.



Contents

Abstract

Node-link diagrams can be problematic because large number of nodes and edges often causes visual clutter. My objective is to build and improve on the Vectorial Preview project completed by Jeremy Subtil in GSoC 2009. Gephi currently uses the statistical hierarchy method to reduce clutter in the layout module. The layout module exports into the preview module.

I will add Force Directed Edge Bundling (FDEB) support into the Gephi Preview module for improved visual comprehension. Implementing the FDEB algorithm will require refactoring the Preview API for vectorial export of SVG/PDF with the option of FDEB rendering.


Background

Preview API is a set of interfaces letting the user manipulate the preview graph structure from external plugins.

  • PreviewController controls this preview graph structure building, interacts w/PreviewGraphFactory
    • PreviewModel holds preview settings in supervisor objects. When a change is made to preview setting, supervisor notifies/updates preview graph elements
      • The following are example PreviewModel classes:
        • NodeSupervisor -> handles node color, border, radius
        • EdgeSupervisor -> handles edge curves, colors
        • DirectedEdgeSupervisor -> handles mini-labels and arrows size for directed edges
        • DirectedEdgeSupervisorImpl -> extends EdgeSupervisorImpl for (c)
    • PreviewImpl is a set of classes implementing the Preview API interfaces. It builds the preview graph structure and handles its computations when settings are changed.
      • PreviewGraphFactory builds the preview graph structure elements (e.g. nodes, edges, colors, etc.) This is a PreviewImpl class.
  • DesktopPreview contains (1) UI and (2) Processing applet for rendering preview graphs
    • ProcessingPreview.java holds the handling engine
  • PreviewExport contains preview export classes, such as the SVG and the PDF ones.

Extended goals of this project

  1. Implement FDEB algorithm/module independently
  2. Refractor Preview API to integrate FDEB
  3. Improve Preview API modularity


Refactoring Proposal

Phase 1: Brainstorming FDEB processing applet

I propose that I first make a copy ProcessingPreview.java within DesktopPreview and rewrite it as ProcessingFDEBPreview.java. The purpose of this initial separation is to give the user the option to use FDEB rendering (my proposed project) or opt for the existing rendering (last year’s project.)

Within ProcessingFDEBPreview.java, I will write the FDEB algorithm based on edge clutter reduction using edge bundling techniques proposed by Holten and van Wijk. The cited paper recommends edge compatibility measures and calculations, with algorithms recreating Coulomb repulsion for nodes and Hooke’s attraction for edges. This physics engine will be written within the existing architecture of Supervisor, SupervisorImpl, and PreviewImpl classes.


Phase 2: Implement FDEB module within vectorial preview

Currently, the Vectorial Preview uses a processing-based graph rendering component for export. The proposed FDEB Vectorial Preview will be an added option for FDEB processing-based graph rendering. As proposed by a mentor, I will need to improve the module to configure properties of (1) bundled edges, (2) the “electrostatic force” between points, (3) the number of combination of subdivision points, and (4) edge compatibility and smoothing. Presets should loaded and modified easily through UI. PDFExporter and SVGExporter will need to be modified to support FDEB and future builds.

The proposed solution is targeted to solve the goal proposed by the mentor: each property would be separately rendered and handled through Processing, PDF, and SVG modules. Only friends of the certain algorithm can pass an instance to these renderers, and the friendpackage would link this bridge and inherit tasks from the existing supervisors system.


Phase 3: Design Preview API for improved UI and modularity

The current problem with the existing Preview API is organization. For example, there are eight instances to handle Edge, and I feel this should be simplified to one, where arrows, color, child, labels, minilabels, etc. are handled within one handler. The same applies for nodes, childs, and future objects that are scaled.In the forced-based graph API source code, the graphic engine is separated into three subdirectories (1) algorithm, (2) data, and (3) graphic engine.

(1) FDEB Algorithm

The FDEB algorithm and all future rendering plugins should be placed in the algorithm subdirectory.

(2) Data Engine

Edge, node, and child settings, setup factories, and generators should be placed in the data engine subdirectory.

(3) Graph Engine

One possible refactoring strategy is to focus on ProcessingPreview and organize its render() routines into a rendering engine classes that are linked to node, edge, and child properties produced from FDEB algorithms with appropriate factories/generators. I found one API Design sample that could be useful to adopt. It’s called friendpackage that bridges an api and impl package through synchronious output. In NetBeans, I found a specific class called Interface MethodElement.Impl that can handle this task if written in a similar structure as the source code.


This module design allows for extensibility because the new plugin algorithm could be dropped in (1), plugin settings and properties should be placed in (2), and few or no changes to friendpackages/supervisors should be placed in (3). The master PreviewModel and PreviewController will only need minor changes and should be placed in the directory.


Note

It is important to make sure that the proposed API design encounters no errors in scalability. New API plugins and algorithm packages could call multiple instances of render and cause bugs. Furthermore, mishandling of the friendpackage could cause concurrency errors when instances are sent multiple times to the render() functions. Thus it is important for the refactored supervisor/friendpackage and UI to circumvent these potential problems.


Roadmap

  • April 9 – May 24: It will take some time before I become very familiar with NetBeans API and Practical API Design, and I think it is essential for progress
  • April 9 – April 26: Biggest test for myself: become familiar with the bugs listed on launchpad so that I understand Gephi API beyond PreviewAPI
  • April 26 – May 24: Community Bonding Period, get full attention for ideas, ask all possible questions, make sure I am familiar with everything on my own, finalize realistic goals and roadmap
  • May 24 – June 14 (Three Weeks): Do Part 1 and make sure FDEB Processing algorithms is successful
  • June 14 – June 21 (One Week): Review work of FDEB w/ mentor, fix bugs, make improvements, finalize roadmap to integrate FDEB into PreviewAPI refactoring for Part 2
  • June 21 – July 12 (Three Weeks): Make as much progress as possible to meet the mid-term evaluations. My goal is to have a working version of FDEB by this deadline.
  • July 12 – August 9 (Four Weeks): Design, design, design. Focus on modularity and extensible classes. Take into consideration mbastian’s comment, “There is no extensive use of Lookup in the Preview modules, except for PreviewController. However that must change with the planned refactoring, as more modularity will be developed. Just an example applied to Preview, one can imagine Properties class implementingPreviewProperty and setting the annotation.”
  • August 9 – August 16 (One Week): “Take a week to scrub code, write tests, improve documentation, etc.”

References

Retrieved from "http://wiki.gephi.org/index.php/Specification_-_GSoC_Force-Directed_Edge_Bundling"
Personal tools