Mercurial > projects > dwt-addons

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