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.algorithm.generator;
033
034/**
035 * Banana tree generator. A (n,k)-banana tree is composed of a root node and n
036 * k-stars with one leaf of each star connected to the root node.
037 * 
038 * @reference Chen, W. C.; Lü, H. I.; and Yeh, Y. N.
039 *            "Operations of Interlaced Trees and Graceful Trees." Southeast
040 *            Asian Bull. Math. 21, 337-348, 1997.
041 * 
042 */
043public class BananaTreeGenerator extends BaseGenerator {
044
045        protected int k;
046        protected int currentStarIndex;
047        protected int edgeId;
048        protected boolean setCoordinates;
049
050        /**
051         * Build a new Banana tree generator with default star size.
052         */
053        public BananaTreeGenerator() {
054                this(4);
055        }
056
057        /**
058         * Build a new Banana tree generator composing of k-stars.
059         * 
060         * @param k
061         *            size of star
062         */
063        public BananaTreeGenerator(int k) {
064                this.k = k;
065                this.setCoordinates = true;
066                this.currentStarIndex = 0;
067                this.edgeId = 0;
068        }
069
070        /*
071         * (non-Javadoc)
072         * 
073         * @see org.graphstream.algorithm.generator.Generator#begin()
074         */
075        public void begin() {
076                addNode("root");
077        }
078
079        /*
080         * (non-Javadoc)
081         * 
082         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
083         */
084        public boolean nextEvents() {
085                addNode(getNodeId(currentStarIndex, 0));
086
087                for (int i = 1; i < k; i++) {
088                        addNode(getNodeId(currentStarIndex, i));
089                        addEdge(String.format("E%04d", edgeId++),
090                                        getNodeId(currentStarIndex, 0),
091                                        getNodeId(currentStarIndex, i));
092                }
093
094                addEdge(String.format("E%04d", edgeId++),
095                                getNodeId(currentStarIndex, 1), "root");
096
097                currentStarIndex++;
098
099                if (setCoordinates)
100                        flushCoords();
101
102                return true;
103        }
104
105        /**
106         * Format node id.
107         * 
108         * @param star
109         *            index of the star
110         * @param index
111         *            index of the node in the star
112         * @return unique node id
113         */
114        protected String getNodeId(int star, int index) {
115                return String.format("S%02d_%02d", star, index);
116        }
117
118        /**
119         * Set coordinates of nodes.
120         */
121        protected void flushCoords() {
122                sendNodeAttributeChanged(sourceId, "root", "x", null, 0);
123                sendNodeAttributeChanged(sourceId, "root", "y", null, 0);
124
125                double r1 = 8.0;
126
127                for (int i = 0; i < currentStarIndex; i++) {
128                        double a = i * 2 * Math.PI / currentStarIndex;
129                        double rx = r1 * Math.cos(a);
130                        double ry = r1 * Math.sin(a);
131
132                        sendNodeAttributeChanged(sourceId, getNodeId(i, 0), "x", null, rx);
133                        sendNodeAttributeChanged(sourceId, getNodeId(i, 0), "y", null, ry);
134
135                        for (int j = 1; j < k; j++) {
136                                double b = a - (j - 1) * 2 * Math.PI / (k - 1);
137                                double r2 = 0.8 * r1 * Math.sin(Math.PI / currentStarIndex);
138
139                                sendNodeAttributeChanged(sourceId, getNodeId(i, j), "x", null,
140                                                rx - r2 * Math.cos(b));
141                                sendNodeAttributeChanged(sourceId, getNodeId(i, j), "y", null,
142                                                ry - r2 * Math.sin(b));
143                        }
144                }
145        }
146}