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