bundles/org.eclipse.draw2d/src/org/eclipse/draw2d/graph/ConvertCompoundGraph.java

/*******************************************************************************
 * Copyright (c) 2003, 2010 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.graph;

import org.eclipse.draw2d.geometry.Insets;

/**
 * Converts a compound directed graph into a simple directed graph.
 * 
 * @author Randy Hudson
 * @since 2.1.2
 */
class ConvertCompoundGraph extends GraphVisitor {

	private void addContainmentEdges(CompoundDirectedGraph graph) {
		// For all nested nodes, connect to head and/or tail of containing
		// subgraph if present
		for (int i = 0; i < graph.nodes.size(); i++) {
			Node node = graph.nodes.getNode(i);
			Subgraph parent = node.getParent();
			if (parent == null)
				continue;
			if (node instanceof Subgraph) {
				Subgraph sub = (Subgraph) node;
				connectHead(graph, sub.head, parent);
				connectTail(graph, sub.tail, parent);
			} else {
				connectHead(graph, node, parent);
				connectTail(graph, node, parent);
			}
		}
	}

	int buildNestingTreeIndices(NodeList nodes, int base) {
		for (int i = 0; i < nodes.size(); i++) {
			Node node = (Node) nodes.get(i);
			if (node instanceof Subgraph) {
				Subgraph s = (Subgraph) node;
				s.nestingTreeMin = base;
				base = buildNestingTreeIndices(s.members, base);
			}
			node.nestingIndex = base++;
		}
		return base++;
	}

	private void connectHead(CompoundDirectedGraph graph, Node node,
			Subgraph parent) {
		boolean connectHead = true;
		for (int j = 0; connectHead && j < node.incoming.size(); j++) {
			Node ancestor = node.incoming.getEdge(j).source;
			if (parent.isNested(ancestor))
				connectHead = false;
		}
		if (connectHead) {
			Edge e = new Edge(parent.head, node);
			e.weight = 0;
			graph.edges.add(e);
			graph.containment.add(e);
		}
	}

	private void connectTail(CompoundDirectedGraph graph, Node node,
			Subgraph parent) {
		boolean connectTail = true;
		for (int j = 0; connectTail && j < node.outgoing.size(); j++) {
			Node ancestor = node.outgoing.getEdge(j).target;
			if (parent.isNested(ancestor))
				connectTail = false;
		}
		if (connectTail) {
			Edge e = new Edge(node, parent.tail);
			e.weight = 0;
			graph.edges.add(e);
			graph.containment.add(e);
		}
	}

	private void convertSubgraphEndpoints(CompoundDirectedGraph graph) {
		for (int i = 0; i < graph.edges.size(); i++) {
			Edge edge = (Edge) graph.edges.get(i);
			if (edge.source instanceof Subgraph) {
				Subgraph s = (Subgraph) edge.source;
				Node newSource;
				if (s.isNested(edge.target))
					newSource = s.head;
				else
					newSource = s.tail;
				// s.outgoing.remove(edge);
				edge.source = newSource;
				newSource.outgoing.add(edge);
			}
			if (edge.target instanceof Subgraph) {
				Subgraph s = (Subgraph) edge.target;
				Node newTarget;
				if (s.isNested(edge.source))
					newTarget = s.tail;
				else
					newTarget = s.head;

				// s.incoming.remove(edge);
				edge.target = newTarget;
				newTarget.incoming.add(edge);
			}
		}
	}

	private void replaceSubgraphsWithBoundaries(CompoundDirectedGraph graph) {
		for (int i = 0; i < graph.subgraphs.size(); i++) {
			Subgraph s = (Subgraph) graph.subgraphs.get(i);
			graph.nodes.add(s.head);
			graph.nodes.add(s.tail);
			graph.nodes.remove(s);
		}
	}

	void revisit(DirectedGraph g) {
		for (int i = 0; i < g.edges.size(); i++) {
			Edge e = g.edges.getEdge(i);
			if (e.source instanceof SubgraphBoundary) {
				e.source.outgoing.remove(e);
				e.source = e.source.getParent();
			}
			if (e.target instanceof SubgraphBoundary) {
				e.target.incoming.remove(e);
				e.target = e.target.getParent();
			}
		}
	}

	/**
	 * @see GraphVisitor#visit(org.eclipse.draw2d.graph.DirectedGraph)
	 */
	public void visit(DirectedGraph dg) {
		CompoundDirectedGraph graph = (CompoundDirectedGraph) dg;

		NodeList roots = new NodeList();
		// Find all subgraphs and root subgraphs
		for (int i = 0; i < graph.nodes.size(); i++) {
			Object node = graph.nodes.get(i);
			if (node instanceof Subgraph) {
				Subgraph s = (Subgraph) node;
				Insets padding = dg.getPadding(s);
				s.head = new SubgraphBoundary(s, padding, 0);
				s.tail = new SubgraphBoundary(s, padding, 2);
				Edge headToTail = new Edge(s.head, s.tail);
				headToTail.weight = 10;
				graph.edges.add(headToTail);
				graph.containment.add(headToTail);

				graph.subgraphs.add(s);
				if (s.getParent() == null)
					roots.add(s);
				if (s.members.size() == 2) // The 2 being the head and tail only
					graph.edges.add(new Edge(s.head, s.tail));
			}
		}

		buildNestingTreeIndices(roots, 0);
		convertSubgraphEndpoints(graph);
		addContainmentEdges(graph);
		replaceSubgraphsWithBoundaries(graph);
	}

}