Mercurial > projects > dwt2
diff org.eclipse.draw2d/src/org/eclipse/draw2d/graph/CompoundRankSorter.d @ 12:bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
author | Frank Benoit <benoit@tionex.de> |
---|---|
date | Sat, 14 Mar 2009 18:23:29 +0100 |
parents | |
children | dbfb303e8fb0 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/org.eclipse.draw2d/src/org/eclipse/draw2d/graph/CompoundRankSorter.d Sat Mar 14 18:23:29 2009 +0100 @@ -0,0 +1,237 @@ +/******************************************************************************* + * Copyright (c) 2003, 2005 IBM Corporation and others. + * 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: + * IBM Corporation - initial API and implementation + * Port to the D programming language: + * Frank Benoit <benoit@tionex.de> + *******************************************************************************/ +module org.eclipse.draw2d.graph.CompoundRankSorter; + +import java.lang.all; +import org.eclipse.draw2d.graph.RankSorter; +import org.eclipse.draw2d.graph.Subgraph; +import org.eclipse.draw2d.graph.Node; +import org.eclipse.draw2d.graph.DirectedGraph; +import org.eclipse.draw2d.graph.Rank; +import org.eclipse.draw2d.graph.NestingTree; +import org.eclipse.draw2d.graph.CompoundDirectedGraph; +import org.eclipse.draw2d.graph.Edge; +import org.eclipse.draw2d.graph.LocalOptimizer; + +/** + * Sorts nodes in a compound directed graph. + * @author Randy Hudson + * @since 2.1.2 + */ +class CompoundRankSorter : RankSorter { + +static class RowEntry { + double contribution; + int count; + void reset() { + count = 0; + contribution = 0; + } +} + +static class RowKey { + int rank; + Subgraph s; + this() { } + this(Subgraph s, int rank) { + this.s = s; + this.rank = rank; + } + + public override int opEquals(Object obj) { + RowKey rp = cast(RowKey)obj; + return rp.s is s && rp.rank is rank; + } + + public override hash_t toHash() { + return s.toHash() ^ (rank * 31); + } +} + +bool init_; +RowKey key; + +Map map; + +public this(){ + key = new RowKey(); + map = new HashMap(); +} + +void addRowEntry(Subgraph s, int row) { + key.s = s; + key.rank = row; + if (!map.containsKey(key)) + map.put(new RowKey(s, row), new RowEntry()); +} + +protected void assignIncomingSortValues() { + super.assignIncomingSortValues(); + pullTogetherSubgraphs(); +} + +protected void assignOutgoingSortValues() { + super.assignOutgoingSortValues(); + pullTogetherSubgraphs(); +} + +void optimize(DirectedGraph g) { + CompoundDirectedGraph graph = cast(CompoundDirectedGraph)g; + Iterator containment = graph.containment.iterator(); + while (containment.hasNext()) + graph.removeEdge(cast(Edge)containment.next()); + graph.containment.clear(); + (new LocalOptimizer()) + .visit(graph); +} + +private void pullTogetherSubgraphs() { + if (true) + return; + for (int j = 0; j < rank.count(); j++) { + Node n = rank.getNode(j); + Subgraph s = n.getParent(); + while (s !is null) { + getRowEntry(s, currentRow).reset(); + s = s.getParent(); + } + } + for (int j = 0; j < rank.count(); j++) { + Node n = rank.getNode(j); + Subgraph s = n.getParent(); + while (s !is null) { + RowEntry entry = getRowEntry(s, currentRow); + entry.count++; + entry.contribution += n.sortValue; + s = s.getParent(); + } + } + + double weight = 0.5;// * (1.0 - progress) * 3; + + for (int j = 0; j < rank.count(); j++) { + Node n = rank.getNode(j); + Subgraph s = n.getParent(); + if (s !is null) { + RowEntry entry = getRowEntry(s, currentRow); + n.sortValue = + n.sortValue * (1.0 - weight) + weight * entry.contribution / entry.count; + } + } +} + +double evaluateNodeOutgoing() { + double result = super.evaluateNodeOutgoing(); +// result += Math.random() * rankSize * (1.0 - progress) / 3.0; + if (progress > 0.2) { + Subgraph s = node.getParent(); + double connectivity = mergeConnectivity(s, node.rank + 1, result, progress); + result = connectivity; + } + return result; +} + +double evaluateNodeIncoming() { + double result = super.evaluateNodeIncoming(); +// result += Math.random() * rankSize * (1.0 - progress) / 3.0; + if (progress > 0.2) { + Subgraph s = node.getParent(); + double connectivity = mergeConnectivity(s, node.rank - 1, result, progress); + result = connectivity; + } + return result; +} + +double mergeConnectivity(Subgraph s, int row, double result, double scaleFactor) { + while (s !is null && getRowEntry(s, row) is null) + s = s.getParent(); + if (s !is null) { + RowEntry entry = getRowEntry(s, row); + double connectivity = entry.contribution / entry.count; + result = connectivity * 0.3 + (0.7) * result; + s = s.getParent(); + } + return result; +} + +RowEntry getRowEntry(Subgraph s, int row) { + key.s = s; + key.rank = row; + return cast(RowEntry)map.get(key); +} + +void copyConstraints(NestingTree tree) { + if (tree.subgraph !is null) + tree.sortValue = tree.subgraph.rowOrder; + for (int i = 0; i < tree.contents.size(); i++) { + Object child = tree.contents.get(i); + if (auto n = cast(Node)child ) { + n.sortValue = n.rowOrder; + } else { + copyConstraints(cast(NestingTree)child); + } + } +} + +public void init(DirectedGraph g) { + super.init(g); + init_ = true; + + for (int row = 0; row < g.ranks.size(); row++) { + Rank rank = g.ranks.getRank(row); + + NestingTree tree = NestingTree.buildNestingTreeForRank(rank); + copyConstraints(tree); + tree.recursiveSort(true); + rank.clear(); + tree.repopulateRank(rank); + + for (int j = 0; j < rank.count(); j++) { + Node n = rank.getNode(j); + Subgraph s = n.getParent(); + while (s !is null) { + addRowEntry(s, row); + s = s.getParent(); + } + } + } +} + +protected void postSort() { + super.postSort(); + if (init_) + updateRank(rank); +} + +void updateRank(Rank rank) { + for (int j = 0; j < rank.count(); j++) { + Node n = rank.getNode(j); + Subgraph s = n.getParent(); + while (s !is null) { + getRowEntry(s, currentRow).reset(); + s = s.getParent(); + } + } + for (int j = 0; j < rank.count(); j++) { + Node n = rank.getNode(j); + Subgraph s = n.getParent(); + while (s !is null) { + RowEntry entry = getRowEntry(s, currentRow); + entry.count++; + entry.contribution += n.index; + s = s.getParent(); + } + } +} + +}