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

   1 /*
   2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3 * of California
   4 * All rights reserved.
   5 *
   6 * This software is open-source under the BSD license; see either
   7 * "license.txt" or
   8 * http://jung.sourceforge.net/license.txt for a description.
   9 */
  10 package edu.uci.ics.jung.algorithms.layout;
  11
  12 import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
  13 import edu.uci.ics.jung.algorithms.util.IterativeContext;
  14 import edu.uci.ics.jung.graph.Graph;
  15
  16 import org.apache.commons.collections15.Factory;
  17 import org.apache.commons.collections15.map.LazyMap;
  18
  19 import java.awt.geom.Point2D;
  20 import java.util.ArrayList;
  21 import java.util.Collection;
  22 import java.util.ConcurrentModificationException;
  23 import java.util.HashMap;
  24 import java.util.List;
  25 import java.util.Map;
  26
  27 /**
  28  * Implements a self-organizing map layout algorithm, based on Meyer's
  29  * self-organizing graph methods.
  30  *
  31  * @author Yan Biao Boey
  32  */
  33 public class ISOMLayout<V, E> extends AbstractLayout<V,E> implements IterativeContext {
  34
  35         Map<V, ISOMVertexData> isomVertexData =
  36                 LazyMap.decorate(new HashMap<V, ISOMVertexData>(),
  37                                 new Factory<ISOMVertexData>() {
  38                                         public ISOMVertexData create() {
  39                                                 return new ISOMVertexData();
  40                                         }});
  41
  42         private int maxEpoch;
  43         private int epoch;
  44
  45         private int radiusConstantTime;
  46         private int radius;
  47         private int minRadius;
  48
  49         private double adaption;
  50         private double initialAdaption;
  51         private double minAdaption;
  52
  53     protected GraphElementAccessor<V,E> elementAccessor =
  54         new RadiusGraphElementAccessor<V,E>();
  55
  56         private double coolingFactor;
  57
  58         private List<V> queue = new ArrayList<V>();
  59         private String status = null;
  60
  61         /**
  62          * Returns the current number of epochs and execution status, as a string.
  63          */
  64         public String getStatus() {
  65                 return status;
  66         }
  67
  68         /**
  69          * Creates an <code>ISOMLayout</code> instance for the specified graph <code>g</code>.
  70          * @param g
  71          */
  72         public ISOMLayout(Graph<V,E> g) {
  73                 super(g);
  74         }
  75
  76         public void initialize() {
  77
  78                 setInitializer(new RandomLocationTransformer<V>(getSize()));
  79                 maxEpoch = 2000;
  80                 epoch = 1;
  81
  82                 radiusConstantTime = 100;
  83                 radius = 5;
  84                 minRadius = 1;
  85
  86                 initialAdaption = 90.0D / 100.0D;
  87                 adaption = initialAdaption;
  88                 minAdaption = 0;
  89
  90                 //factor = 0; //Will be set later on
  91                 coolingFactor = 2;
  92
  93                 //temperature = 0.03;
  94                 //initialJumpRadius = 100;
  95                 //jumpRadius = initialJumpRadius;
  96
  97                 //delay = 100;
  98         }
  99
 100
 101         /**
 102         * Advances the current positions of the graph elements.
 103         */
 104         public void step() {
 105                 status = "epoch: " + epoch + "; ";
 106                 if (epoch < maxEpoch) {
 107                         adjust();
 108                         updateParameters();
 109                         status += " status: running";
 110
 111                 } else {
 112                         status += "adaption: " + adaption + "; ";
 113                         status += "status: done";
 114 //                      done = true;
 115                 }
 116         }
 117
 118         private synchronized void adjust() {
 119                 //Generate random position in graph space
 120                 Point2D tempXYD = new Point2D.Double();
 121
 122                 // creates a new XY data location
 123         tempXYD.setLocation(10 + Math.random() * getSize().getWidth(),
 124                 10 + Math.random() * getSize().getHeight());
 125
 126                 //Get closest vertex to random position
 127                 V winner = elementAccessor.getVertex(this, tempXYD.getX(), tempXYD.getY());
 128
 129                 while(true) {
 130                     try {
 131                         for(V v : getGraph().getVertices()) {
 132                             ISOMVertexData ivd = getISOMVertexData(v);
 133                             ivd.distance = 0;
 134                             ivd.visited = false;
 135                         }
 136                         break;
 137                     } catch(ConcurrentModificationException cme) {}
 138         }
 139                 adjustVertex(winner, tempXYD);
 140         }
 141
 142         private synchronized void updateParameters() {
 143                 epoch++;
 144                 double factor = Math.exp(-1 * coolingFactor * (1.0 * epoch / maxEpoch));
 145                 adaption = Math.max(minAdaption, factor * initialAdaption);
 146                 //jumpRadius = (int) factor * jumpRadius;
 147                 //temperature = factor * temperature;
 148                 if ((radius > minRadius) && (epoch % radiusConstantTime == 0)) {
 149                         radius--;
 150                 }
 151         }
 152
 153         private synchronized void adjustVertex(V v, Point2D tempXYD) {
 154                 queue.clear();
 155                 ISOMVertexData ivd = getISOMVertexData(v);
 156                 ivd.distance = 0;
 157                 ivd.visited = true;
 158                 queue.add(v);
 159                 V current;
 160
 161                 while (!queue.isEmpty()) {
 162                         current = queue.remove(0);
 163                         ISOMVertexData currData = getISOMVertexData(current);
 164                         Point2D currXYData = transform(current);
 165
 166                         double dx = tempXYD.getX() - currXYData.getX();
 167                         double dy = tempXYD.getY() - currXYData.getY();
 168                         double factor = adaption / Math.pow(2, currData.distance);
 169
 170                         currXYData.setLocation(currXYData.getX()+(factor*dx), currXYData.getY()+(factor*dy));
 171
 172                         if (currData.distance < radius) {
 173                             Collection<V> s = getGraph().getNeighbors(current);
 174                             while(true) {
 175                                 try {
 176                                         for(V child : s) {
 177                                         ISOMVertexData childData = getISOMVertexData(child);
 178                                         if (childData != null && !childData.visited) {
 179                                             childData.visited = true;
 180                                             childData.distance = currData.distance + 1;
 181                                             queue.add(child);
 182                                         }
 183                                     }
 184                                     break;
 185                                 } catch(ConcurrentModificationException cme) {}
 186                             }
 187                         }
 188                 }
 189         }
 190
 191         protected ISOMVertexData getISOMVertexData(V v) {
 192                 return isomVertexData.get(v);
 193         }
 194
 195         /**
 196          * This one is an incremental visualization.
 197          * @return <code>true</code> is the layout algorithm is incremental, <code>false</code> otherwise
 198          */
 199         public boolean isIncremental() {
 200                 return true;
 201         }
 202
 203         /**
 204          * Returns <code>true</code> if the vertex positions are no longer being
 205          * updated.  Currently <code>ISOMLayout</code> stops updating vertex
 206          * positions after a certain number of iterations have taken place.
 207          * @return <code>true</code> if the vertex position updates have stopped,
 208          * <code>false</code> otherwise
 209          */
 210         public boolean done() {
 211                 return epoch >= maxEpoch;
 212         }
 213
 214         protected static class ISOMVertexData {
 215                 int distance;
 216                 boolean visited;
 217
 218                 protected ISOMVertexData() {
 219                     distance = 0;
 220                     visited = false;
 221                 }
 222         }
 223
 224         /**
 225          * Resets the layout iteration count to 0, which allows the layout algorithm to
 226          * continue updating vertex positions.
 227          */
 228         public void reset() {
 229                 epoch = 0;
 230         }
 231 }