Mercurial > projects > dwt-addons
annotate dwtx/draw2d/graph/CollapsedEdges.d @ 98:95307ad235d9
Added Draw2d code, still work in progress
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) 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.CollapsedEdges; |
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.draw2d.graph.Edge; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
17 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
18 /** |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
19 * Contains the information from all edges going from a given cluster to some other |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
20 * cluster. An edge with minimal slack as chosen to maintain the link between clusters. |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
21 * The weight and any slack more than the minimal edge's slack is tracked for all other |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
22 * edges. |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
23 * @since 3.1 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
24 */ |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
25 class CollapsedEdges { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
26 |
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 * The total weight of the collapsed edges. |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
29 */ |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
30 int collapsedWeight; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
31 int collapsedCount; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
32 |
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 * The total amount of weighted difference in the collapsed edges slack and the |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
35 * tightest edge's slack. |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
36 */ |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
37 int overage; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
38 int unOverage; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
39 Edge tightestEdge; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
40 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
41 this(Edge edge) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
42 tightestEdge = edge; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
43 collapsedWeight = edge.weight; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
44 collapsedCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
45 } |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
46 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
47 public int getWeightedPull() { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
48 return tightestEdge.getSlack() * collapsedWeight + overage; |
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 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
51 public bool isTight() { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
52 return tightestEdge.getSlack() is 0; |
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 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
55 /** |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
56 * Compares the given edge to the current tightest edge. If the given edge is tighter |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
57 * than the current, the current tightest is returned. Otherwise, the edge itself is |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
58 * returned. The returned edge would be the one to remove from the graph. |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
59 * @param candidate another edge |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
60 * @return the edge which is not the tightest edge |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
61 * @since 3.1 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
62 */ |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
63 Edge processEdge(Edge candidate) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
64 collapsedCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
65 if (candidate.getSlack() < tightestEdge.getSlack()) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
66 overage += collapsedWeight * (tightestEdge.getSlack() - candidate.getSlack()); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
67 Edge temp = tightestEdge; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
68 tightestEdge = candidate; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
69 collapsedWeight += candidate.weight; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
70 return temp; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
71 } else { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
72 int over = candidate.getSlack() - tightestEdge.getSlack(); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
73 unOverage += over; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
74 overage += candidate.weight * over; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
75 collapsedWeight += candidate.weight; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
76 return candidate; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
77 } |
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 } |