Attachment 35274 Details for Bug 129257 – BreakCycles.java

BreakCycles.java

BreakCycles.java (text/plain), 7.54 KB, created by Jennifer Cormier

on 2006-02-23 18:41:35 EST

(hide)

Description:

Filename:

MIME Type:

Creator: Jennifer Cormier

Created: 2006-02-23 18:41:35 EST

Size: 7.54 KB

patch

obsolete

>/*******************************************************************************
> * 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
> *******************************************************************************/
>package org.eclipse.draw2d.internal.graph;
>
>import java.util.ArrayList;
>import java.util.List;
>
>import org.eclipse.draw2d.graph.DirectedGraph;
>import org.eclipse.draw2d.graph.Edge;
>import org.eclipse.draw2d.graph.Node;
>import org.eclipse.draw2d.graph.NodeList;
>
>/**
> * 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
> */
>public class BreakCycles extends 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 = new NodeList();
>
>private boolean allNodesFlagged() {
>	for (int i = 0; i < graphNodes.size(); i++) {
>		if (graphNodes.getNode(i).flag == 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 boolean 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) == 0)	
>			sortedInsert(noLefts, node);
>	}
>	
>	while (noLefts.size() > 0) {
>		Node node = (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) == 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 == 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
>		boolean hasSink;
>		do {
>			hasSink = false;
>			for (int i = 0; i < graphNodes.size(); i++) {
>				Node node = graphNodes.getNode(i);
>				if (getOutDegree(node) == 0 && node.flag == false) {
>					hasSink = true;
>					node.flag = true;
>					updateIncoming(node);
>					sR.add(node);
>					break;
>				}
>			}	
>		} while (hasSink);
>		
>		// Add all sources to sL
>		boolean hasSource;
>		do {
>			hasSource = false;
>			for (int i = 0; i < graphNodes.size(); i++) {	
>				Node node = graphNodes.getNode(i);
>				if (getInDegree(node) == 0 && node.flag == 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 != 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()
>	  && ((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 == 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 == false) {
>			setInDegree(out, getInDegree(out) - 1);
>			setDegree(out, getOutDegree(out) - getInDegree(out));
>		}
>	}
>}
>
>/**
> * @see GraphVisitor#visit(org.eclipse.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);
>	}
>}
>
>/* (non-Javadoc)
> * @see com.atc_nycorp.iFUSE.dataflow.views.graphlayout.draw2dinternal.GraphVisitor#revisit(org.eclipse.draw2d.graph.DirectedGraph)
> */
>@Override
>public void revisit(DirectedGraph g) {
>	// Bug fix:  
>	// Edges with virtual nodes are not properly inverted so we prevent 
>	// them from being inverted during InvertEdges.visit() and instead invert them here.
>	for (int i = 0; i < g.edges.size(); i++) {
>		Edge e = g.edges.getEdge(i);
>		if ( e.isFeedback )
>			e.invert();
>	}
>	super.revisit(g);
>}
>
>}

Actions: View

Attachments on bug 129257: 35274 | 35275