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

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