Mercurial > projects > dwt-addons

annotate dwtx/draw2d/graph/CompoundDirectedGraphLayout.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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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, 2007 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.CompoundDirectedGraphLayout;
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.DirectedGraphLayout;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
17 import dwtx.draw2d.graph.TransposeMetrics;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
18 import dwtx.draw2d.graph.CompoundBreakCycles;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
19 import dwtx.draw2d.graph.RouteEdges;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
20 import dwtx.draw2d.graph.ConvertCompoundGraph;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
21 import dwtx.draw2d.graph.InitialRankSolver;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
22 import dwtx.draw2d.graph.TightSpanningTreeSolver;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
23 import dwtx.draw2d.graph.RankAssignmentSolver;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
24 import dwtx.draw2d.graph.CompoundPopulateRanks;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
25 import dwtx.draw2d.graph.CompoundVerticalPlacement;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
26 import dwtx.draw2d.graph.MinCross;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
27 import dwtx.draw2d.graph.CompoundRankSorter;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
28 import dwtx.draw2d.graph.SortSubgraphs;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
29 import dwtx.draw2d.graph.CompoundHorizontalPlacement;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
30
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
31 /**
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
32 * Performs a graph layout on a <code>CompoundDirectedGraph</code>. The input format is
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
33 * the same as for {@link DirectedGraphLayout}. All nodes, including subgraphs and their
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
34 * children, should be added to the {@link DirectedGraph#nodes} field.
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
35 * <P>
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
36 * The requirements for this algorithm are the same as those of
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
37 * <code>DirectedGraphLayout</code>, with the following exceptions:
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
38 * <UL>
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
39 * <LI>There is an implied edge between a subgraph and each of its member nodes. These
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
40 * edges form the containment graph <EM>T</EM>. Thus, the compound directed graph
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
41 * <EM>CG</EM> is said to be connected iff Union(<EM>G</EM>, <EM>T</EM>) is connected,
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
42 * where G represents the given nodes (including subgraphs) and edges.
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 * <LI>This algorithm will remove any compound cycles found in the input graph
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
45 * <em>G</em> by inverting edges according to a heuristic until no more cycles are
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
46 * found. A compound cycle is defined as: a cycle comprised of edges from <EM>G</EM>,
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
47 * <EM>T</EM>, and <em>T<SUP>-1</SUP></em>, in the form
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
48 * (c<SUP>*</SUP>e<SUP>+</SUP>p<SUP>*</SUP>e<SUP>+</SUP>)*, where
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
49 * <em>T<SUP>-1</SUP></em> is the backwards graph of <EM>T</EM>, c element of T, e
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
50 * element of G, and p element of T<SUP>-1</SUP>.
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
51 * </UL>
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
52 *
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
53 * @author Randy Hudson
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
54 * @since 2.1.2
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 public final class CompoundDirectedGraphLayout : DirectedGraphLayout {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
57
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
58 void init() {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
59 steps.add(new TransposeMetrics());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
60 steps.add(new CompoundBreakCycles());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
61 steps.add(new RouteEdges());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
62 steps.add(new ConvertCompoundGraph());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
63 steps.add(new InitialRankSolver());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
64 steps.add(new TightSpanningTreeSolver());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
65 steps.add(new RankAssignmentSolver());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
66 steps.add(new CompoundPopulateRanks());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
67 steps.add(new CompoundVerticalPlacement());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
68 steps.add(new MinCross(new CompoundRankSorter()));
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
69 steps.add(new SortSubgraphs());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
70 steps.add(new CompoundHorizontalPlacement());
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
71 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
72
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
73 }