/* Copyright (c) 1998-2006 The Regents of the University of California All rights reserved. Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software. IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. PT_COPYRIGHT_VERSION_2 COPYRIGHTENDKEY */ package diva.graph.layout; import java.awt.geom.Line2D; import java.awt.geom.Rectangle2D; import java.util.HashMap; import java.util.Iterator; import java.util.Random; import diva.graph.GraphModel; /** * A simple layout which places nodes on a grid using a cost function. * It performs the following simple-minded algorithm: * *
* EDGE_COST(e) = [ * HEIGHT(e) + * WIDTH(e) + * ELBOW_PENALTY(e) + * EDGE_OVERLAP_PENALTY * num_overlap(e) + * CROSSING_PENALTY * num_crossing(e) * ] **/ protected double edgeCost(Object edge) { GraphModel model = getLayoutTarget().getGraphModel(); Object tail = model.getTail(edge); Object head = model.getHead(edge); head = _getParentInGraph(head); tail = _getParentInGraph(tail); if ((head == null) || (tail == null)) { return 0; } int[] ptail = getXY(tail); int[] phead = getXY(head); double heightCost = HEIGHT_FACTOR * Math.abs(phead[1] - ptail[1]); double widthCost = WIDTH_FACTOR * Math.abs(phead[0] - ptail[0]); double elbowCost = ((heightCost == 0) || (widthCost == 0)) ? 0 : ELBOW_PENALTY; double overlapCost = numOverlaps(edge, _graph) * EDGE_OVERLAP_PENALTY; double crossingCost = numCrossings(edge, _graph) * CROSSING_PENALTY; return heightCost + widthCost + elbowCost + overlapCost + crossingCost; } /** * @see #setCoolingFactor(double) */ public double getCoolingFactor() { return _cool; } /** * @see #setIterationCount(int) */ public int getIterationCount(int cnt) { return _numIters; } /** * @see #setMoveCount(int) */ public int getMoveCount(int cnt) { return _numIters; } /** * Return the sparseness value of this layout; the default value * is 1.0. * * @see #setSparseness(double) */ public double getSparseness() { return _sparseness; } /** * Return the logical X, Y positions of the given * node as an integer array of length 2. */ protected int[] getXY(Object node) { return (int[]) _map.get(node); } /** * Initialize the grid and randomly assign nodes to vertices of * the grid. The grid initialization is based on the aspect ratio * of the viewport in which the layout is being performed. In * particular the following algorithm is used: * *
* GH = H/W * sqrt(N) * SPARSENESS ** * Where H and W are the height and width of the viewport, N is * the number of nodes in the graph, and SPARSENESS is some * measure of the sparseness of the layout. A SPARSENESS of 1 * will mean that the graph is tightly packed, and the packing * amount decreases linearly with the SPARSENESS value. * * @see #setSparseness(double) */ protected void initGrid() { GraphModel model = getLayoutTarget().getGraphModel(); int nodeCount = model.getNodeCount(_graph); if (nodeCount > 0) { Rectangle2D dim = getLayoutTarget().getViewport(_graph); double aspect = dim.getHeight() / dim.getWidth(); double gh = Math.sqrt(nodeCount * aspect) * _sparseness; //debug("aspect=" + aspect); //debug("gh=" + gh); // Fix the number of vertical nodes. _gh = (int) Math.ceil(gh); // Infer the number of horizontal nodes. _gw = nodeCount / _gh; while ((_gh * _gw) < nodeCount) { _gw++; } _grid = new Object[_gw][_gh]; Iterator nodes = model.nodes(_graph); for (int x = 0; x < _gw; x++) { for (int y = 0; y < _gh; y++) { if (!nodes.hasNext()) { break; } setXY(nodes.next(), x, y); } } } } /** * Perform the annealing layout algorithm on the given graph * in the context of the given layout target. */ public void layout(Object composite) { LayoutTarget target = getLayoutTarget(); _graph = composite; _map = new HashMap(); if (target.getGraphModel().getNodeCount(_graph) > 0) { initGrid(); // Avoid exceptions if the graph is not visible. if ((_gh == 0) || (_gw == 0)) { return; } anneal(); assignLayout(); cleanupStructures(); } } /** * Return the absolute cost of an individual node. By default the * cost function is: * *
* NODE_COST(n) = SUM [ EDGE_COST(n.edge(i)) ] + * TEE_PENALTY * num_tee(g) **/ protected double nodeCost(Object node) { LayoutTarget target = getLayoutTarget(); GraphModel model = target.getGraphModel(); if (node == null) { return 0; } int cost = 0; for (Iterator i = model.inEdges(node); i.hasNext();) { cost += edgeCost(i.next()); } for (Iterator i = model.outEdges(node); i.hasNext();) { cost += edgeCost(i.next()); } double teeCost = numTees(_graph) * TEE_PENALTY; cost += teeCost; return cost; } /** * Return the number of crossings between this edge and other * edges in the graph. */ protected final int numCrossings(Object inEdge, Object composite) { int num = 0; GraphModel model = getLayoutTarget().getGraphModel(); Object inTail = model.getTail(inEdge); Object inHead = model.getHead(inEdge); inHead = _getParentInGraph(inHead); inTail = _getParentInGraph(inTail); if ((inHead == null) || (inTail == null)) { return 0; } int[] inTailPt = getXY(inTail); int[] inHeadPt = getXY(inHead); for (Iterator i = model.nodes(composite); i.hasNext();) { Object node = i.next(); for (Iterator j = model.outEdges(node); j.hasNext();) { Object edge = j.next(); Object tail = model.getTail(edge); Object head = model.getHead(edge); if ((tail == null) || (head == null) || (tail == inTail) || (tail == inHead) || (head == inTail) || (head == inHead)) { //these cannot cross continue; } int[] tailPt = getXY(tail); int[] headPt = getXY(head); if (Line2D.linesIntersect(inTailPt[0], inTailPt[1], inHeadPt[0], inHeadPt[1], tailPt[0], tailPt[1], headPt[0], headPt[1])) { num++; } } } // debug("\tEdge crossings: " + in + ", " + num); return num; } /** * Return the number of instances of nodes that are being placed * on top of edges that they are not connected to. */ protected final int numTees(Object composite) { return 0; //XXX } /** * Return the number of overlaps between this edge and other edges * in the graph. For now, simply test to see if the lines are * horizontal or vertical and overlap with each other. */ protected final int numOverlaps(Object inEdge, Object composite) { int num = 0; GraphModel model = getLayoutTarget().getGraphModel(); Object inTail = model.getTail(inEdge); Object inHead = model.getHead(inEdge); inHead = _getParentInGraph(inHead); inTail = _getParentInGraph(inTail); if ((inHead == null) || (inTail == null)) { return 0; } int[] inTailPt = getXY(inTail); int[] inHeadPt = getXY(inHead); for (int which = 0; which < 2; which++) { if (inTailPt[which] == inHeadPt[which]) { for (Iterator i = model.nodes(composite); i.hasNext();) { Object node = i.next(); for (Iterator j = model.outEdges(node); j.hasNext();) { Object edge = j.next(); Object tail = model.getTail(edge); Object head = model.getHead(edge); head = _getParentInGraph(head); tail = _getParentInGraph(tail); if ((head != null) && (tail != null)) { int[] tailPt = getXY(tail); int[] headPt = getXY(head); if ((tailPt[which] == headPt[which]) && (tailPt[which] == inTailPt[which])) { //int other = which + (1 % 2); // test to see if the "other" coordinate is // *between* the two points. num++; } } } } break; } } // debug("\tEdge overlaps: " + in + ", " + num); return num; } /** * Set the cooling factor to be a value greater than 0 and less * than or equal to 1. The cooling factor determines how quickly * the annealing "settles"; the lower the factor, the faster the * annealing settles. The Default value is .95. */ public void setCoolingFactor(double val) { if ((val <= 0) || (val > 1)) { String err = "Cooling factor must be greater than 0 and less or equal to 1: " + val; throw new IllegalArgumentException(err); } _cool = val; } /** * Set the number of iterations to cool over. Default value is 100. */ public void setIterationCount(int cnt) { _numIters = cnt; } /** * Set the number of moves per iteration. Default value is 10. */ public void setMoveCount(int cnt) { _numIters = cnt; } /** * Set the sparseness of this layout. A sparseness of 1.0 will * mean that the graph is tightly packed, and the packing amount * decreases linearly with the SPARSENESS value. */ public void setSparseness(double val) { if (val < 1.0) { String err = "Illegal sparseness value: " + val; throw new IllegalArgumentException(err); } _sparseness = val; } /** * Set the logical X, Y positions of the given node. */ protected void setXY(Object node, int x, int y) { int[] pos = (int[]) _map.get(node); if (pos == null) { pos = new int[2]; _map.put(node, pos); } _grid[x][y] = node; pos[0] = x; pos[1] = y; } /** * Take a snapshot of the minimum cost arrangement of the nodes, * so that we can backtrack to it later. */ private void snapMin() { if (_minGrid == null) { _minGrid = new Object[_gw][_gh]; } for (int x = 0; x < _gw; x++) { for (int y = 0; y < _gh; y++) { _minGrid[x][y] = _grid[x][y]; } } } /** * Swap the two nodes' grid positions. */ private void swap(Object node1, Object node2) { // debug("SWAP: " + node1 + ", " + node2); int xtmp; // debug("SWAP: " + node1 + ", " + node2); int ytmp; int[] xy1 = getXY(node1); int[] xy2 = getXY(node2); xtmp = xy1[0]; ytmp = xy1[1]; setXY(node1, xy2[0], xy2[1]); setXY(node2, xtmp, ytmp); } // Unfortunately, the head and/or tail of the edge may not // be directly contained in the graph. In this case, we need to // figure out which of their parents IS in the graph and calculate the // cost of that instead. private Object _getParentInGraph(Object node) { GraphModel model = getLayoutTarget().getGraphModel(); while ((node != null) && !model.containsNode(_graph, node)) { Object parent = model.getParent(node); if (model.isNode(parent)) { node = parent; } else { node = null; } } return node; } }