summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRene Kuhlemann2012-08-27 16:34:11 (EDT)
committer Fabian Steeg2012-08-27 16:34:11 (EDT)
commit8f24887180493f186cdd7a0f4d722caf2d97d849 (patch)
tree7108bdc5c95f905ae43ecb8cc6b7460d148c2e8f
parentc4a1a6eeac47f230171428d35094d9deea8e054b (diff)
downloadorg.eclipse.gef4-8f24887180493f186cdd7a0f4d722caf2d97d849.zip
org.eclipse.gef4-8f24887180493f186cdd7a0f4d722caf2d97d849.tar.gz
org.eclipse.gef4-8f24887180493f186cdd7a0f4d722caf2d97d849.tar.bz2
[384730] Sugiyama DAG layout algorithm (CQ 6643)
A layout algorithm that implements layered drawing for directed acyclic graphs using the Sugiyama method.
-rw-r--r--org.eclipse.zest.layouts/src/org/eclipse/zest/layouts/algorithms/SugiyamaLayoutAlgorithm.java412
1 files changed, 412 insertions, 0 deletions
diff --git a/org.eclipse.zest.layouts/src/org/eclipse/zest/layouts/algorithms/SugiyamaLayoutAlgorithm.java b/org.eclipse.zest.layouts/src/org/eclipse/zest/layouts/algorithms/SugiyamaLayoutAlgorithm.java
new file mode 100644
index 0000000..9a7c968
--- /dev/null
+++ b/org.eclipse.zest.layouts/src/org/eclipse/zest/layouts/algorithms/SugiyamaLayoutAlgorithm.java
@@ -0,0 +1,412 @@
+/*******************************************************************************
+ * Copyright (c) 2012 Rene Kuhlemann.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Rene Kuhlemann - provided first version of code based on the initial paper
+ * of Sugiyama et al. (http://dx.doi.org/10.1109/TSMC.1981.4308636),
+ * associated to bugzilla entry #384730
+ *******************************************************************************/
+package org.eclipse.zest.layouts.algorithms;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.IdentityHashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+
+import org.eclipse.draw2d.geometry.Dimension;
+import org.eclipse.zest.layouts.LayoutAlgorithm;
+import org.eclipse.zest.layouts.dataStructures.DisplayIndependentRectangle;
+import org.eclipse.zest.layouts.interfaces.LayoutContext;
+import org.eclipse.zest.layouts.interfaces.NodeLayout;
+
+/**
+ * The SugiyamaLayoutAlgorithm class implements an algorithm to arrange a
+ * directed graph in a layered tree-like layout. The final presentation follows
+ * five design principles for enhanced readability:
+ *
+ * - Hierarchical layout of vertices - Least crossings of lines (edges) -
+ * Straightness of lines when ever possible - Close layout of vertices connected
+ * to each other, i.e. short paths - Balanced layout of lines coming into or
+ * going from a vertex
+ *
+ * For further information see http://dx.doi.org/10.1109/TSMC.1981.4308636
+ *
+ * This layout algorithm works only with - directed graphs (
+ * {@link ZestStyles.CONNECTIONS_DIRECTED}) - graphs without cycles (otherwise
+ * an appropriate RuntimeException is thrown)
+ *
+ * @version 1.0
+ * @author Rene Kuhlemann
+ */
+public class SugiyamaLayoutAlgorithm implements LayoutAlgorithm {
+
+ // Tree direction constants
+ public final static int HORIZONTAL = 1;
+ public final static int VERTICAL = 2;
+
+ // Internal constants
+ private static final int MAX_LAYERS = 10;
+ private static final int MAX_SWEEPS = 50;
+ private static final int PADDING = -1;
+
+ private class NodeWrapper {
+ int index;
+ final int layer;
+ final NodeLayout node;
+ final List<NodeWrapper> pred = new LinkedList<NodeWrapper>();
+ final List<NodeWrapper> succ = new LinkedList<NodeWrapper>();
+
+ NodeWrapper(NodeLayout n, int l) {
+ node = n;
+ layer = l;
+ } // NodeLayout wrapper
+
+ NodeWrapper(int l) {
+ this(null, l);
+ } // Dummy to connect two NodeLayout objects
+
+ NodeWrapper() {
+ this(null, PADDING);
+ } // Padding for final refinement phase
+
+ void addPredecessor(NodeWrapper node) {
+ pred.add(node);
+ }
+
+ void addSuccessor(NodeWrapper node) {
+ succ.add(node);
+ }
+
+ boolean isDummy() {
+ return ((node == null) && (layer != PADDING));
+ }
+
+ boolean isPadding() {
+ return ((node == null) && (layer == PADDING));
+ }
+
+ int getPriorityDown() {
+ if (isPadding())
+ return (0);
+ if (isDummy()) {
+ if (succ.get(0).isDummy())
+ return (Integer.MAX_VALUE); // part of a straight line
+ else
+ return (Integer.MAX_VALUE >> 1); // start of a straight line
+ }
+ return (pred.size());
+ }
+
+ int getPriorityUp() {
+ if (isPadding())
+ return (0);
+ if (isDummy()) {
+ if (pred.get(0).isDummy())
+ return (Integer.MAX_VALUE); // part of a straight line
+ else
+ return (Integer.MAX_VALUE >> 1); // start of a straight line
+ }
+ return (succ.size());
+ }
+
+ }
+
+ private final List<ArrayList<NodeWrapper>> layers = new ArrayList<ArrayList<NodeWrapper>>(
+ MAX_LAYERS);
+ private final Map<NodeLayout, NodeWrapper> map = new IdentityHashMap<NodeLayout, NodeWrapper>();
+ private final int direction;
+ private final Dimension dimension;
+
+ private LayoutContext context;
+ private int size; // size of the biggest layer for various purposes
+
+ /**
+ * Constructs a tree-like, layered layout of a directed graph.
+ *
+ * @param dir
+ * - {@link SugiyamaLayoutAlgorithm#HORIZONTAL}: left to right -
+ * {@link SugiyamaLayoutAlgorithm#VERTCAL}: top to bottom
+ *
+ * @param dim
+ * - desired size of the layout area. Uses
+ * {@link LayoutContext#getBounds()} if not set
+ */
+ public SugiyamaLayoutAlgorithm(int dir, Dimension dim) {
+ if (dir == HORIZONTAL)
+ direction = HORIZONTAL;
+ else
+ direction = VERTICAL;
+ dimension = dim;
+ }
+
+ public SugiyamaLayoutAlgorithm(int dir) {
+ this(dir, null);
+ }
+
+ public SugiyamaLayoutAlgorithm() {
+ this(VERTICAL, null);
+ }
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see
+ * org.eclipse.zest.layouts.LayoutAlgorithm#setLayoutContext(org.eclipse
+ * .zest.layouts.interfaces.LayoutContext)
+ */
+ public void setLayoutContext(LayoutContext context) {
+ this.context = context;
+ }
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see org.eclipse.zest.layouts.LayoutAlgorithm#applyLayout(boolean)
+ */
+ public void applyLayout(boolean clean) {
+ if (!clean)
+ return;
+ layers.clear();
+ map.clear();
+ createLayers();
+ reduceCrossings();
+ padLayers();
+ refineLayers();
+ calculatePositions();
+ }
+
+ private void createLayers() {
+ List<NodeLayout> nodes = new ArrayList<NodeLayout>(
+ Arrays.asList(context.getNodes()));
+ List<NodeLayout> predecessors = findRoots(nodes);
+ nodes.removeAll(predecessors); // nodes now contains only nodes that are
+ // no roots
+ addLayer(predecessors);
+ for (int level = 1; nodes.isEmpty() == false; level++) {
+ if (level > MAX_LAYERS)
+ throw new RuntimeException(
+ "Graphical tree exceeds maximum depth of " + MAX_LAYERS
+ + "! (Graph not directed? Cycles?)");
+ List<NodeLayout> layer = new ArrayList<NodeLayout>();
+ for (NodeLayout item : nodes) {
+ if (predecessors.containsAll(Arrays.asList(item
+ .getPredecessingNodes())))
+ layer.add(item);
+ }
+ nodes.removeAll(layer);
+ predecessors.addAll(layer);
+ addLayer(layer);
+ }
+ }
+
+ /**
+ * Wraps all {@link NodeLayout} objects into an internal presentation
+ * {@link NodeWrapper} and inserts dummy wrappers into the layers between an
+ * object and their predecessing nodes if necessary. Finally, all nodes are
+ * chained over immediate adjacent layers down to their predecessors. This
+ * is necessary to apply the final step of the Sugiyama algorithm to refine
+ * the node position within a layer.
+ *
+ * @param list
+ * : List of all {@link NodeLayout} objects within the current
+ * layer
+ */
+ private void addLayer(List<NodeLayout> list) {
+ ArrayList<NodeWrapper> layer = new ArrayList<NodeWrapper>(list.size());
+ for (NodeLayout node : list) {
+ // wrap each NodeLayout with the internal data object and provide a
+ // corresponding mapping
+ NodeWrapper nw = new NodeWrapper(node, layers.size());
+ map.put(node, nw);
+ layer.add(nw);
+ // insert dummy nodes if the adjacent layer does not contain the
+ // predecessor
+ for (NodeLayout node_predecessor : node.getPredecessingNodes()) { // for
+ // all
+ // predecessors
+ NodeWrapper nw_predecessor = map.get(node_predecessor);
+ for (int level = nw_predecessor.layer + 1; level < nw.layer; level++) {
+ // add "virtual" wrappers (dummies) to the layers in between
+ // virtual wrappers are in fact parts of a double linked
+ // list
+ NodeWrapper nw_dummy = new NodeWrapper(level);
+ nw_dummy.addPredecessor(nw_predecessor);
+ nw_predecessor.addSuccessor(nw_dummy);
+ nw_predecessor = nw_dummy;
+ layers.get(level).add(nw_dummy);
+ }
+ nw.addPredecessor(nw_predecessor);
+ nw_predecessor.addSuccessor(nw);
+ }
+ }
+ layers.add(layer);
+ updateIndex(layer);
+ }
+
+ /**
+ * Reduces connection crossings between two adjacent layers by a combined
+ * top-down and bottom-up approach. It uses a heuristic approach based on
+ * the predecessor's barycenter.
+ */
+ private void reduceCrossings() {
+ for (int round = 0; round < MAX_SWEEPS; round++) {
+ if ((round & 1) == 0) { // if round is even then do a bottom-up scan
+ for (int index = 1; index < layers.size(); index++)
+ reduceCrossingsDown(layers.get(index));
+ } else { // else top-down
+ for (int index = layers.size() - 2; index >= 0; index--)
+ reduceCrossingsUp(layers.get(index));
+ }
+ }
+ }
+
+ private static void reduceCrossingsDown(ArrayList<NodeWrapper> layer) {
+ // DOWN: scan PREDECESSORS
+ for (NodeWrapper node : layer)
+ node.index = getBaryCenter(node.pred);
+ Collections.sort(layer, new Comparator<NodeWrapper>() {
+ public int compare(NodeWrapper node1, NodeWrapper node2) {
+ return (node1.index - node2.index);
+ }
+ });
+ updateIndex(layer);
+ }
+
+ private static void reduceCrossingsUp(ArrayList<NodeWrapper> layer) {
+ // UP: scan SUCCESSORS
+ for (NodeWrapper node : layer)
+ node.index = getBaryCenter(node.succ);
+ Collections.sort(layer, new Comparator<NodeWrapper>() {
+ public int compare(NodeWrapper node1, NodeWrapper node2) {
+ return (node1.index - node2.index);
+ }
+ });
+ updateIndex(layer);
+ }
+
+ /**
+ * Fills in virtual nodes, so the layer system finally becomes an
+ * equidistant grid
+ */
+ private void padLayers() {
+ size = 0;
+ for (List<NodeWrapper> iter : layers)
+ if (iter.size() > size)
+ size = iter.size();
+ for (List<NodeWrapper> iter : layers) { // padding is always added at
+ // the END of each layer!
+ for (int i = size - iter.size(); i > 0; i--)
+ iter.add(new NodeWrapper());
+ updateIndex(iter);
+ }
+ }
+
+ private void refineLayers() { // from Sugiyama paper: down, up and down
+ // again yields best results, wonder why...
+ for (int index = 1; index < layers.size(); index++)
+ refineLayersDown(layers.get(index));
+ for (int index = layers.size() - 1; index > 0; index--)
+ refineLayersUp(layers.get(index));
+ for (int index = 1; index < layers.size(); index++)
+ refineLayersDown(layers.get(index));
+ }
+
+ private void refineLayersDown(List<NodeWrapper> layer) {
+ final int end = layer.size() - 1;
+ // first, get a priority list
+ List<NodeWrapper> list = new ArrayList<NodeWrapper>(layer);
+ Collections.sort(list, new Comparator<NodeWrapper>() {
+ public int compare(NodeWrapper node1, NodeWrapper node2) {
+ return (node2.getPriorityDown() - node1.getPriorityDown()); // descending
+ // ordering!!!
+ }
+ });
+ // second, remove padding from the layer's end and place them in front
+ // of the current node to improve its position
+ for (NodeWrapper iter : list) {
+ if (iter.isPadding())
+ break; // break, if there are no more "real" nodes
+ int delta = getBaryCenter(iter.pred) - iter.index; // distance to
+ // new position
+ for (int i = 0; i < delta; i++)
+ layer.add(iter.index, layer.remove(end));
+ }
+ updateIndex(layer);
+ }
+
+ private void refineLayersUp(List<NodeWrapper> layer) {
+ final int end = layer.size() - 1;
+ // first, get a priority list
+ List<NodeWrapper> list = new ArrayList<NodeWrapper>(layer);
+ Collections.sort(list, new Comparator<NodeWrapper>() {
+ public int compare(NodeWrapper node1, NodeWrapper node2) {
+ return (node2.getPriorityUp() - node1.getPriorityUp()); // descending
+ // ordering!!!
+ }
+ });
+ // second, remove padding from the layer's end and place them in front
+ // of the current node to improve its position
+ for (NodeWrapper iter : list) {
+ if (iter.isPadding())
+ break; // break, if there are no more "real" nodes
+ int delta = getBaryCenter(iter.succ) - iter.index; // distance to
+ // new position
+ for (int i = 0; i < delta; i++)
+ layer.add(iter.index, layer.remove(end));
+ }
+ updateIndex(layer);
+ }
+
+ private void calculatePositions() {
+ DisplayIndependentRectangle bound = context.getBounds();
+ if (dimension != null)
+ bound = new DisplayIndependentRectangle(0, 0,
+ dimension.preciseWidth(), dimension.preciseHeight());
+ double dx = bound.width / layers.size();
+ double dy = bound.height / size;
+ for (NodeLayout node : context.getNodes()) {
+ NodeWrapper nw = map.get(node);
+ if (direction == HORIZONTAL)
+ node.setLocation((nw.layer + 0.5d) * dx, (nw.index + 0.5d) * dy);
+ else
+ node.setLocation((nw.index + 0.5d) * dx, (nw.layer + 0.5d) * dy);
+ }
+ }
+
+ private static List<NodeLayout> findRoots(List<NodeLayout> list) {
+ List<NodeLayout> roots = new ArrayList<NodeLayout>();
+ for (NodeLayout iter : list) { // no predecessors means: this is a root,
+ // add it to list
+ if (iter.getPredecessingNodes().length == 0)
+ roots.add(iter);
+ }
+ return (roots);
+ }
+
+ private static int getBaryCenter(List<NodeWrapper> list) {
+ if (list.isEmpty())
+ return (0);
+ if (list.size() == 1)
+ return (list.get(0).index);
+ double barycenter = 0;
+ for (NodeWrapper node : list)
+ barycenter += node.index;
+ return ((int) (barycenter / list.size())); // always rounding off to
+ // avoid wrap around in
+ // position refining!!!
+ }
+
+ private static void updateIndex(List<NodeWrapper> list) {
+ for (int index = 0; index < list.size(); index++)
+ list.get(index).index = index;
+ }
+
+} \ No newline at end of file