Mercurial > projects > dwt2
annotate org.eclipse.draw2d/src/org/eclipse/draw2d/graph/CollapsedEdges.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 |
rev | line source |
---|---|
12
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
1 /******************************************************************************* |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
2 * Copyright (c) 2005 IBM Corporation and others. |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
3 * All rights reserved. This program and the accompanying materials |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
4 * are made available under the terms of the Eclipse Public License v1.0 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
5 * which accompanies this distribution, and is available at |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
6 * http://www.eclipse.org/legal/epl-v10.html |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
7 * |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
8 * Contributors: |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
9 * IBM Corporation - initial API and implementation |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
10 * Port to the D programming language: |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
11 * Frank Benoit <benoit@tionex.de> |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
12 *******************************************************************************/ |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
13 module org.eclipse.draw2d.graph.CollapsedEdges; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
14 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
15 import java.lang.all; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
16 import org.eclipse.draw2d.graph.Edge; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
17 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
18 /** |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
19 * Contains the information from all edges going from a given cluster to some other |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
20 * cluster. An edge with minimal slack as chosen to maintain the link between clusters. |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
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 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
22 * edges. |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
23 * @since 3.1 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
24 */ |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
25 class CollapsedEdges { |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
26 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
27 /** |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
28 * The total weight of the collapsed edges. |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
29 */ |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
30 int collapsedWeight; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
31 int collapsedCount; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
32 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
33 /** |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
34 * The total amount of weighted difference in the collapsed edges slack and the |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
35 * tightest edge's slack. |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
36 */ |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
37 int overage; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
38 int unOverage; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
39 Edge tightestEdge; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
40 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
41 this(Edge edge) { |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
42 tightestEdge = edge; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
43 collapsedWeight = edge.weight; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
44 collapsedCount++; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
45 } |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
46 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
47 public int getWeightedPull() { |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
48 return tightestEdge.getSlack() * collapsedWeight + overage; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
49 } |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
50 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
51 public bool isTight() { |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
52 return tightestEdge.getSlack() is 0; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
53 } |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
54 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
55 /** |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
56 * Compares the given edge to the current tightest edge. If the given edge is tighter |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
57 * than the current, the current tightest is returned. Otherwise, the edge itself is |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
58 * returned. The returned edge would be the one to remove from the graph. |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
59 * @param candidate another edge |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
60 * @return the edge which is not the tightest edge |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
61 * @since 3.1 |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
62 */ |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
63 Edge processEdge(Edge candidate) { |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
64 collapsedCount++; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
65 if (candidate.getSlack() < tightestEdge.getSlack()) { |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
66 overage += collapsedWeight * (tightestEdge.getSlack() - candidate.getSlack()); |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
67 Edge temp = tightestEdge; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
68 tightestEdge = candidate; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
69 collapsedWeight += candidate.weight; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
70 return temp; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
71 } else { |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
72 int over = candidate.getSlack() - tightestEdge.getSlack(); |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
73 unOverage += over; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
74 overage += candidate.weight * over; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
75 collapsedWeight += candidate.weight; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
76 return candidate; |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
77 } |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
78 } |
bc29606a740c
Added dwt-addons in original directory structure of eclipse.org
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
79 } |