Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/CompoundPopulateRanks.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.CompoundPopulateRanks;
14
15 import dwt.dwthelper.utils;
16 import dwtx.dwtxhelper.Collection;
17 import dwtx.draw2d.graph.PopulateRanks;
18 import dwtx.draw2d.graph.DirectedGraph;
19 import dwtx.draw2d.graph.Subgraph;
20 import dwtx.draw2d.graph.CompoundDirectedGraph;
21 import dwtx.draw2d.graph.Edge;
22 import dwtx.draw2d.graph.NodeList;
23 import dwtx.draw2d.graph.Node;
24
25 /**
26 * Places nodes into ranks for a compound directed graph. If a subgraph spans a rank
27 * without any nodes which belong to that rank, a bridge node is inserted to prevent nodes
28 * from violating the subgraph boundary.
29 * @author Randy Hudson
30 * @since 2.1.2
31 */
32 class CompoundPopulateRanks : PopulateRanks {
33
34 public void visit(DirectedGraph g) {
35 CompoundDirectedGraph graph = cast(CompoundDirectedGraph)g;
36
37 /**
38 * Remove long containment edges at this point so they don't affect MinCross.
39 */
40 Iterator containment = graph.containment.iterator();
41 while (containment.hasNext()) {
42 Edge e = cast(Edge)containment.next();
43 if (e.getSlack() > 0) {
44 graph.removeEdge(e);
45 containment.remove();
46 }
47 }
48
49 super.visit(g);
50 NodeList subgraphs = graph.subgraphs;
51 for (int i = 0; i < subgraphs.size(); i++) {
52 Subgraph subgraph = cast(Subgraph)subgraphs.get(i);
53 bridgeSubgraph(subgraph, graph);
54 }
55 }
56
57 /**
58 * @param subgraph
59 */
60 private void bridgeSubgraph(Subgraph subgraph, CompoundDirectedGraph g) {
61 int offset = subgraph.head.rank;
62 bool occupied[] = new bool[subgraph.tail.rank - subgraph.head.rank + 1];
63 Node bridge[] = new Node[occupied.length];
64
65 for (int i = 0; i < subgraph.members.size(); i++) {
66 Node n = cast(Node)subgraph.members.get(i);
67 if (auto s = cast(Subgraph)n ) {
68 for (int r = s.head.rank; r <= s.tail.rank; r++)
69 occupied[r - offset] = true;
70 } else
71 occupied[n.rank - offset] = true;
72 }
73
74 for (int i = 0; i < bridge.length; i++) {
75 if (!occupied[i]) {
76 Node br = bridge[i] = new Node(stringcast("bridge"), subgraph); //$NON-NLS-1$
77 br.rank = i + offset;
78 br.height = br.width = 0;
79 br.nestingIndex = subgraph.nestingIndex;
80 g.ranks.getRank(br.rank).add(br);
81 g.nodes.add(br);
82 }
83 }
84 }
85
86 }