Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/TightSpanningTreeSolver.d @ 98:95307ad235d9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added Draw2d code, still work in progress
author Frank Benoit <benoit@tionex.de>
date Sun, 03 Aug 2008 00:52:14 +0200
parents
children
comparison
equal deleted inserted replaced
96:b492ba44e44d 98:95307ad235d9
1 /*******************************************************************************
2 * Copyright (c) 2003, 2005 IBM Corporation and others.
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors:
9 * IBM Corporation - initial API and implementation
10 * Port to the D programming language:
11 * Frank Benoit <benoit@tionex.de>
12 *******************************************************************************/
13 module dwtx.draw2d.graph.TightSpanningTreeSolver;
14
15 import dwt.dwthelper.utils;
16 import dwtx.draw2d.graph.SpanningTreeVisitor;
17 import dwtx.draw2d.graph.DirectedGraph;
18 import dwtx.draw2d.graph.Edge;
19 import dwtx.draw2d.graph.EdgeList;
20 import dwtx.draw2d.graph.Node;
21 import dwtx.draw2d.graph.NodeList;
22
23 /**
24 * Finds a tight spanning tree from the graphs edges which induce a valid rank assignment.
25 * This process requires that the nodes be initially given a feasible ranking.
26 * @author Randy Hudson
27 * @since 2.1.2
28 */
29 class TightSpanningTreeSolver : SpanningTreeVisitor {
30
31 protected DirectedGraph graph;
32 protected CandidateList candidates;
33
34 static final class CandidateList {
35 private Edge[] edges;
36 private int size_;
37
38 public this(){
39 edges = new Edge[10];
40 }
41 public void add(Edge edge) {
42 if (size_ is edges.length - 1) {
43 Edge newEdges[] = new Edge[edges.length * 2];
44 System.arraycopy(edges, 0, newEdges, 0, edges.length);
45 edges = newEdges;
46 }
47 edges[size_++] = edge;
48 }
49
50 public Edge getEdge(int index) {
51 return edges[index];
52 }
53
54 public void remove(Edge edge) {
55 for (int i = 0; i < size_; i++) {
56 if (edges[i] is edge) {
57 edges[i] = edges[size_ - 1];
58 size_--;
59 return;
60 }
61 }
62 throw new RuntimeException("Remove called on invalid Edge"); //$NON-NLS-1$
63 }
64
65 public int size() {
66 return size_;
67 }
68 }
69
70 protected NodeList members;
71
72 public this(){
73 candidates = new CandidateList();
74 members = new NodeList();
75 }
76
77 public void visit(DirectedGraph graph) {
78 this.graph = graph;
79 init();
80 solve();
81 }
82
83 Node addEdge(Edge edge) {
84 int delta = edge.getSlack();
85 edge.tree = true;
86 Node node;
87 if (edge.target.flag) {
88 delta = -delta;
89 node = edge.source;
90 setParentEdge(node, edge);
91 getSpanningTreeChildren(edge.target).add(edge);
92 } else {
93 node = edge.target;
94 setParentEdge(node, edge);
95 getSpanningTreeChildren(edge.source).add(edge);
96 }
97 members.adjustRank(delta);
98 addNode(node);
99 return node;
100 }
101
102 private bool isNodeReachable(Node node) {
103 return node.flag;
104 }
105
106 private void setNodeReachable(Node node) {
107 node.flag = true;
108 }
109
110 private bool isCandidate(Edge e) {
111 return e.flag;
112 }
113
114 private void setCandidate(Edge e) {
115 e.flag = true;
116 }
117
118 void addNode(Node node) {
119 setNodeReachable(node);
120 EdgeList list = node.incoming;
121 Edge e;
122 for (int i = 0; i < list.size(); i++) {
123 e = list.getEdge(i);
124 if (!isNodeReachable(e.source)) {
125 if (!isCandidate(e)) {
126 setCandidate(e);
127 candidates.add(e);
128 }
129 } else
130 candidates.remove(e);
131 }
132
133 list = node.outgoing;
134 for (int i = 0; i < list.size(); i++) {
135 e = list.getEdge(i);
136 if (!isNodeReachable(e.target)) {
137 if (!isCandidate(e)) {
138 setCandidate(e);
139 candidates.add(e);
140 }
141 } else
142 candidates.remove(e);
143 }
144 members.add(node);
145 }
146
147 void init() {
148 graph.edges.resetFlags(true);
149 graph.nodes.resetFlags();
150 for (int i = 0; i < graph.nodes.size(); i++) {
151 Node node = cast(Node)graph.nodes.get(i);
152 node.workingData[0] = new EdgeList();
153 }
154 }
155
156 protected void solve() {
157 Node root = graph.nodes.getNode(0);
158 setParentEdge(root, null);
159 addNode(root);
160 while (members.size() < graph.nodes.size()) {
161 if (candidates.size() is 0)
162 throw new RuntimeException("graph is not fully connected");//$NON-NLS-1$
163 int minSlack = Integer.MAX_VALUE, slack;
164 Edge minEdge = null, edge;
165 for (int i = 0; i < candidates.size() && minSlack > 0; i++) {
166 edge = candidates.getEdge(i);
167 slack = edge.getSlack();
168 if (slack < minSlack) {
169 minSlack = slack;
170 minEdge = edge;
171 }
172 }
173 addEdge(minEdge);
174 }
175 graph.nodes.normalizeRanks();
176 }
177
178 }