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.Arrays;
036import java.util.Collections;
037import java.util.Comparator;
038import java.util.HashMap;
039import java.util.LinkedList;
040
041import org.graphstream.algorithm.Prim;
042import org.graphstream.algorithm.SpanningTree;
043import org.graphstream.algorithm.generator.BarabasiAlbertGenerator;
044import org.graphstream.algorithm.util.FibonacciHeap;
045import org.graphstream.graph.Edge;
046import org.graphstream.graph.Graph;
047import org.graphstream.graph.Node;
048import org.graphstream.graph.implementations.AdjacencyListGraph;
049import org.graphstream.stream.PipeBase;
050import org.graphstream.ui.geom.Point3;
051import org.graphstream.ui.swingViewer.Viewer;
052
053public class HierarchicalLayout extends PipeBase implements Layout {
054
055        public static enum Rendering {
056                VERTICAL, HORIZONTAL, DISK
057        }
058
059        static class Position {
060                int level;
061                int order;
062                String parent;
063                boolean changed;
064                double x, y;
065
066                Position(int level, int order) {
067                        this.level = level;
068                        this.order = order;
069                        this.changed = true;
070                }
071        }
072
073        final HashMap<String, Position> nodesPosition;
074        final LinkedList<String> roots;
075        final Graph internalGraph;
076
077        boolean structureChanged;
078
079        Rendering renderingType;
080
081        Point3 hi, lo;
082
083        long lastStep;
084
085        int nodeMoved;
086
087        double distanceBetweenLevels = 1;
088        double levelWidth = 1, levelHeight = 1;
089
090        public HierarchicalLayout() {
091                roots = new LinkedList<String>();
092                // listeners = new LinkedList<LayoutListener>();
093                nodesPosition = new HashMap<String, Position>();
094                internalGraph = new AdjacencyListGraph("hierarchical_layout-intern");
095                hi = new Point3();
096                lo = new Point3();
097                renderingType = Rendering.VERTICAL;
098        }
099
100        public void setRoots(String... rootsId) {
101                roots.clear();
102
103                if (rootsId != null) {
104                        for (String id : rootsId)
105                                roots.add(id);
106                }
107        }
108
109        // public void addListener(LayoutListener listener) {
110        // listeners.add(listener);
111        // }
112
113        public void clear() {
114                // TODO Auto-generated method stub
115
116        }
117
118        public void compute() {
119                nodeMoved = 0;
120
121                if (structureChanged) {
122                        structureChanged = false;
123                        computePositions();
124                }
125
126                publishPositions();
127                lastStep = System.currentTimeMillis();
128        }
129
130        protected void computePositions() {
131                final int[] levels = new int[internalGraph.getNodeCount()];
132                Arrays.fill(levels, -1);
133
134                final int[] columns = new int[internalGraph.getNodeCount()];
135
136                LinkedList<Node> roots = new LinkedList<Node>(), roots2 = new LinkedList<Node>();
137
138                if (this.roots.size() > 0) {
139                        for (int i = 0; i < this.roots.size(); i++)
140                                roots.add(internalGraph.getNode(this.roots.get(i)));
141                }
142
143                SpanningTree tree = new Prim("weight", "inTree");
144                tree.init(internalGraph);
145                tree.compute();
146
147                if (roots.size() == 0) {
148                        int max = internalGraph.getNode(0).getDegree();
149                        int maxIndex = 0;
150
151                        for (int i = 1; i < internalGraph.getNodeCount(); i++)
152                                if (internalGraph.getNode(i).getDegree() > max) {
153                                        max = internalGraph.getNode(i).getDegree();
154                                        maxIndex = i;
155                                }
156
157                        roots.add(internalGraph.getNode(maxIndex));
158                }
159
160                Box rootBox = new Box();
161                LevelBox rootLevelBox = new LevelBox(0);
162                LinkedList<LevelBox> levelBoxes = new LinkedList<LevelBox>();
163
164                rootLevelBox.add(rootBox);
165                levelBoxes.add(rootLevelBox);
166
167                for (int i = 0; i < roots.size(); i++) {
168                        Node n = roots.get(i);
169                        levels[n.getIndex()] = 0;
170                        columns[n.getIndex()] = i;
171                        setBox(rootBox, n);
172                }
173
174                do {
175                        while (roots.size() > 0) {
176                                Node root = roots.poll();
177                                int level = levels[root.getIndex()] + 1;
178                                Box box = getChildrenBox(root);
179
180                                for (Edge e : root.getEdgeSet()) {
181                                        if (e.getAttribute(tree.getFlagAttribute()).equals(
182                                                        tree.getFlagOn())) {
183                                                Node op = e.getOpposite(root);
184
185                                                if (levels[op.getIndex()] < 0
186                                                                || level < levels[op.getIndex()]) {
187                                                        levels[op.getIndex()] = level;
188                                                        roots2.add(op);
189                                                        op.setAttribute("parent", root);
190                                                        setBox(box, op);
191                                                }
192                                        }
193                                }
194                        }
195
196                        roots.addAll(roots2);
197                        roots2.clear();
198                } while (roots.size() > 0);
199
200                FibonacciHeap<Integer, Box> boxes = new FibonacciHeap<Integer, Box>();
201                boxes.add(0, rootBox);
202
203                for (int i = 0; i < internalGraph.getNodeCount(); i++) {
204                        Box box = getChildrenBox(internalGraph.getNode(i));
205
206                        if (box != null) {
207                                boxes.add(box.level, box);
208
209                                while (levelBoxes.size() <= box.level)
210                                        levelBoxes.add(new LevelBox(levelBoxes.size()));
211
212                                levelBoxes.get(box.level).add(box);
213                        }
214                }
215
216                for (int i = 0; i < levelBoxes.size(); i++)
217                        levelBoxes.get(i).sort();
218
219                while (boxes.size() > 0)
220                        renderBox(boxes.extractMin());
221
222                hi.x = hi.y = Double.MIN_VALUE;
223                lo.x = lo.y = Double.MAX_VALUE;
224
225                for (int idx = 0; idx < internalGraph.getNodeCount(); idx++) {
226                        Node n = internalGraph.getNode(idx);
227                        double y = n.getNumber("y");
228                        double x = n.getNumber("x");
229
230                        if (!n.hasNumber("oldX") || n.getNumber("oldX") != x
231                                        || !n.hasNumber("oldY") || n.getNumber("oldY") != y) {
232                                n.setAttribute("oldX", x);
233                                n.setAttribute("oldY", y);
234                                n.addAttribute("changed");
235                                nodeMoved++;
236                        }
237
238                        hi.x = Math.max(hi.x, x);
239                        hi.y = Math.max(hi.y, y);
240                        lo.x = Math.min(lo.x, x);
241                        lo.y = Math.min(lo.y, y);
242                }
243        }
244
245        protected void setBox(Box box, Node node) {
246                if (node.hasAttribute("box"))
247                        getBox(node).remove(node);
248
249                box.add(node);
250                node.setAttribute("box", box);
251
252                if (!node.hasAttribute("children"))
253                        node.addAttribute("children", new Box(node, 1));
254
255                getChildrenBox(node).level = box.level + 1;
256        }
257
258        protected static Box getBox(Node node) {
259                Box box = node.getAttribute("box");
260                return box;
261        }
262
263        protected static Box getChildrenBox(Node node) {
264                Box box = node.getAttribute("children");
265                return box;
266        }
267
268        protected void renderBox(Box box) {
269                if (box.size() == 0)
270                        return;
271
272                for (int i = 0; i < box.size(); i++) {
273                        Node n = box.get(i);
274
275                        switch (renderingType) {
276                        case VERTICAL:
277                                n.setAttribute("x", box.width * i / (double) box.size());
278                                n.setAttribute("y", box.height / 2);
279                                break;
280                        case DISK:
281                        case HORIZONTAL:
282                                n.setAttribute("x", box.width / 2);
283                                n.setAttribute("y", box.height * i / (double) box.size());
284                                break;
285                        }
286                }
287
288                double sx = 1, sy = 1;
289                double dx = 0, dy = 0;
290
291                if (box.parent != null) {
292                        Box parentBox = getBox(box.parent);
293
294                        switch (renderingType) {
295                        case VERTICAL:
296                                sx = 1 / (double) parentBox.size();
297                                sy = 1 / Math.pow(2, box.level);
298                                break;
299                        case DISK:
300                        case HORIZONTAL:
301                                sx = 1 / Math.pow(2, box.level);
302                                sy = 1 / (double) parentBox.size();
303                                break;
304                        }
305                }
306
307                box.scale(sx, sy);
308
309                if (box.parent != null) {
310                        Box parentBox = getBox(box.parent);
311
312                        dx = box.parent.getNumber("x");
313                        dy = box.parent.getNumber("y");
314
315                        switch (renderingType) {
316                        case VERTICAL:
317                                dx -= box.width / 2;
318                                dy += parentBox.height / 2;
319                                break;
320                        case DISK:
321                        case HORIZONTAL:
322                                dx += parentBox.width / 2;
323                                dy -= box.height / 2;
324                                break;
325                        }
326                }
327
328                box.translate(dx, dy);
329        }
330
331        protected void explore(Node parent, Node who, SpanningTree tree,
332                        int[] levels) {
333
334        }
335
336        protected void publishPositions() {
337                for (Node n : internalGraph) {
338                        if (n.hasAttribute("changed")) {
339                                n.removeAttribute("changed");
340
341                                sendNodeAttributeChanged(sourceId, n.getId(), "xyz", null,
342                                                new double[] { n.getNumber("x"), n.getNumber("y"), 0 });
343                        }
344                }
345        }
346
347        /*
348         * (non-Javadoc)
349         * 
350         * @see org.graphstream.ui.layout.Layout#freezeNode(java.lang.String,
351         * boolean)
352         */
353        public void freezeNode(String id, boolean frozen) {
354        }
355
356        /*
357         * (non-Javadoc)
358         * 
359         * @see org.graphstream.ui.layout.Layout#getForce()
360         */
361        public double getForce() {
362                return 0;
363        }
364
365        /*
366         * (non-Javadoc)
367         * 
368         * @see org.graphstream.ui.layout.Layout#getHiPoint()
369         */
370        public Point3 getHiPoint() {
371                return hi;
372        }
373
374        /*
375         * (non-Javadoc)
376         * 
377         * @see org.graphstream.ui.layout.Layout#getLastStepTime()
378         */
379        public long getLastStepTime() {
380                return lastStep;
381        }
382
383        /*
384         * (non-Javadoc)
385         * 
386         * @see org.graphstream.ui.layout.Layout#getLayoutAlgorithmName()
387         */
388        public String getLayoutAlgorithmName() {
389                return "Hierarchical";
390        }
391
392        /*
393         * (non-Javadoc)
394         * 
395         * @see org.graphstream.ui.layout.Layout#getLowPoint()
396         */
397        public Point3 getLowPoint() {
398                return lo;
399        }
400
401        /*
402         * (non-Javadoc)
403         * 
404         * @see org.graphstream.ui.layout.Layout#getNodeMoved()
405         */
406        public int getNodeMovedCount() {
407                return nodeMoved;
408        }
409
410        /*
411         * (non-Javadoc)
412         * 
413         * @see org.graphstream.ui.layout.Layout#getQuality()
414         */
415        public double getQuality() {
416                return 0;
417        }
418
419        /*
420         * (non-Javadoc)
421         * 
422         * @see org.graphstream.ui.layout.Layout#getStabilization()
423         */
424        public double getStabilization() {
425                return 1 - nodeMoved / (double) internalGraph.getNodeCount();
426        }
427
428        /*
429         * (non-Javadoc)
430         * 
431         * @see org.graphstream.ui.layout.Layout#getStabilizationLimit()
432         */
433        public double getStabilizationLimit() {
434                return 1;
435        }
436
437        /*
438         * (non-Javadoc)
439         * 
440         * @see org.graphstream.ui.layout.Layout#getSteps()
441         */
442        public int getSteps() {
443                return 0;
444        }
445
446        /*
447         * (non-Javadoc)
448         * 
449         * @see org.graphstream.ui.layout.Layout#inputPos(java.lang.String)
450         */
451        public void inputPos(String filename) throws IOException {
452                throw new UnsupportedOperationException();
453        }
454
455        /*
456         * (non-Javadoc)
457         * 
458         * @see org.graphstream.ui.layout.Layout#moveNode(java.lang.String, double,
459         * double, double)
460         */
461        public void moveNode(String id, double x, double y, double z) {
462                // TODO Auto-generated method stub
463
464        }
465
466        /*
467         * (non-Javadoc)
468         * 
469         * @see org.graphstream.ui.layout.Layout#outputPos(java.lang.String)
470         */
471        public void outputPos(String filename) throws IOException {
472                throw new UnsupportedOperationException();
473        }
474
475        // /*
476        // * (non-Javadoc)
477        // *
478        // * @see
479        // *
480        // org.graphstream.ui.layout.Layout#removeListener(org.graphstream.ui.layout
481        // * .LayoutListener)
482        // */
483        // public void removeListener(LayoutListener listener) {
484        // listeners.remove(listener);
485        // }
486
487        /*
488         * (non-Javadoc)
489         * 
490         * @see org.graphstream.ui.layout.Layout#setForce(double)
491         */
492        public void setForce(double value) {
493        }
494
495        /*
496         * (non-Javadoc)
497         * 
498         * @see org.graphstream.ui.layout.Layout#setQuality(int)
499         */
500        public void setQuality(double qualityLevel) {
501        }
502
503        /*
504         * (non-Javadoc)
505         * 
506         * @see org.graphstream.ui.layout.Layout#setSendNodeInfos(boolean)
507         */
508        public void setSendNodeInfos(boolean send) {
509        }
510
511        /*
512         * (non-Javadoc)
513         * 
514         * @see org.graphstream.ui.layout.Layout#setStabilizationLimit(double)
515         */
516        public void setStabilizationLimit(double value) {
517        }
518
519        /*
520         * (non-Javadoc)
521         * 
522         * @see org.graphstream.ui.layout.Layout#shake()
523         */
524        public void shake() {
525                // No, I will not shake my work
526        }
527
528        /*
529         * (non-Javadoc)
530         * 
531         * @see org.graphstream.stream.PipeBase#nodeAdded(java.lang.String, long,
532         * java.lang.String)
533         */
534        public void nodeAdded(String sourceId, long timeId, String nodeId) {
535                internalGraph.addNode(nodeId);
536                structureChanged = true;
537        }
538
539        /*
540         * (non-Javadoc)
541         * 
542         * @see org.graphstream.stream.PipeBase#nodeRemoved(java.lang.String, long,
543         * java.lang.String)
544         */
545        public void nodeRemoved(String sourceId, long timeId, String nodeId) {
546                internalGraph.removeNode(nodeId);
547                structureChanged = true;
548        }
549
550        /*
551         * (non-Javadoc)
552         * 
553         * @see org.graphstream.stream.PipeBase#edgeAdded(java.lang.String, long,
554         * java.lang.String, java.lang.String, java.lang.String, boolean)
555         */
556        public void edgeAdded(String sourceId, long timeId, String edgeId,
557                        String fromId, String toId, boolean directed) {
558                internalGraph.addEdge(edgeId, fromId, toId, directed);
559                structureChanged = true;
560        }
561
562        /*
563         * (non-Javadoc)
564         * 
565         * @see org.graphstream.stream.PipeBase#edgeRemoved(java.lang.String, long,
566         * java.lang.String)
567         */
568        public void edgeRemoved(String sourceId, long timeId, String edgeId) {
569                internalGraph.removeEdge(edgeId);
570                structureChanged = true;
571        }
572
573        /*
574         * (non-Javadoc)
575         * 
576         * @see org.graphstream.stream.PipeBase#graphCleared(java.lang.String, long)
577         */
578        public void graphCleared(String sourceId, long timeId) {
579                internalGraph.clear();
580                structureChanged = true;
581        }
582
583        static class Box extends LinkedList<Node> {
584                private static final long serialVersionUID = -1929536876444346726L;
585
586                Node parent;
587                int level;
588                double x, y;
589                double width, height;
590                int order;
591
592                Box() {
593                        this(null, 0);
594                }
595
596                Box(Node parent, int level) {
597                        this.parent = parent;
598                        this.level = level;
599                        this.width = 5;
600                        this.height = 1;
601                        this.order = 0;
602                        this.x = 0;
603                        this.y = 0;
604                }
605
606                void scale(double sx, double sy) {
607                        width *= sx;
608                        height *= sy;
609
610                        for (int i = 0; i < size(); i++) {
611                                get(i).setAttribute("x", sx * get(i).getNumber("x"));
612                                get(i).setAttribute("y", sy * get(i).getNumber("y"));
613                        }
614                }
615
616                void translate(double dx, double dy) {
617                        for (int i = 0; i < size(); i++) {
618                                get(i).setAttribute("x", dx + get(i).getNumber("x"));
619                                get(i).setAttribute("y", dy + get(i).getNumber("y"));
620                        }
621                }
622        }
623
624        static class LevelBox extends LinkedList<Box> {
625                private static final long serialVersionUID = -5818919480025868466L;
626
627                int level;
628
629                LevelBox(int level) {
630                        this.level = level;
631                }
632
633                void sort() {
634                        if (level > 0) {
635                                Collections.sort(this, new Comparator<Box>() {
636                                        public int compare(Box b0, Box b1) {
637                                                Box pb0 = getBox(b0.parent);
638                                                Box pb1 = getBox(b1.parent);
639
640                                                if (pb0.order < pb1.order)
641                                                        return -1;
642                                                else if (pb0.order > pb1.order)
643                                                        return 1;
644
645                                                return 0;
646                                        }
647                                });
648                        }
649
650                        for (int i = 0; i < size(); i++)
651                                get(i).order = i;
652                }
653        }
654
655        public static void main(String... args) {
656                Graph g = new AdjacencyListGraph("g");
657                BarabasiAlbertGenerator gen = new BarabasiAlbertGenerator();
658                HierarchicalLayout hl = new HierarchicalLayout();
659                gen.addSink(g);
660                gen.begin();
661                for (int i = 0; i < 200; i++)
662                        gen.nextEvents();
663                gen.end();
664
665                Viewer v = g.display(false);
666                v.enableAutoLayout(hl);
667        }
668}