Ruben Laguna's blog

Mar 9, 2009 - 10 minute read - Comments - algorithm based force graph java layout library netbeans prefuse topcomponent visual visualization visualizer

Force Directed Layout in NetBeans

I just came up with the idea of reproducing the GraphView demo I saw in prefuse by using the Netbeans Visual Library API.

The GraphView demo uses a Force Directed Layout algorithm to dinamically position the nodes on the screen. It’s really fast and cool. Download prefuse and experiment with it by yourself.

I wanted to achieve something similiar with the Visual Library and I succeed up to a point. The force based layout algorithm that I implemented is much simpler that the used in prefuse, so there is no spring-like movement. It looks way cooler with springs. It just uses repulsion between nodes and attraction between connected nodes.

There is also some performance issues with the Visual Library as well, the performance is not what I expected but this is maybe due to how I use the library. Or just maybe it’s just because the implementation of the layout algorithm is not as efficient as it should be. If anybody knows of a better way of using it please leave a comment in the blog.

I should warn you before that this is just a proof-of-concept on how to get a minimum force based layout algorithm working with Netbeans Visual Library. This is a starting point, it don’t think the algorithm is usable for any non-trivial app app in this state. But from here you can get the idea on how to implement your own dynamic layout (force-based or not).

This is a video of the Force Directed Layout in action:

Now let’s go and explain how I did it.

First you need a TopComponent to show the stuff.

/*
 *   DynamicLayoutDemoTopComponent.java
 *
 *   Copyright (c) 2009 Ruben Laguna <ruben.laguna at gmail.com>. All rights reserved.
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package com.rubenlaguna;

import java.awt.BorderLayout;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.logging.Logger;
import javax.swing.JComponent;
import org.openide.util.NbBundle;
import org.openide.windows.TopComponent;
import org.openide.windows.WindowManager;
//import org.openide.util.ImageUtilities;
import org.netbeans.api.settings.ConvertAsProperties;
import org.netbeans.api.visual.graph.GraphScene;
import org.netbeans.api.visual.graph.layout.GridGraphLayout;
import org.netbeans.api.visual.layout.LayoutFactory;
import org.netbeans.api.visual.layout.SceneLayout;

/**
 * Top component which displays something.
 */
@ConvertAsProperties(dtd = "-//com.rubenlaguna//DynamicLayoutDemo//EN",
autostore = false)
public final class DynamicLayoutDemoTopComponent extends TopComponent implements Runnable {

    private static DynamicLayoutDemoTopComponent instance;
    /** path to the icon used by the component and its open action */
//    static final String ICON_PATH = "SET/PATH/TO/ICON/HERE";
    private static final String PREFERRED_ID = "DynamicLayoutDemoTopComponent";
    private GraphSceneImpl2 scene;
    private JComponent view;
    private static ScheduledExecutorService EX = Executors.newSingleThreadScheduledExecutor();
    private SceneLayout sceneGraphLayout;

    public DynamicLayoutDemoTopComponent() {
        initComponents();
        setName(NbBundle.getMessage(DynamicLayoutDemoTopComponent.class, "CTL_DynamicLayoutDemoTopComponent"));
        setToolTipText(NbBundle.getMessage(DynamicLayoutDemoTopComponent.class, "HINT_DynamicLayoutDemoTopComponent"));
//        setIcon(ImageUtilities.loadImage(ICON_PATH, true));
        scene = new GraphSceneImpl2();
        view = scene.createView();
        jScrollPane1.setViewportView(view);

        add(scene.createSatelliteView(), BorderLayout.WEST);
        scene.addNode("1");
        scene.addNode("2");
        scene.addNode("3");
        scene.addNode("4");
        scene.addNode("5");
        scene.addNode("6");
        scene.addNode("7");
        scene.addNode("8");
        scene.addNode("9");
        scene.addNode("10");
        scene.addNode("11");
        scene.addNode("12");
        scene.addNode("13");
        scene.addNode("14");
        scene.addNode("15");
        scene.addNode("16");
        scene.addNode("17");
        scene.addNode("18");
        scene.addNode("19");
        scene.addNode("20");
        scene.addNode("21");
        scene.addNode("22");
        scene.addNode("23");
        scene.addNode("24");
        scene.addNode("25");



        scene.addEdge("1", "2");
        scene.addEdge("2", "3");
        scene.addEdge("3", "4");
        scene.addEdge("4", "5");

        scene.addEdge("6", "7");
        scene.addEdge("7", "8");
        scene.addEdge("8", "9");
        scene.addEdge("9", "10");

        scene.addEdge("11", "12");
        scene.addEdge("12", "13");
        scene.addEdge("13", "14");
        scene.addEdge("14", "15");

        scene.addEdge("16", "17");
        scene.addEdge("17", "18");
        scene.addEdge("18", "19");
        scene.addEdge("19", "20");

        scene.addEdge("21", "22");
        scene.addEdge("22", "23");
        scene.addEdge("23", "24");
        scene.addEdge("24", "25");

        scene.addEdge("1", "6");
        scene.addEdge("2", "7");
        scene.addEdge("3", "8");
        scene.addEdge("4", "9");
        scene.addEdge("5", "10");

        scene.addEdge("6","11");
        scene.addEdge("7","12");
        scene.addEdge("8","13");
        scene.addEdge("9","14");
        scene.addEdge("10","15");

        scene.addEdge("11","16");
        scene.addEdge("12","17");
        scene.addEdge("13","18");
        scene.addEdge("14","19");
        scene.addEdge("15","20");

        scene.addEdge("16","21");
        scene.addEdge("17","22");
        scene.addEdge("18","23");
        scene.addEdge("19","24");
        scene.addEdge("20","25");

        GridGraphLayout<String, String> graphLayout = new GridGraphLayout<String, String>();
        //sceneGraphLayout = LayoutFactory.createSceneGraphLayout(scene, graphLayout);
        //sceneGraphLayout.invokeLayout();
        ForceDirectedLayout<String, String> graphLayout2 = new ForceDirectedLayout<String, String>();
        graphLayout.setAnimated(false);
        sceneGraphLayout = LayoutFactory.createSceneGraphLayout(scene, graphLayout2);
        EX.schedule(this, 50, TimeUnit.MILLISECONDS);
    }

    /** This method is called from within the constructor to
     * initialize the form.
     * WARNING: Do NOT modify this code. The content of this method is
     * always regenerated by the Form Editor.
     */
    // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents
    private void initComponents() {

        jScrollPane1 = new javax.swing.JScrollPane();

        setLayout(new java.awt.BorderLayout());
        add(jScrollPane1, java.awt.BorderLayout.CENTER);
    }// </editor-fold>//GEN-END:initComponents
    // Variables declaration - do not modify//GEN-BEGIN:variables
    private javax.swing.JScrollPane jScrollPane1;
    // End of variables declaration//GEN-END:variables

    /**
     * Gets default instance. Do not use directly: reserved for *.settings files only,
     * i.e. deserialization routines; otherwise you could get a non-deserialized instance.
     * To obtain the singleton instance, use {@link #findInstance}.
     */
    public static synchronized DynamicLayoutDemoTopComponent getDefault() {
        if (instance == null) {
            instance = new DynamicLayoutDemoTopComponent();
        }
        return instance;
    }

    /**
     * Obtain the DynamicLayoutDemoTopComponent instance. Never call {@link #getDefault} directly!
     */
    public static synchronized DynamicLayoutDemoTopComponent findInstance() {
        TopComponent win = WindowManager.getDefault().findTopComponent(PREFERRED_ID);
        if (win == null) {
            Logger.getLogger(DynamicLayoutDemoTopComponent.class.getName()).warning(
                    "Cannot find " + PREFERRED_ID + " component. It will not be located properly in the window system.");
            return getDefault();
        }
        if (win instanceof DynamicLayoutDemoTopComponent) {
            return (DynamicLayoutDemoTopComponent) win;
        }
        Logger.getLogger(DynamicLayoutDemoTopComponent.class.getName()).warning(
                "There seem to be multiple components with the '" + PREFERRED_ID +
                "' ID. That is a potential source of errors and unexpected behavior.");
        return getDefault();
    }

    @Override
    public int getPersistenceType() {
        return TopComponent.PERSISTENCE_NEVER;
    }

    @Override
    public void componentOpened() {
        // TODO add custom code on component opening
    }

    @Override
    public void componentClosed() {
        // TODO add custom code on component closing
    }

    void writeProperties(java.util.Properties p) {
        // better to version settings since initial version as advocated at
        // http://wiki.apidesign.org/wiki/PropertyFiles
        p.setProperty("version", "1.0");
        // TODO store your settings
    }

    Object readProperties(java.util.Properties p) {
        DynamicLayoutDemoTopComponent singleton = DynamicLayoutDemoTopComponent.getDefault();
        singleton.readPropertiesImpl(p);
        return singleton;
    }

    private void readPropertiesImpl(java.util.Properties p) {
        String version = p.getProperty("version");
        // TODO read your settings according to their version
    }

    @Override
    protected String preferredID() {
        return PREFERRED_ID;
    }

    public void run() {

        sceneGraphLayout.invokeLayout();
        EX.schedule(this, 50, TimeUnit.MILLISECONDS);
    }
}

This TopComponent does a bunch of things:

  1. sets up the GraphScene

  2. adds some nodes and edges to it (forming a grid)

  3. Instantiate a ForceDirectedLayout and generate a SceneLayout out of it

  4. Creates an Executor that will do SceneLayout.invokeLayout every 50 milliseconds.

  5. The GraphScene that I use is very simple. It’s based on GraphScene.StringGraph:

/*
 *   GraphSceneImpl2.java
 *
 *   Copyright (c) 2009 Ruben Laguna <ruben.laguna at gmail.com>. All rights reserved.
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package com.rubenlaguna;

import org.netbeans.api.visual.anchor.AnchorFactory;
import org.netbeans.api.visual.graph.GraphScene;
import org.netbeans.api.visual.widget.ConnectionWidget;
import org.netbeans.api.visual.widget.LabelWidget;
import org.netbeans.api.visual.widget.LayerWidget;
import org.netbeans.api.visual.widget.Widget;

/**
 *
 * @author ecerulm
 */
public class GraphSceneImpl2 extends GraphScene.StringGraph {

    private int edgeID = 0;
    private LayerWidget mainLayer;
    private LayerWidget connectionLayer;

    public GraphSceneImpl2() {
        mainLayer = new LayerWidget(this);
        connectionLayer = new LayerWidget(this);
        addChild(mainLayer);
        addChild(connectionLayer);
    }

    @Override
    protected Widget attachNodeWidget(String node) {
        LabelWidget w = new LabelWidget(this, node);
        mainLayer.addChild(w);
        return w;
    }

    @Override
    protected Widget attachEdgeWidget(String edge) {
        ConnectionWidget connectionWidget = new ConnectionWidget(this);
        connectionLayer.addChild(connectionWidget);
        return connectionWidget;
    }

    @Override
    protected void attachEdgeSourceAnchor(String edge, String oldSourceNode, String sourceNode) {
       ((ConnectionWidget) findWidget (edge)).setSourceAnchor (AnchorFactory.createRectangularAnchor (findWidget (sourceNode)));
    }

    @Override
    protected void attachEdgeTargetAnchor(String edge, String oldTargetNode, String targetNode) {
        ((ConnectionWidget) findWidget (edge)).setTargetAnchor (AnchorFactory.createRectangularAnchor (findWidget (targetNode)));
    }

    public void addEdge(String source, String target) {
        String id = "edge" + (edgeID++);
        addEdge(id);
        setEdgeSource(id, source);
        setEdgeTarget(id, target);

    }
}

And finally the ForceDirectLayout:

/*
 *   ForceDirectedLayout.java
 *
 *   Copyright (c) 2009 Ruben Laguna <ruben.laguna at gmail.com>. All rights reserved.
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package com.rubenlaguna;

import java.awt.Point;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import org.netbeans.api.visual.graph.layout.GraphLayout;
import org.netbeans.api.visual.graph.layout.UniversalGraph;
import org.netbeans.api.visual.model.ObjectScene;
import org.netbeans.api.visual.widget.Widget;

/**
 *
 * @author ecerulm
 */
public class ForceDirectedLayout<N, E> extends GraphLayout<N, E> {

    private Random random = new Random();
    private boolean firstTime = true;

    @Override
    protected void performGraphLayout(UniversalGraph<N, E> graph) {
        ObjectScene scene = graph.getScene();
        Collection<N> allNodes = graph.getNodes();
        Map<N, Point> forceForEachNode = new HashMap<N, Point>();



        if (firstTime) {
            List<Point> list = new ArrayList<Point>();
            for (Iterator<N> it = allNodes.iterator(); it.hasNext();) {
                N object = it.next();
                Point point = new Point(random.nextInt(600), random.nextInt(600));
                list.add(point);
            }


            for (int i = 0; i < (list.size() / 2); i++) {
                Point p = list.get(i);

                for (int j = i + 1; j < list.size(); j++) {
                    Point p2 = list.get(j);
                    double distance = Math.sqrt(Math.pow(p2.x - p.x, 2) + Math.pow(p2.y - p.y, 2));
                    if (distance < 40) {
                        p2.translate(30, 30);
                    }
                }

            }
            ;

            for (Iterator<N> it = allNodes.iterator(); it.hasNext();) {
                N object = it.next();
                Point p = list.remove(0);
                setResolvedNodeLocation(graph, object, p);
                scene.findWidget(object).setPreferredLocation(p);
            }
            firstTime = false;

            return;
        }

        //initialize forceForEachNode map
        for (Iterator<N> it = allNodes.iterator(); it.hasNext();) {
            N object = it.next();
            forceForEachNode.put(object, new Point(0, 0));
        }


        //Calculate repulsion forces
        for (Iterator<N> it = allNodes.iterator(); it.hasNext();) {
            N thisNode = it.next();
            HashSet<N> allOtherNodes = new HashSet<N>(allNodes);
            allOtherNodes.remove(thisNode);
            for (Iterator<N> it1 = allOtherNodes.iterator(); it1.hasNext();) {
                N otherNode = it1.next();


                Point thisWidget = scene.findWidget(thisNode).getLocation();
                Point otherWidget = scene.findWidget(otherNode).getLocation();
                if ((null != thisWidget) && (null != otherWidget)) {
                    int x = thisWidget.x - otherWidget.x;
                    int y = thisWidget.y - otherWidget.y;
                    double sum = Math.pow(x, 2) + Math.pow(y, 2);
                    double distance = Math.sqrt(sum);
                    double minDist = 50.0;
                    x = ((int) (x * (minDist / distance))); //inversely proportional to the distance
                    y = ((int) (y * (minDist / distance)));
                    //Point force = new Point(x,y);
                    Point currentForce = forceForEachNode.get(thisNode);
                    currentForce.translate(x, y);
                }
            }
        }

        // get got all the repulsion forces.

        //now the attraction forces.
        for (Iterator<N> it = allNodes.iterator(); it.hasNext();) {
            N thisNode = it.next();
            for (E edge : graph.findNodeEdges(thisNode, true, false)) {
                N otherNode = graph.getEdgeTarget(edge);
                if (otherNode != null) {
                    Point thisWidget = scene.findWidget(thisNode).getLocation();
                    Point otherWidget = scene.findWidget(otherNode).getLocation();
                    if ((null != thisWidget) && (null != otherWidget)) {

                        int x = thisWidget.x - otherWidget.x;
                        int y = thisWidget.y - otherWidget.y;
                        double sum = Math.pow(x, 2) + Math.pow(y, 2);
                        double distance = Math.sqrt(sum);
                        double minDist = 50.0;
                        x = -((int) (x * (distance / 30))); //directly proportional to the distance
                        y = -((int) (y * (distance / 30)));

                        //Point force = new Point(x,y);
                        Point currentForce = forceForEachNode.get(thisNode);
                        currentForce.translate(x, y);
                        currentForce = forceForEachNode.get(otherNode);
                        currentForce.translate(-x, -y);
                    }
                }
            }
        }

        //Use the force  (silly joke)
        for (Iterator<N> it = allNodes.iterator(); it.hasNext();) {
            N object = it.next();
            Point force = forceForEachNode.get(object);
            int x = force.x / 50;
            int y = force.y / 50;
            if (x > 0) {
                x = Math.min(x, 15);
            } else {
                x = Math.max(x, -15);
            }
            if (y > 0) {
                y = Math.min(y, 15);
            } else {
                y = Math.max(y, -15);
            }
            //x = x+((int) (x * (((float)random.nextInt(5)) / 100.0)));
            //y = y+((int) (y * (((float)random.nextInt(5)) / 100.0)));
            x = x + (-3+random.nextInt(6));
            y = y + (-3+random.nextInt(6));


            Point newPosition = scene.findWidget(object).getLocation();
            if (null != newPosition) {
                newPosition.translate(x, y);
                setResolvedNodeLocation(graph, object, newPosition);
            }

        }
    }

    @Override
    protected void performNodesLayout(UniversalGraph<N, E> graph, Collection<N> nodes) {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}

The result is shown in the picture below. Of cource, you can’t see the dinamic behaviour of this layout algorithm in the picture. You’ll have to download and execute this Netbeans Platform Application: dynamiclayoutdemo (Netbeans 6.7 M2) to see it with you own eyes.

Reference: