--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dwtx/draw2d/graph/BreakCycles.d	Sun Aug 03 00:52:14 2008 +0200
@@ -0,0 +1,280 @@
+/*******************************************************************************
+ * Copyright (c) 2003, 2005 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.BreakCycles;
+
+import dwt.dwthelper.utils;
+import dwtx.dwtxhelper.Collection;
+import dwtx.draw2d.graph.GraphVisitor;
+import dwtx.draw2d.graph.NodeList;
+import dwtx.draw2d.graph.DirectedGraph;
+import dwtx.draw2d.graph.Node;
+import dwtx.draw2d.graph.Edge;
+
+/**
+ * This visitor eliminates cycles in the graph using a "greedy" heuristic.  Nodes which
+ * are sources and sinks are marked and placed in a source and sink list, leaving only
+ * nodes involved in cycles. A remaining node with the highest (outgoing-incoming) edges
+ * score is then chosen greedily as if it were a source. The process is repeated until all
+ * nodes have been marked and placed in a list.  The lists are then concatenated, and any
+ * edges which go backwards in this list will be inverted during the layout procedure.
+ *
+ * @author Daniel Lee
+ * @since 2.1.2
+ */
+class BreakCycles : GraphVisitor {
+
+// Used in identifying cycles and in cycle removal.
+// Flag field indicates "presence". If true, the node has been removed from the list.
+NodeList graphNodes;
+
+public this(){
+    graphNodes = new NodeList();
+}
+
+private bool allNodesFlagged() {
+    for (int i = 0; i < graphNodes.size(); i++) {
+        if (graphNodes.getNode(i).flag is false)
+            return false;
+    }
+    return true;
+}
+
+private void breakCycles(DirectedGraph g) {
+    initializeDegrees(g);
+    greedyCycleRemove(g);
+    invertEdges(g);
+}
+
+/*
+ * Returns true if g contains cycles, false otherwise
+ */
+private bool containsCycles(DirectedGraph g) {
+    List noLefts = new ArrayList();
+    //Identify all initial nodes for removal
+    for (int i = 0; i < graphNodes.size(); i++) {
+        Node node = graphNodes.getNode(i);
+        if (getIncomingCount(node) is 0)
+            sortedInsert(noLefts, node);
+    }
+
+    while (noLefts.size() > 0) {
+        Node node = cast(Node)noLefts.remove(noLefts.size() - 1);
+        node.flag = true;
+        for (int i = 0; i < node.outgoing.size(); i++) {
+            Node right = node.outgoing.getEdge(i).target;
+            setIncomingCount(right, getIncomingCount(right) - 1);
+            if (getIncomingCount(right) is 0)
+                sortedInsert(noLefts, right);
+        }
+    }
+
+    if (allNodesFlagged())
+        return false;
+    return true;
+}
+
+/*
+ * Returns the node in graphNodes with the largest
+ * (outgoing edge count - incoming edge count) value
+ */
+private Node findNodeWithMaxDegree() {
+    int max = Integer.MIN_VALUE;
+    Node maxNode = null;
+
+    for (int i = 0; i < graphNodes.size(); i++) {
+        Node node = graphNodes.getNode(i);
+        if (getDegree(node) >= max && node.flag is false) {
+            max = getDegree(node);
+            maxNode = node;
+        }
+    }
+    return maxNode;
+}
+
+private int getDegree(Node n) {
+    return n.workingInts[3];
+}
+
+private int getIncomingCount(Node n) {
+    return n.workingInts[0];
+}
+
+private int getInDegree(Node n) {
+    return n.workingInts[1];
+}
+
+private int getOrderIndex(Node n) {
+    return n.workingInts[0];
+}
+
+private int getOutDegree(Node n) {
+    return n.workingInts[2];
+}
+
+private void greedyCycleRemove(DirectedGraph g) {
+    NodeList sL = new NodeList();
+    NodeList sR = new NodeList();
+
+    do {
+        // Add all sinks and isolated nodes to sR
+        bool hasSink;
+        do {
+            hasSink = false;
+            for (int i = 0; i < graphNodes.size(); i++) {
+                Node node = graphNodes.getNode(i);
+                if (getOutDegree(node) is 0 && node.flag is false) {
+                    hasSink = true;
+                    node.flag = true;
+                    updateIncoming(node);
+                    sR.add(node);
+                    break;
+                }
+            }
+        } while (hasSink);
+
+        // Add all sources to sL
+        bool hasSource;
+        do {
+            hasSource = false;
+            for (int i = 0; i < graphNodes.size(); i++) {
+                Node node = graphNodes.getNode(i);
+                if (getInDegree(node) is 0 && node.flag is false) {
+                    hasSource = true;
+                    node.flag = true;
+                    updateOutgoing(node);
+                    sL.add(node);
+                    break;
+                }
+            }
+        } while (hasSource);
+
+        // When all sinks and sources are removed, choose a node with the
+        // maximum degree (outDegree - inDegree) and add it to sL
+        Node max = findNodeWithMaxDegree();
+        if (max !is null) {
+            sL.add(max);
+            max.flag = true;
+            updateIncoming(max);
+            updateOutgoing(max);
+        }
+    } while (!allNodesFlagged());
+
+    // Assign order indexes
+    int orderIndex = 0;
+    for (int i = 0; i < sL.size(); i++) {
+        setOrderIndex(sL.getNode(i), orderIndex++);
+    }
+    for (int i = sR.size() - 1; i >= 0; i--) {
+        setOrderIndex(sR.getNode(i), orderIndex++);
+    }
+}
+
+private void initializeDegrees(DirectedGraph g) {
+    graphNodes.resetFlags();
+    for (int i = 0; i < g.nodes.size(); i++) {
+        Node n = graphNodes.getNode(i);
+        setInDegree(n, n.incoming.size());
+        setOutDegree(n, n.outgoing.size());
+        setDegree(n, n.outgoing.size() - n.incoming.size());
+    }
+}
+
+private void invertEdges(DirectedGraph g) {
+    for (int i = 0; i < g.edges.size(); i++) {
+        Edge e = g.edges.getEdge(i);
+        if (getOrderIndex(e.source) > getOrderIndex(e.target)) {
+            e.invert();
+            e.isFeedback_ = true;
+        }
+    }
+}
+
+private void setDegree(Node n, int deg) {
+    n.workingInts[3] = deg;
+}
+
+private void setIncomingCount(Node n, int count) {
+    n.workingInts[0] = count;
+}
+
+private void setInDegree(Node n, int deg) {
+    n.workingInts[1] = deg;
+}
+
+private void setOutDegree(Node n, int deg) {
+    n.workingInts[2] = deg;
+}
+
+private void setOrderIndex(Node n, int index) {
+    n.workingInts[0] = index;
+}
+
+private void sortedInsert(List list, Node node) {
+    int insert = 0;
+    while (insert < list.size()
+      && (cast(Node)list.get(insert)).sortValue > node.sortValue)
+        insert++;
+    list.add(insert, node);
+}
+
+/*
+ * Called after removal of n. Updates the degree values of n's incoming nodes.
+ */
+private void updateIncoming(Node n) {
+    for (int i = 0; i < n.incoming.size(); i++) {
+        Node in_ = n.incoming.getEdge(i).source;
+        if (in_.flag is false) {
+            setOutDegree(in_, getOutDegree(in_) - 1);
+            setDegree(in_, getOutDegree(in_) - getInDegree(in_));
+        }
+    }
+}
+
+/*
+ * Called after removal of n. Updates the degree values of n's outgoing nodes.
+ */
+private void updateOutgoing(Node n) {
+    for (int i = 0; i < n.outgoing.size(); i++) {
+        Node out_ = n.outgoing.getEdge(i).target;
+        if (out_.flag is false) {
+            setInDegree(out_, getInDegree(out_) - 1);
+            setDegree(out_, getOutDegree(out_) - getInDegree(out_));
+        }
+    }
+}
+
+public void revisit(DirectedGraph g) {
+    for (int i = 0; i < g.edges.size(); i++) {
+        Edge e = g.edges.getEdge(i);
+        if (e.isFeedback())
+            e.invert();
+    }
+}
+
+/**
+ * @see GraphVisitor#visit(dwtx.draw2d.graph.DirectedGraph)
+ */
+public void visit(DirectedGraph g) {
+    // put all nodes in list, initialize index
+    graphNodes.resetFlags();
+    for (int i = 0; i < g.nodes.size(); i++) {
+        Node n = g.nodes.getNode(i);
+        setIncomingCount(n, n.incoming.size());
+        graphNodes.add(n);
+    }
+    if (containsCycles(g)) {
+        breakCycles(g);
+    }
+}
+
+}