--- /dev/null
+package org.simantics.debug.graphical.layout;\r
+\r
+import gnu.trove.list.array.TIntArrayList;\r
+import gnu.trove.map.hash.TObjectIntHashMap;\r
+\r
+import java.util.ArrayList;\r
+\r
+import org.simantics.debug.graphical.model.Edge;\r
+import org.simantics.debug.graphical.model.Node;\r
+\r
+public class LayoutGraph {\r
+\r
+ static final double G = 0.001;\r
+ static final double K = 0.001;\r
+ static final double Q = 10000.0;\r
+ \r
+ private static void computeForces(Node[] nodes, Edge[] edges) {\r
+ for(Node node : nodes) {\r
+ node.forceX = 0.0;\r
+ node.forceY = 0.0;\r
+ }\r
+ \r
+ for(Edge edge : edges) {\r
+ Node a = edge.getA();\r
+ Node b = edge.getB();\r
+ double ax = a.getX();\r
+ double ay = a.getY();\r
+ double bx = b.getX();\r
+ double by = b.getY();\r
+ double fx = K * (bx - ax);\r
+ double fy = K * (by - ay);\r
+ a.forceX += fx;\r
+ a.forceY += fy;\r
+ b.forceX -= fx;\r
+ b.forceY -= fy;\r
+ }\r
+ \r
+ for(int i=0;i<nodes.length;++i) { \r
+ Node a = nodes[i];\r
+ a.forceX -= a.getX()*G;\r
+ a.forceY -= a.getY()*G;\r
+ for(int j=i+1;j<nodes.length;++j) {\r
+ Node b = nodes[j];\r
+ \r
+ double ax = a.getX();\r
+ double ay = a.getY();\r
+ double bx = b.getX();\r
+ double by = b.getY();\r
+ double dx = bx - ax;\r
+ double dy = by - ay;\r
+ double l2 = dx*dx + dy*dy;\r
+ if(l2 > 0.1) {\r
+ double l = Math.sqrt(l2);\r
+ double l3 = l*l2;\r
+ double fx = Q * dx / l3;\r
+ double fy = Q * dy / l3;\r
+ a.forceX -= fx;\r
+ a.forceY -= fy;\r
+ b.forceX += fx;\r
+ b.forceY += fy;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ \r
+ public static void layout(Node[] nodes, Edge[] edges) { \r
+ /*for(int iter=0;iter<100;++iter) {\r
+ computeForces(nodes, edges);\r
+ for(Node node : nodes) {\r
+ node.setPos(node.getX() + node.forceX*10.0, node.getY() + node.forceY*10.0);\r
+ }\r
+ } */\r
+ \r
+ TObjectIntHashMap<Node> nodeIds = new TObjectIntHashMap<Node>();\r
+ for(int i=0;i<nodes.length;++i)\r
+ nodeIds.put(nodes[i], i); \r
+ \r
+ int[][] neighbors = new int[nodes.length][];\r
+ {\r
+ TIntArrayList[] neighborLists = new TIntArrayList[nodes.length]; \r
+ for(int i=0;i<neighborLists.length;++i)\r
+ neighborLists[i] = new TIntArrayList();\r
+ for(Edge edge : edges) {\r
+ Node a = edge.getA();\r
+ Node b = edge.getB();\r
+ int aId = nodeIds.get(a);\r
+ int bId = nodeIds.get(b);\r
+ neighborLists[aId].add(bId);\r
+ neighborLists[bId].add(aId);\r
+ } \r
+ for(int i=0;i<neighborLists.length;++i) {\r
+ TIntArrayList l = neighborLists[i]; \r
+ removeDuplicates(l);\r
+ neighbors[i] = l.toArray();\r
+ }\r
+ }\r
+ \r
+ LayoutAlgorithm algo = new LayoutAlgorithm(neighbors);\r
+ double[] posX = algo.getPosX();\r
+ double[] posY = algo.getPosY();\r
+ for(int i=0;i<nodes.length;++i) {\r
+ posX[i] = nodes[i].getX();\r
+ posY[i] = nodes[i].getY();\r
+ }\r
+ algo.optimize();\r
+ for(int i=0;i<nodes.length;++i) {\r
+ nodes[i].setPos(posX[i], posY[i]);\r
+ } \r
+ }\r
+ \r
+ private static void removeDuplicates(TIntArrayList l) {\r
+ l.sort();\r
+ int length = l.size();\r
+ int tgt = 0;\r
+ int tgtValue=l.get(tgt);\r
+ for(int src=1;src<length;++src) {\r
+ int srcValue = l.get(src);\r
+ if(srcValue != tgtValue) {\r
+ tgtValue = srcValue;\r
+ l.set(++tgt, tgtValue);\r
+ }\r
+ }\r
+ --length;\r
+ while(length > tgt) {\r
+ l.removeAt(length);\r
+ --length;\r
+ }\r
+ }\r
+\r
+ public static void layoutOld(Node[] nodes, Edge[] edges) {\r
+ \r
+ // Neighborhood array \r
+ TObjectIntHashMap<Node> nodeIds = new TObjectIntHashMap<Node>();\r
+ for(int i=0;i<nodes.length;++i)\r
+ nodeIds.put(nodes[i], i);\r
+ @SuppressWarnings("unchecked")\r
+ ArrayList<Node>[] neighbors = new ArrayList[nodes.length]; \r
+ for(int i=0;i<neighbors.length;++i)\r
+ neighbors[i] = new ArrayList<Node>();\r
+ for(Edge edge : edges) {\r
+ Node a = edge.getA();\r
+ Node b = edge.getB();\r
+ neighbors[nodeIds.get(a)].add(b);\r
+ neighbors[nodeIds.get(b)].add(a);\r
+ }\r
+ \r
+ // Iteration\r
+ for(int iter=0;iter<1;++iter) {\r
+ for(int i=0;i<nodes.length;++i) {\r
+ Node node = nodes[i];\r
+ double x = node.getX();\r
+ double y = node.getY();\r
+ \r
+ // Gravitation\r
+ double forceX = -G * x;\r
+ double forceY = -G * y;\r
+ double idS = -G;\r
+ \r
+ // Attraction\r
+ ArrayList<Node> ns = neighbors[i];\r
+ idS -= K * ns.size();\r
+ for(Node n : ns) {\r
+ forceX -= K * (x - n.getX());\r
+ forceY -= K * (y - n.getY());\r
+ }\r
+ \r
+ // Repulsion\r
+ double xx=0.0, xy=0.0, yy=0.0;\r
+ for(int j=0;j<nodes.length;++j)\r
+ if(i != j) {\r
+ Node n = nodes[j];\r
+ double dx = x - n.getX();\r
+ double dy = y - n.getY();\r
+ double l2 = dx*dx + dy*dy;\r
+ if(l2 > 0.01) {\r
+ double l = Math.sqrt(l2);\r
+ double l3 = l*l2;\r
+ idS += Q / l3;\r
+ double l5 = l3*l2;\r
+ xx -= Q*dx*dx / l5;\r
+ xy -= Q*dx*dy / l5;\r
+ yy -= Q*dy*dy / l5;\r
+ \r
+ forceX += Q * dx / l3;\r
+ forceY += Q * dy / l3;\r
+ }\r
+ }\r
+ \r
+ xx += idS;\r
+ yy += idS;\r
+ \r
+ System.out.println("force"+i+" = (" + forceX + ", " + forceY + ")"); \r
+ \r
+ // Solve\r
+ double det = xx * yy - xy * xy;\r
+ System.out.println("mx"+i+" = (" + xx + "," + xy + "," + yy + ") " + det);\r
+ if(Math.abs(det) > 1e-6) {\r
+ double dx = (yy * forceX - xy * forceY) / det;\r
+ double dy = (xx * forceY - xy * forceX) / det;\r
+ node.setPos(x-dx*0.5, y-dy*0.5);\r
+ }\r
+ }\r
+ } \r
+ }\r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff