/*******************************************************************************
 * Copyright (c) 2003, 2007 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 * Port to the D programming language:
 *     Frank Benoit <benoit@tionex.de>
 *******************************************************************************/
module dwtx.draw2d.graph.CompoundDirectedGraphLayout;

import dwt.dwthelper.utils;
import dwtx.draw2d.graph.DirectedGraphLayout;
import dwtx.draw2d.graph.TransposeMetrics;
import dwtx.draw2d.graph.CompoundBreakCycles;
import dwtx.draw2d.graph.RouteEdges;
import dwtx.draw2d.graph.ConvertCompoundGraph;
import dwtx.draw2d.graph.InitialRankSolver;
import dwtx.draw2d.graph.TightSpanningTreeSolver;
import dwtx.draw2d.graph.RankAssignmentSolver;
import dwtx.draw2d.graph.CompoundPopulateRanks;
import dwtx.draw2d.graph.CompoundVerticalPlacement;
import dwtx.draw2d.graph.MinCross;
import dwtx.draw2d.graph.CompoundRankSorter;
import dwtx.draw2d.graph.SortSubgraphs;
import dwtx.draw2d.graph.CompoundHorizontalPlacement;

/**
 * Performs a graph layout on a <code>CompoundDirectedGraph</code>.  The input format is
 * the same as for {@link DirectedGraphLayout}.  All nodes, including subgraphs and their
 * children, should be added to the {@link DirectedGraph#nodes} field.
 * <P>
 * The requirements for this algorithm are the same as those of
 * <code>DirectedGraphLayout</code>, with the following exceptions:
 * <UL>
 *    <LI>There is an implied edge between a subgraph and each of its member nodes. These
 *    edges form the containment graph <EM>T</EM>. Thus, the compound directed graph
 *    <EM>CG</EM> is said to be connected iff Union(<EM>G</EM>, <EM>T</EM>) is connected,
 *    where G represents the given nodes (including subgraphs) and edges.
 *
 *    <LI>This algorithm will remove any compound cycles found in the input graph
 *    <em>G</em> by inverting edges according to a heuristic until no more cycles are
 *    found. A compound cycle is defined as: a cycle comprised of edges from <EM>G</EM>,
 *    <EM>T</EM>, and <em>T<SUP>-1</SUP></em>, in the form
 *    (c<SUP>*</SUP>e<SUP>+</SUP>p<SUP>*</SUP>e<SUP>+</SUP>)*, where
 *    <em>T<SUP>-1</SUP></em> is the backwards graph of <EM>T</EM>, c element of T, e
 *    element of G, and p element of T<SUP>-1</SUP>.
 * </UL>
 *
 * @author Randy Hudson
 * @since 2.1.2
 */
public final class CompoundDirectedGraphLayout : DirectedGraphLayout {

void init() {
    steps.add(new TransposeMetrics());
    steps.add(new CompoundBreakCycles());
    steps.add(new RouteEdges());
    steps.add(new ConvertCompoundGraph());
    steps.add(new InitialRankSolver());
    steps.add(new TightSpanningTreeSolver());
    steps.add(new RankAssignmentSolver());
    steps.add(new CompoundPopulateRanks());
    steps.add(new CompoundVerticalPlacement());
    steps.add(new MinCross(new CompoundRankSorter()));
    steps.add(new SortSubgraphs());
    steps.add(new CompoundHorizontalPlacement());
}

}