projects/dwt-addons: dwtx/draw2d/graph/SortSubgraphs.d annotate

author	Frank Benoit <benoit@tionex.de>
date	Sun, 03 Aug 2008 00:52:14 +0200
parents
children

rev	line source
98 95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	1 /*******************************************************************************
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	2 * Copyright (c) 2003, 2005 IBM Corporation and others.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	3 * All rights reserved. This program and the accompanying materials
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	4 * are made available under the terms of the Eclipse Public License v1.0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	5 * which accompanies this distribution, and is available at
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	6 * http://www.eclipse.org/legal/epl-v10.html
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	7 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	8 * Contributors:
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	9 * IBM Corporation - initial API and implementation
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	10 * Port to the D programming language:
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	11 * Frank Benoit <benoit@tionex.de>
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	12 *******************************************************************************/
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	13 module dwtx.draw2d.graph.SortSubgraphs;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	14
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	15 import dwt.dwthelper.utils;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	16 import dwtx.dwtxhelper.Collection;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	17 import dwtx.draw2d.graph.GraphVisitor;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	18 import dwtx.draw2d.graph.NestingTree;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	19 import dwtx.draw2d.graph.CompoundDirectedGraph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	20 import dwtx.draw2d.graph.Node;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	21 import dwtx.draw2d.graph.NodeList;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	22 import dwtx.draw2d.graph.NodePair;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	23 import dwtx.draw2d.graph.DirectedGraph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	24 import dwtx.draw2d.graph.RankList;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	25 import dwtx.draw2d.graph.Rank;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	26 import dwtx.draw2d.graph.Subgraph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	27
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	28 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	29 * Performs a topological sort from left to right of the subgraphs in a compound directed
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	30 * graph. This ensures that subgraphs do not intertwine.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	31 * @author Randy Hudson
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	32 * @since 2.1.2
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	33 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	34 class SortSubgraphs : GraphVisitor {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	35
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	36 CompoundDirectedGraph g;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	37
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	38 NestingTree[] nestingTrees;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	39
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	40 Set orderingGraphEdges;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	41 Set orderingGraphNodes;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	42 NodePair pair;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	43
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	44 public this(){
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	45 orderingGraphEdges = new HashSet();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	46 orderingGraphNodes = new HashSet();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	47 pair = new NodePair();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	48 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	49
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	50 private void breakSubgraphCycles() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	51 //The stack of nodes which have no unmarked incoming edges
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	52 List noLefts = new ArrayList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	53
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	54 int index = 1;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	55 //Identify all initial nodes for removal
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	56 for (Iterator iter = orderingGraphNodes.iterator(); iter.hasNext();) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	57 Node node = cast(Node)iter.next();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	58 if (node.x is 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	59 sortedInsert(noLefts, node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	60 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	61
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	62 Node cycleRoot;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	63 do {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	64 //Remove all leftmost nodes, updating the nodes to their right
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	65 while (noLefts.size() > 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	66 Node node = cast(Node)noLefts.remove(noLefts.size() - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	67 node.sortValue = index++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	68 orderingGraphNodes.remove(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	69 // System.out.println("removed:" + node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	70 NodeList rightOf = rightOf(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	71 if (rightOf is null)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	72 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	73 for (int i = 0; i < rightOf.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	74 Node right = rightOf.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	75 right.x--;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	76 if (right.x is 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	77 sortedInsert(noLefts, right);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	78 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	79 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	80 cycleRoot = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	81 double min = Double.MAX_VALUE;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	82 for (Iterator iter = orderingGraphNodes.iterator(); iter.hasNext();) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	83 Node node = cast(Node)iter.next();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	84 if (node.sortValue < min) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	85 cycleRoot = node;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	86 min = node.sortValue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	87 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	88 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	89 if (cycleRoot !is null) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	90 //break the cycle;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	91 sortedInsert(noLefts, cycleRoot);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	92 // System.out.println("breaking cycle with:" + cycleRoot);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	93 // Display.getCurrent().beep();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	94 cycleRoot.x = -1; //prevent x from ever reaching 0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	95 } // else if (OGmembers.size() > 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	96 //System.out.println("FAILED TO FIND CYCLE ROOT"); //$NON-NLS-1$
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	97 } while (cycleRoot !is null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	98 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	99
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	100 private void buildSubgraphOrderingGraph() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	101 RankList ranks = g.ranks;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	102 nestingTrees = new NestingTree[ranks.size()];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	103 for (int r = 0; r < ranks.size(); r++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	104 NestingTree entry = NestingTree.buildNestingTreeForRank(ranks.getRank(r));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	105 nestingTrees[r] = entry;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	106 entry.calculateSortValues();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	107 entry.recursiveSort(false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	108 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	109
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	110 for (int i = 0; i < nestingTrees.length; i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	111 NestingTree entry = nestingTrees[i];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	112 buildSubgraphOrderingGraph(entry);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	113 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	114 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	115
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	116 private void buildSubgraphOrderingGraph(NestingTree entry) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	117 NodePair pair = new NodePair();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	118 if (entry.isLeaf)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	119 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	120 for (int i = 0; i < entry.contents.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	121 Object right = entry.contents.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	122 if (auto r = cast(Node)right )
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	123 pair.n2 = r;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	124 else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	125 pair.n2 = (cast(NestingTree)right).subgraph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	126 buildSubgraphOrderingGraph(cast(NestingTree)right);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	127 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	128 if (pair.n1 !is null && !orderingGraphEdges.contains(pair)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	129 orderingGraphEdges.add(pair);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	130 leftToRight(pair.n1, pair.n2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	131 orderingGraphNodes.add(pair.n1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	132 orderingGraphNodes.add(pair.n2);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	133 pair.n2.x++; //Using x field to count predecessors.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	134 pair = new NodePair(pair.n2, null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	135 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	136 pair.n1 = pair.n2;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	137 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	138 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	139 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	140
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	141 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	142 * Calculates the average position P for each node and subgraph. The average position is
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	143 * stored in the sortValue for each node or subgraph.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	144 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	145 * Runs in approximately linear time with respect to the number of nodes, including
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	146 * virtual nodes.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	147 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	148 private void calculateSortValues() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	149 RankList ranks = g.ranks;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	150
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	151 g.subgraphs.resetSortValues();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	152 g.subgraphs.resetIndices();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	153
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	154 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	155 * For subgraphs, the sum of all positions is kept, along with the number of
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	156 * contributions, which is tracked in the subgraph's index field.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	157 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	158 for (int r = 0; r < ranks.size(); r++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	159 Rank rank = ranks.getRank(r);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	160 for (int j = 0; j < rank.count(); j++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	161 Node node = rank.getNode(j);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	162 node.sortValue = node.index;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	163 Subgraph parent = node.getParent();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	164 while (parent !is null) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	165 parent.sortValue += node.sortValue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	166 parent.index++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	167 parent = parent.getParent();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	168 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	169 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	170 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	171
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	172 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	173 * For each subgraph, divide the sum of the positions by the number of contributions,
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	174 * to give the average position.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	175 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	176 for (int i = 0; i < g.subgraphs.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	177 Subgraph subgraph = cast(Subgraph)g.subgraphs.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	178 subgraph.sortValue /= subgraph.index;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	179 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	180 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	181
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	182 private void repopulateRanks() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	183 for (int i = 0; i < nestingTrees.length; i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	184 Rank rank = g.ranks.getRank(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	185 rank.clear();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	186 nestingTrees[i].repopulateRank(rank);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	187 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	188 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	189
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	190 private NodeList rightOf(Node left) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	191 return cast(NodeList)left.workingData[0];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	192 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	193
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	194 private void leftToRight(Node left, Node right) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	195 rightOf(left).add(right);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	196 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	197
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	198 void sortedInsert(List list, Node node) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	199 int insert = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	200 while (insert < list.size()
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	201 && (cast(Node)list.get(insert)).sortValue > node.sortValue)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	202 insert++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	203 list.add(insert, node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	204 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	205
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	206 private void topologicalSort() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	207 for (int i = 0; i < nestingTrees.length; i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	208 nestingTrees[i].getSortValueFromSubgraph();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	209 nestingTrees[i].recursiveSort(false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	210 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	211 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	212
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	213 void init() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	214 for (int r = 0; r < g.ranks.size(); r++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	215 Rank rank = g.ranks.getRank(r);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	216 for (int i = 0; i < rank.count(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	217 Node n = cast(Node)rank.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	218 n.workingData[0] = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	219 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	220 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	221 for (int i = 0; i < g.subgraphs.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	222 Subgraph s = cast(Subgraph)g.subgraphs.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	223 s.workingData[0] = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	224 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	225 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	226
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	227 public void visit(DirectedGraph dg) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	228 g = cast(CompoundDirectedGraph)dg;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	229
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	230 init();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	231 buildSubgraphOrderingGraph();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	232 calculateSortValues();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	233 breakSubgraphCycles();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	234 topologicalSort();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	235 repopulateRanks();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	236 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	237
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	238 }

98

95307ad235d9 Added Draw2d code, still work in progress