/* * The original file Graph.java (1.5 99/11/29) is * Copyright (c) 1997 Sun Microsystems, Inc. All Rights Reserved. * Adapted by F. Wienberg, 1999 * * Sun grants you ("Licensee") a non-exclusive, royalty free, license to use, * modify and redistribute this software in source and binary code form, * provided that i) this copyright notice and license appear on all copies of * the software; and ii) Licensee does not utilize the software in a manner * which is disparaging to Sun. * * This software is provided "AS IS," without a warranty of any kind. ALL * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING ANY * IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR * NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE * LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING * OR DISTRIBUTING THE SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS * LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, * INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF * OR INABILITY TO USE SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE * POSSIBILITY OF SUCH DAMAGES. * * This software is not designed or intended for use in on-line control of * aircraft, air traffic, aircraft navigation or aircraft communications; or in * the design, construction, operation or maintenance of any nuclear * facility. Licensee represents and warrants that it will not use or * redistribute the Software for such purposes. */ package CH.ifa.draw.util; import java.util.*; import CH.ifa.draw.framework.*; import java.awt.*; public class GraphLayout extends FigureChangeAdapter { public double LENGTH_FACTOR=1.0; public double REPULSION_STRENGTH=0.5; public double REPULSION_LIMIT=200.0; int REPULSION_TYPE=0; // 0: (1-r)/r 1: 1-r 2: (1-r)^2 public double SPRING_STRENGTH=0.1; public double TORQUE_STRENGTH=0.25; public double FRICTION_FACTOR=0.75; private Hashtable nodes = new Hashtable(), edges = new Hashtable(); public GraphLayout() {} private GraphNode getGraphNode(Figure node) { return (GraphNode)nodes.get(node); } private double len(Figure edge) { return ((Double)edges.get(edge)).doubleValue()*LENGTH_FACTOR; } public void addNode(Figure node) { nodes.put(node, new GraphNode(node)); node.addFigureChangeListener(this); } public void addEdge(ConnectionFigure edge, int addlen) { Dimension d1 = edge.start().owner().size(); Dimension d2 = edge.end().owner().size(); int len = Math.max(d1.width,d1.height)/2 + Math.max(d2.width,d2.height)/2 + addlen; edges.put(edge, new Double(len)); } public synchronized void relax() { if (nodes == null) return; Enumeration edgeEnum = edges.keys(); while (edgeEnum.hasMoreElements()) { ConnectionFigure e = (ConnectionFigure)edgeEnum.nextElement(); double targetlen = len(e); GraphNode from = getGraphNode(e.start().owner()); GraphNode to = getGraphNode(e.end().owner()); double vx = to.x - from.x; double vy = to.y - from.y; double len = Math.sqrt(vx * vx + vy * vy); if (len>0) { double f = SPRING_STRENGTH * (targetlen - len) / len; double dx = f * vx; double dy = f * vy; double phi=Math.atan2(vx,vy); double dir=-Math.sin(4*phi); dx += TORQUE_STRENGTH*vy*dir/len; dy += -TORQUE_STRENGTH*vx*dir/len; to.dx += dx; to.dy += dy; from.dx += -dx; from.dy += -dy; } } Enumeration nodeEnum1 = nodes.elements(); while (nodeEnum1.hasMoreElements()) { GraphNode n1 = (GraphNode)nodeEnum1.nextElement(); double dx = 0; double dy = 0; Enumeration nodeEnum2 = nodes.elements(); while (nodeEnum2.hasMoreElements()) { GraphNode n2 = (GraphNode)nodeEnum2.nextElement(); if (n1 == n2) { continue; } double vx = n1.x - n2.x; double vy = n1.y - n2.y; double lensqr = vx * vx + vy * vy; double len = Math.sqrt(lensqr); if (len == 0) { dx += REPULSION_STRENGTH * Math.random(); dy += REPULSION_STRENGTH * Math.random(); } else if (len < REPULSION_LIMIT) { // Normalize length. vx=vx/REPULSION_LIMIT; vy=vy/REPULSION_LIMIT; len=len/REPULSION_LIMIT; // Compute force. double f=0; switch (REPULSION_TYPE) { case 0: f = 0.5 * (1 - len) / len; break; case 1: f = 1 - len; break; case 2: f = 2 * (1 - len) * (1 - len); break; } f *= REPULSION_STRENGTH; dx += f * vx; dy += f * vy; } } n1.dx += dx; n1.dy += dy; } Enumeration nodeEnum = nodes.keys(); while (nodeEnum.hasMoreElements()) { Figure node = (Figure)nodeEnum.nextElement(); GraphNode n = getGraphNode(node); if (!Boolean.TRUE.equals(node.getAttribute("Location"))) { n.x += Math.max(-5, Math.min(5, n.dx)); n.y += Math.max(-5, Math.min(5, n.dy)); Point c = node.center(); node.moveBy((int)Math.round(n.x)-c.x, (int)Math.round(n.y)-c.y); //System.out.println("v= " + n.dx + "," + n.dy); if (n.x < 0) { n.x = 0; } if (n.y < 0) { n.y = 0; } } n.dx *= FRICTION_FACTOR; n.dy *= FRICTION_FACTOR; } } /** * Sent when a figure changed */ synchronized public void figureChanged(FigureChangeEvent e) { if (nodes!=null) { Figure node = e.getFigure(); if (nodes.containsKey(node)) { getGraphNode(node).update(); } } } public void remove() { if (nodes!=null) { Enumeration nodeEnum = nodes.keys(); while (nodeEnum.hasMoreElements()) { Figure node = (Figure)nodeEnum.nextElement(); node.removeFigureChangeListener(this); } nodes = null; edges = null; } } } class GraphNode { double x=0.0, y=0.0; double dx=0.0; double dy=0.0; final Figure node; GraphNode(Figure node) { this.node = node; update(); } void update() { Point p = node.center(); if (Math.abs(p.x - Math.round(x))>1 || Math.abs(p.y - Math.round(y))>1) { x = p.x; y = p.y; //System.out.println(this+" has new coords: "+x+","+y+"\n"); } } }