1 package org.simantics.debug.graphical.layout;
3 import gnu.trove.list.array.TIntArrayList;
4 import gnu.trove.map.hash.TObjectIntHashMap;
6 import java.util.ArrayList;
8 import org.simantics.debug.graphical.model.Edge;
9 import org.simantics.debug.graphical.model.Node;
11 public class LayoutGraph {
13 static final double G = 0.001;
14 static final double K = 0.001;
15 static final double Q = 10000.0;
17 private static void computeForces(Node[] nodes, Edge[] edges) {
18 for(Node node : nodes) {
23 for(Edge edge : edges) {
30 double fx = K * (bx - ax);
31 double fy = K * (by - ay);
38 for(int i=0;i<nodes.length;++i) {
40 a.forceX -= a.getX()*G;
41 a.forceY -= a.getY()*G;
42 for(int j=i+1;j<nodes.length;++j) {
51 double l2 = dx*dx + dy*dy;
53 double l = Math.sqrt(l2);
55 double fx = Q * dx / l3;
56 double fy = Q * dy / l3;
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);
74 TObjectIntHashMap<Node> nodeIds = new TObjectIntHashMap<Node>();
75 for(int i=0;i<nodes.length;++i)
76 nodeIds.put(nodes[i], i);
78 int[][] neighbors = new int[nodes.length][];
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) {
86 int aId = nodeIds.get(a);
87 int bId = nodeIds.get(b);
88 neighborLists[aId].add(bId);
89 neighborLists[bId].add(aId);
91 for(int i=0;i<neighborLists.length;++i) {
92 TIntArrayList l = neighborLists[i];
94 neighbors[i] = l.toArray();
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();
106 for(int i=0;i<nodes.length;++i) {
107 nodes[i].setPos(posX[i], posY[i]);
111 private static void removeDuplicates(TIntArrayList l) {
113 int length = l.size();
115 int tgtValue=l.get(tgt);
116 for(int src=1;src<length;++src) {
117 int srcValue = l.get(src);
118 if(srcValue != tgtValue) {
120 l.set(++tgt, tgtValue);
124 while(length > tgt) {
130 public static void layoutOld(Node[] nodes, Edge[] edges) {
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);
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();
155 double forceX = -G * x;
156 double forceY = -G * y;
160 ArrayList<Node> ns = neighbors[i];
161 idS -= K * ns.size();
163 forceX -= K * (x - n.getX());
164 forceY -= K * (y - n.getY());
168 double xx=0.0, xy=0.0, yy=0.0;
169 for(int j=0;j<nodes.length;++j)
172 double dx = x - n.getX();
173 double dy = y - n.getY();
174 double l2 = dx*dx + dy*dy;
176 double l = Math.sqrt(l2);
184 forceX += Q * dx / l3;
185 forceY += Q * dy / l3;
192 System.out.println("force"+i+" = (" + forceX + ", " + forceY + ")");
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);