1 package org.simantics.debug.graphical.layout;
\r
3 import gnu.trove.list.array.TIntArrayList;
\r
4 import gnu.trove.map.hash.TObjectIntHashMap;
\r
6 import java.util.ArrayList;
\r
8 import org.simantics.debug.graphical.model.Edge;
\r
9 import org.simantics.debug.graphical.model.Node;
\r
11 public class LayoutGraph {
\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
17 private static void computeForces(Node[] nodes, Edge[] edges) {
\r
18 for(Node node : nodes) {
\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
38 for(int i=0;i<nodes.length;++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
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
53 double l = Math.sqrt(l2);
\r
55 double fx = Q * dx / l3;
\r
56 double fy = Q * dy / l3;
\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
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
78 int[][] neighbors = new int[nodes.length][];
\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
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
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
106 for(int i=0;i<nodes.length;++i) {
\r
107 nodes[i].setPos(posX[i], posY[i]);
\r
111 private static void removeDuplicates(TIntArrayList l) {
\r
113 int length = l.size();
\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
124 while(length > tgt) {
\r
125 l.removeAt(length);
\r
130 public static void layoutOld(Node[] nodes, Edge[] edges) {
\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
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
155 double forceX = -G * x;
\r
156 double forceY = -G * y;
\r
160 ArrayList<Node> ns = neighbors[i];
\r
161 idS -= K * ns.size();
\r
163 forceX -= K * (x - n.getX());
\r
164 forceY -= K * (y - n.getY());
\r
168 double xx=0.0, xy=0.0, yy=0.0;
\r
169 for(int j=0;j<nodes.length;++j)
\r
172 double dx = x - n.getX();
\r
173 double dy = y - n.getY();
\r
174 double l2 = dx*dx + dy*dy;
\r
176 double l = Math.sqrt(l2);
\r
180 xx -= Q*dx*dx / l5;
\r
181 xy -= Q*dx*dy / l5;
\r
182 yy -= Q*dy*dy / l5;
\r
184 forceX += Q * dx / l3;
\r
185 forceY += Q * dy / l3;
\r
192 System.out.println("force"+i+" = (" + forceX + ", " + forceY + ")");
\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