001/*
002 * Copyright 2006 - 2013
003 *     Stefan Balev     <stefan.balev@graphstream-project.org>
004 *     Julien Baudry    <julien.baudry@graphstream-project.org>
005 *     Antoine Dutot    <antoine.dutot@graphstream-project.org>
006 *     Yoann Pigné      <yoann.pigne@graphstream-project.org>
007 *     Guilhelm Savin   <guilhelm.savin@graphstream-project.org>
008 * 
009 * This file is part of GraphStream <http://graphstream-project.org>.
010 * 
011 * GraphStream is a library whose purpose is to handle static or dynamic
012 * graph, create them from scratch, file or any source and display them.
013 * 
014 * This program is free software distributed under the terms of two licenses, the
015 * CeCILL-C license that fits European law, and the GNU Lesser General Public
016 * License. You can  use, modify and/ or redistribute the software under the terms
017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
019 * the Free Software Foundation, either version 3 of the License, or (at your
020 * option) any later version.
021 * 
022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
024 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
025 * 
026 * You should have received a copy of the GNU Lesser General Public License
027 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
028 * 
029 * The fact that you are presently reading this means that you have had
030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
031 */
032package org.graphstream.ui.layout;
033
034import java.io.IOException;
035import java.util.HashMap;
036import java.util.Iterator;
037import java.util.Random;
038
039import org.graphstream.algorithm.generator.BarabasiAlbertGenerator;
040import org.graphstream.graph.implementations.DefaultGraph;
041import org.graphstream.stream.PipeBase;
042import org.graphstream.ui.geom.Point3;
043import org.miv.pherd.geom.Vector3;
044
045public class Eades84Layout extends PipeBase implements Layout {
046
047        boolean is3D;
048
049        double c1;
050        double c2;
051        double c3;
052        double c4;
053
054        double M;
055
056        HashMap<String, Spring> springs;
057        HashMap<String, EadesParticle> particles;
058
059        Random random;
060
061        int nodeMoved = 0;
062//      LinkedList<LayoutListener> listeners;
063        double stabilization = 0;
064
065        Point3 high;
066        Point3 low;
067
068        public Eades84Layout() {
069                //
070                // Appropriate for most graphs :
071                //
072                c1 = 2;
073                c2 = 1;
074                c3 = 2;
075                c4 = 0.5;
076                M = 100;
077                //
078
079                is3D = false;
080
081                springs = new HashMap<String, Spring>();
082                particles = new HashMap<String, EadesParticle>();
083                random = new Random();
084//              listeners = new LinkedList<LayoutListener>();
085
086                high = new Point3(1, 1, 1);
087                low = new Point3(-1, -1, -1);
088        }
089
090        public String getLayoutAlgorithmName() {
091                return "Eades1984";
092        }
093
094        public int getNodeMovedCount() {
095                return nodeMoved;
096        }
097
098        public double getStabilization() {
099                return stabilization;
100        }
101
102        public double getStabilizationLimit() {
103                return M;
104        }
105
106        public void setStabilizationLimit(double l) {
107                M = l;
108        }
109
110        public Point3 getLowPoint() {
111                return low;
112        }
113
114        public Point3 getHiPoint() {
115                return high;
116        }
117
118        public int getSteps() {
119                // TODO Auto-generated method stub
120                return 0;
121        }
122
123        public long getLastStepTime() {
124                // TODO Auto-generated method stub
125                return 0;
126        }
127
128        public double getQuality() {
129                // TODO Auto-generated method stub
130                return 0;
131        }
132
133        public double getForce() {
134                // TODO Auto-generated method stub
135                return 0;
136        }
137
138        public void clear() {
139                // TODO Auto-generated method stub
140
141        }
142
143//      public void addListener(LayoutListener listener) {
144//              listeners.add(listener);
145//      }
146//
147//      public void removeListener(LayoutListener listener) {
148//              listeners.remove(listener);
149//      }
150
151        public void setForce(double value) {
152                // TODO Auto-generated method stub
153
154        }
155
156        public void setQuality(double qualityLevel) {
157                // TODO Auto-generated method stub
158
159        }
160
161        public void setSendNodeInfos(boolean send) {
162                // TODO Auto-generated method stub
163
164        }
165
166        public void shake() {
167                // TODO Auto-generated method stub
168
169        }
170
171        public void moveNode(String id, double x, double y, double z) {
172                // TODO Auto-generated method stub
173
174        }
175
176        public void freezeNode(String id, boolean frozen) {
177                // TODO Auto-generated method stub
178
179        }
180
181        public void compute() {
182                nodeMoved = 0;
183
184                for (Spring s : springs.values())
185                        s.computeForce();
186
187                for (EadesParticle p : particles.values())
188                        p.step();
189
190                double minx, miny, minz, maxx, maxy, maxz;
191
192                minx = miny = minz = Double.MAX_VALUE;
193                maxx = maxy = maxz = Double.MIN_VALUE;
194
195                for (EadesParticle p : particles.values()) {
196                        p.commit();
197
198                        if (p.getEnergy() > 0)
199                                particleMoved(p.id, p.pos.x, p.pos.y, p.pos.z);
200
201                        minx = Math.min(minx, p.pos.x);
202                        miny = Math.min(miny, p.pos.y);
203                        minz = Math.min(minz, p.pos.z);
204                        maxx = Math.max(minx, p.pos.x);
205                        maxy = Math.max(miny, p.pos.y);
206                        maxz = Math.max(minz, p.pos.z);
207                }
208
209                high.x = maxx;
210                high.y = maxy;
211                high.z = maxz;
212
213                low.x = minx;
214                low.y = miny;
215                low.z = minz;
216
217                stabilization += 1;
218
219//              for (LayoutListener listener : listeners)
220//                      listener.stepCompletion(getStabilization());
221        }
222
223        public void nodeAdded(String sourceId, long timeId, String nodeId) {
224                particles.put(nodeId, getNewParticle(nodeId));
225                stabilization = 0;
226        }
227
228        public void nodeRemoved(String sourceId, long timeId, String nodeId) {
229                particles.remove(nodeId);
230                stabilization = 0;
231        }
232
233        public void edgeAdded(String sourceId, long timeId, String edgeId,
234                        String fromNodeId, String toNodeId, boolean directed) {
235                EadesParticle p1, p2;
236                Spring spring;
237
238                p1 = (EadesParticle) particles.get(fromNodeId);
239                p2 = (EadesParticle) particles.get(toNodeId);
240
241                spring = getNewSpring(p1, p2);
242                springs.put(edgeId, spring);
243
244                p1.springs.put(p2, spring);
245                p2.springs.put(p1, spring);
246
247                stabilization = 0;
248        }
249
250        public void edgeRemoved(String sourceId, long timeId, String edgeId) {
251                Spring s = springs.remove(edgeId);
252
253                if (s != null) {
254                        s.p1.springs.remove(s.p2);
255                        s.p2.springs.remove(s.p1);
256
257                        stabilization = 0;
258                }
259        }
260
261        public void inputPos(String filename) throws IOException {
262                throw new RuntimeException("unhandle feature");
263        }
264
265        public void outputPos(String filename) throws IOException {
266                throw new RuntimeException("unhandle feature");
267        }
268
269        public void particleMoved(Object id, double x, double y, double z) {
270                //for (LayoutListener listener : listeners)
271                //      listener.nodeMoved((String) id, x, y, z);
272
273                Object xyz[] = new Object[3];
274                xyz[0] = x;
275                xyz[1] = y;
276                xyz[2] = z;
277
278                sendNodeAttributeChanged(getLayoutAlgorithmName(), (String) id, "xyz",
279                                xyz, xyz);
280
281                // System.out.printf("particle %s moved : %f;%f;%f\n", id, x, y, z);
282        }
283
284        protected EadesParticle getNewParticle(String id) {
285                return new EadesParticle(id);
286        }
287
288        protected Spring getNewSpring(EadesParticle p1, EadesParticle p2) {
289                return new Spring(p1, p2);
290        }
291
292        protected class Spring {
293                EadesParticle p1;
294                EadesParticle p2;
295
296                double force;
297
298                Spring(EadesParticle p1, EadesParticle p2) {
299                        this.p1 = p1;
300                        this.p2 = p2;
301                }
302
303                /**
304                 * Force of a spring is : c1 * log(d/c2)
305                 */
306                void computeForce() {
307                        double d = p1.d(p2);
308                        force = c1 * Math.log(d / c2);
309                }
310
311                void set(EadesParticle p, Vector3 v) {
312                        v.set(Math.signum(p2.getPosition().x - p1.getPosition().x),
313                                        Math.signum(p2.getPosition().y - p1.getPosition().y),
314                                        Math.signum(p2.getPosition().z - p1.getPosition().z));
315
316                        if (p == p2)
317                                v.scalarMult(-1);
318
319                        v.scalarMult(force);
320                }
321        }
322
323        protected class EadesParticle {
324                HashMap<EadesParticle, Spring> springs;
325                Vector3 dir;
326                Vector3 sum;
327                Point3 pos;
328                String id;
329
330                public EadesParticle(String id) {
331                        this.id = id;
332                        springs = new HashMap<EadesParticle, Spring>();
333                        dir = new Vector3();
334                        sum = new Vector3();
335                        pos = new Point3();
336
337                        pos.x = random.nextDouble() * (high.x - low.x) + low.x;
338                        pos.y = random.nextDouble() * (high.y - low.y) + low.y;
339
340                        if (is3D)
341                                pos.z = random.nextDouble() * (high.z - low.z) + low.z;
342                }
343
344                public void step() {
345                        Vector3 v = new Vector3();
346
347                        dir.fill(0);
348                        sum.fill(0);
349
350                        for (Spring s : springs.values()) {
351                                s.set(this, v);
352                                sum.add(v);
353                        }
354
355                        // if (springs.size() > 0)
356                        // sum.scalarDiv(springs.size());
357                        // dir.add(sum);
358
359                        // sum.fill(0);
360
361                        Iterator<EadesParticle> it = particles.values().iterator();
362                        //double i = 0;
363
364                        while (it.hasNext()) {
365                                EadesParticle p = it.next();
366
367                                if (!springs.containsKey(p) && p != this) {
368                                        double d = d(p);
369                                        /*
370                                         * Force of a non-spring particle : c3 / sqrt(d)
371                                         */
372                                        double f = Double.isNaN(d) ? c3 : c3 / Math.sqrt(d);
373
374                                        v.set(Math.signum(getPosition().x - p.getPosition().x),
375                                                        Math.signum(getPosition().y - p.getPosition().y),
376                                                        Math.signum(getPosition().z - p.getPosition().z));
377
378                                        v.scalarMult(f);
379
380                                        sum.add(v);
381                                        //i++;
382                                }
383                        }
384
385                        //if (i + springs.size() > 0)
386                        //      sum.scalarDiv(i + springs.size());
387
388                        dir.add(sum);
389                        dir.scalarMult(c4);
390
391                        assert (!Double.isNaN(dir.data[0]) && !Double.isNaN(dir.data[1]));
392                }
393
394                public double getEnergy() {
395                        return dir.length();
396                }
397
398                public void commit() {
399                        pos.x = pos.x + dir.data[0];
400                        pos.y = pos.y + dir.data[1];
401
402                        assert (!Double.isNaN(pos.x) && !Double.isNaN(pos.y));
403
404                        if (is3D)
405                                pos.z = pos.z + dir.data[2];
406
407                        nodeMoved++;
408                }
409
410                protected double d(EadesParticle p) {
411                        return getPosition().distance(p.getPosition());
412                }
413
414                public Point3 getPosition() {
415                        return pos;
416                }
417        }
418
419        public static void main(String... args) {
420                DefaultGraph g = new DefaultGraph("g");
421                BarabasiAlbertGenerator gen = new BarabasiAlbertGenerator();
422                Eades84Layout layout = new Eades84Layout();
423
424                int size = 30;
425
426                gen.addSink(g);
427                g.addSink(layout);
428                layout.addAttributeSink(g);
429
430                g.display(false);
431
432                gen.begin();
433                while (size-- > 0)
434                        gen.nextEvents();
435                gen.end();
436
437                while (true) {
438                        layout.compute();
439                        try {
440                                Thread.sleep(50);
441                        } catch (Exception e) {
442                        }
443                }
444        }
445}