bundles/org.simantics.debug.graphical/src/org/simantics/debug/graphical/layout/LayoutGraph.java

   1 package org.simantics.debug.graphical.layout;
   2
   3 import gnu.trove.list.array.TIntArrayList;
   4 import gnu.trove.map.hash.TObjectIntHashMap;
   5
   6 import java.util.ArrayList;
   7
   8 import org.simantics.debug.graphical.model.Edge;
   9 import org.simantics.debug.graphical.model.Node;
  10
  11 public class LayoutGraph {
  12
  13     static final double G = 0.001;
  14     static final double K = 0.001;
  15     static final double Q = 10000.0;
  16
  17     private static void computeForces(Node[] nodes, Edge[] edges) {
  18         for(Node node : nodes) {
  19             node.forceX = 0.0;
  20             node.forceY = 0.0;
  21         }
  22
  23         for(Edge edge : edges) {
  24             Node a = edge.getA();
  25             Node b = edge.getB();
  26             double ax = a.getX();
  27             double ay = a.getY();
  28             double bx = b.getX();
  29             double by = b.getY();
  30             double fx = K * (bx - ax);
  31             double fy = K * (by - ay);
  32             a.forceX += fx;
  33             a.forceY += fy;
  34             b.forceX -= fx;
  35             b.forceY -= fy;
  36         }
  37
  38         for(int i=0;i<nodes.length;++i) {
  39             Node a = nodes[i];
  40             a.forceX -= a.getX()*G;
  41             a.forceY -= a.getY()*G;
  42             for(int j=i+1;j<nodes.length;++j) {
  43                 Node b = nodes[j];
  44
  45                 double ax = a.getX();
  46                 double ay = a.getY();
  47                 double bx = b.getX();
  48                 double by = b.getY();
  49                 double dx = bx - ax;
  50                 double dy = by - ay;
  51                 double l2 = dx*dx + dy*dy;
  52                 if(l2 > 0.1) {
  53                     double l = Math.sqrt(l2);
  54                     double l3 = l*l2;
  55                     double fx = Q * dx / l3;
  56                     double fy = Q * dy / l3;
  57                     a.forceX -= fx;
  58                     a.forceY -= fy;
  59                     b.forceX += fx;
  60                     b.forceY += fy;
  61                 }
  62             }
  63         }
  64     }
  65
  66     public static void layout(Node[] nodes, Edge[] edges) {
  67         /*for(int iter=0;iter<100;++iter) {
  68             computeForces(nodes, edges);
  69             for(Node node : nodes) {
  70                 node.setPos(node.getX() + node.forceX*10.0, node.getY() + node.forceY*10.0);
  71             }
  72         } */
  73
  74         TObjectIntHashMap<Node> nodeIds = new TObjectIntHashMap<Node>();
  75         for(int i=0;i<nodes.length;++i)
  76             nodeIds.put(nodes[i], i);
  77
  78         int[][] neighbors = new int[nodes.length][];
  79         {
  80             TIntArrayList[] neighborLists = new TIntArrayList[nodes.length];
  81             for(int i=0;i<neighborLists.length;++i)
  82                 neighborLists[i] = new TIntArrayList();
  83             for(Edge edge : edges) {
  84                 Node a = edge.getA();
  85                 Node b = edge.getB();
  86                 int aId = nodeIds.get(a);
  87                 int bId = nodeIds.get(b);
  88                 neighborLists[aId].add(bId);
  89                 neighborLists[bId].add(aId);
  90             }
  91             for(int i=0;i<neighborLists.length;++i) {
  92                 TIntArrayList l = neighborLists[i];
  93                 removeDuplicates(l);
  94                 neighbors[i] = l.toArray();
  95             }
  96         }
  97
  98         LayoutAlgorithm algo = new LayoutAlgorithm(neighbors);
  99         double[] posX = algo.getPosX();
 100         double[] posY = algo.getPosY();
 101         for(int i=0;i<nodes.length;++i) {
 102             posX[i] = nodes[i].getX();
 103             posY[i] = nodes[i].getY();
 104         }
 105         algo.optimize();
 106         for(int i=0;i<nodes.length;++i) {
 107             nodes[i].setPos(posX[i], posY[i]);
 108         }
 109     }
 110
 111     private static void removeDuplicates(TIntArrayList l) {
 112         l.sort();
 113         int length = l.size();
 114         int tgt = 0;
 115         int tgtValue=l.get(tgt);
 116         for(int src=1;src<length;++src) {
 117             int srcValue = l.get(src);
 118             if(srcValue != tgtValue) {
 119                 tgtValue = srcValue;
 120                 l.set(++tgt, tgtValue);
 121             }
 122         }
 123         --length;
 124         while(length > tgt) {
 125             l.removeAt(length);
 126             --length;
 127         }
 128     }
 129
 130     public static void layoutOld(Node[] nodes, Edge[] edges) {
 131
 132         // Neighborhood array
 133         TObjectIntHashMap<Node> nodeIds = new TObjectIntHashMap<Node>();
 134         for(int i=0;i<nodes.length;++i)
 135             nodeIds.put(nodes[i], i);
 136         @SuppressWarnings("unchecked")
 137         ArrayList<Node>[] neighbors = new ArrayList[nodes.length];
 138         for(int i=0;i<neighbors.length;++i)
 139             neighbors[i] = new ArrayList<Node>();
 140         for(Edge edge : edges) {
 141             Node a = edge.getA();
 142             Node b = edge.getB();
 143             neighbors[nodeIds.get(a)].add(b);
 144             neighbors[nodeIds.get(b)].add(a);
 145         }
 146
 147         // Iteration
 148         for(int iter=0;iter<1;++iter) {
 149             for(int i=0;i<nodes.length;++i) {
 150                 Node node = nodes[i];
 151                 double x = node.getX();
 152                 double y = node.getY();
 153
 154                 // Gravitation
 155                 double forceX = -G * x;
 156                 double forceY = -G * y;
 157                 double idS = -G;
 158
 159                 // Attraction
 160                 ArrayList<Node> ns = neighbors[i];
 161                 idS -= K * ns.size();
 162                 for(Node n : ns) {
 163                     forceX -= K * (x - n.getX());
 164                     forceY -= K * (y - n.getY());
 165                 }
 166
 167                 // Repulsion
 168                 double xx=0.0, xy=0.0, yy=0.0;
 169                 for(int j=0;j<nodes.length;++j)
 170                     if(i != j) {
 171                         Node n = nodes[j];
 172                         double dx = x - n.getX();
 173                         double dy = y - n.getY();
 174                         double l2 = dx*dx + dy*dy;
 175                         if(l2 > 0.01) {
 176                             double l = Math.sqrt(l2);
 177                             double l3 = l*l2;
 178                             idS += Q / l3;
 179                             double l5 = l3*l2;
 180                             xx -= Q*dx*dx / l5;
 181                             xy -= Q*dx*dy / l5;
 182                             yy -= Q*dy*dy / l5;
 183
 184                             forceX += Q * dx / l3;
 185                             forceY += Q * dy / l3;
 186                         }
 187                     }
 188
 189                 xx += idS;
 190                 yy += idS;
 191
 192                 System.out.println("force"+i+" = (" + forceX + ", " + forceY + ")");
 193
 194                 // Solve
 195                 double det = xx * yy - xy * xy;
 196                 System.out.println("mx"+i+" = (" + xx + "," + xy + "," + yy + ") " + det);
 197                 if(Math.abs(det) > 1e-6) {
 198                     double dx = (yy * forceX - xy * forceY) / det;
 199                     double dy = (xx * forceY - xy * forceX) / det;
 200                     node.setPos(x-dx*0.5, y-dy*0.5);
 201                 }
 202             }
 203         }
 204     }
 205
 206 }