third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/BalloonLayout.java

   1 /*
   2  * Copyright (c) 2005, the JUNG Project and the Regents of the University of
   3  * California All rights reserved.
   4  *
   5  * This software is open-source under the BSD license; see either "license.txt"
   6  * or http://jung.sourceforge.net/license.txt for a description.
   7  *
   8  * Created on Jul 9, 2005
   9  */
  10
  11 package edu.uci.ics.jung.algorithms.layout;
  12 import java.awt.Dimension;
  13 import java.awt.geom.Point2D;
  14 import java.util.ArrayList;
  15 import java.util.HashMap;
  16 import java.util.List;
  17 import java.util.Map;
  18
  19 import org.apache.commons.collections15.Transformer;
  20 import org.apache.commons.collections15.map.LazyMap;
  21
  22 import edu.uci.ics.jung.graph.Forest;
  23 import edu.uci.ics.jung.graph.util.TreeUtils;
  24
  25 /**
  26  * A {@code Layout} implementation that assigns positions to {@code Tree} or
  27  * {@code Forest} vertices using associations with nested circles ("balloons").
  28  * A balloon is nested inside another balloon if the first balloon's subtree
  29  * is a subtree of the second balloon's subtree.
  30  *
  31  * @author Tom Nelson
  32  *
  33  */
  34 public class BalloonLayout<V,E> extends TreeLayout<V,E> {
  35
  36     protected Map<V,PolarPoint> polarLocations =
  37         LazyMap.decorate(new HashMap<V, PolarPoint>(),
  38                         new Transformer<V,PolarPoint>() {
  39                                         public PolarPoint transform(V arg0) {
  40                                                 return new PolarPoint();
  41                                         }});
  42
  43     protected Map<V,Double> radii = new HashMap<V,Double>();
  44
  45     /**
  46      * Creates an instance based on the input forest.
  47      */
  48     public BalloonLayout(Forest<V,E> g)
  49     {
  50         super(g);
  51     }
  52
  53     protected void setRootPolars()
  54     {
  55         List<V> roots = TreeUtils.getRoots(graph);
  56         if(roots.size() == 1) {
  57                 // its a Tree
  58                 V root = roots.get(0);
  59                 setRootPolar(root);
  60             setPolars(new ArrayList<V>(graph.getChildren(root)),
  61                     getCenter(), getSize().width/2);
  62         } else if (roots.size() > 1) {
  63                 // its a Forest
  64                 setPolars(roots, getCenter(), getSize().width/2);
  65         }
  66     }
  67
  68     protected void setRootPolar(V root) {
  69         PolarPoint pp = new PolarPoint(0,0);
  70         Point2D p = getCenter();
  71         polarLocations.put(root, pp);
  72         locations.put(root, p);
  73     }
  74
  75
  76     protected void setPolars(List<V> kids, Point2D parentLocation, double parentRadius) {
  77
  78         int childCount = kids.size();
  79         if(childCount == 0) return;
  80         // handle the 1-child case with 0 limit on angle.
  81         double angle = Math.max(0, Math.PI / 2 * (1 - 2.0/childCount));
  82         double childRadius = parentRadius*Math.cos(angle) / (1 + Math.cos(angle));
  83         double radius = parentRadius - childRadius;
  84
  85         double rand = Math.random();
  86
  87         for(int i=0; i< childCount; i++) {
  88                 V child = kids.get(i);
  89                 double theta = i* 2*Math.PI/childCount + rand;
  90                 radii.put(child, childRadius);
  91
  92                 PolarPoint pp = new PolarPoint(theta, radius);
  93                 polarLocations.put(child, pp);
  94
  95                 Point2D p = PolarPoint.polarToCartesian(pp);
  96                 p.setLocation(p.getX()+parentLocation.getX(), p.getY()+parentLocation.getY());
  97                 locations.put(child, p);
  98                 setPolars(new ArrayList<V>(graph.getChildren(child)), p, childRadius);
  99         }
 100     }
 101
 102     @Override
 103     public void setSize(Dimension size) {
 104         this.size = size;
 105         setRootPolars();
 106     }
 107
 108         /**
 109          * Returns the coordinates of {@code v}'s parent, or the
 110          * center of this layout's area if it's a root.
 111          */
 112         public Point2D getCenter(V v) {
 113                 V parent = graph.getParent(v);
 114                 if(parent == null) {
 115                         return getCenter();
 116                 }
 117                 return locations.get(parent);
 118         }
 119
 120         @Override
 121     public void setLocation(V v, Point2D location) {
 122                 Point2D c = getCenter(v);
 123                 Point2D pv = new Point2D.Double(location.getX()-c.getX(),location.getY()-c.getY());
 124                 PolarPoint newLocation = PolarPoint.cartesianToPolar(pv);
 125                 polarLocations.get(v).setLocation(newLocation);
 126
 127                 Point2D center = getCenter(v);
 128                 pv.setLocation(pv.getX()+center.getX(), pv.getY()+center.getY());
 129                 locations.put(v, pv);
 130         }
 131
 132         @Override
 133     public Point2D transform(V v) {
 134                 return locations.get(v);
 135         }
 136
 137         /**
 138          * @return the radii
 139          */
 140         public Map<V, Double> getRadii() {
 141                 return radii;
 142         }
 143 }