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
034import java.util.HashSet;
035
036/**
037 * Build a graph using a lcf notation.
038 * 
039 * Source : <a href="http://en.wikipedia.org/wiki/LCF_notation">Wikipedia</a>
040 * 
041 */
042public class LCFGenerator extends BaseGenerator {
043
044        /**
045         * Model a LCF notation. Such notations are noted [a0,a1,...,an]^k. This is
046         * translate as LCF object in this way :
047         * 
048         * <pre>
049         * new LCF(k, a0, a1, ..., an)
050         * </pre>
051         * 
052         */
053        public static class LCF {
054                int repeat;
055                int[] steps;
056
057                public LCF(int repeat, int... steps) {
058                        this.repeat = repeat;
059                        this.steps = steps;
060                }
061        }
062
063        private int n;
064        private int initialRingSize;
065        private HashSet<String> crossed;
066        protected LCF lcf;
067        protected boolean canBeExtended;
068
069        /**
070         * Build a new graph generator using a LCF notation.
071         * 
072         * @param lcf
073         *            the lcf notation describing the graph
074         * @param initialRingSize
075         *            initial amount of nodes
076         * @param canBeExtended
077         *            true if the graph can be extended, ie. if a node can be added
078         *            in a new #nextEvents() call
079         */
080        public LCFGenerator(LCF lcf, int initialRingSize, boolean canBeExtended) {
081                this.lcf = lcf;
082                this.crossed = new HashSet<String>();
083                this.initialRingSize = initialRingSize;
084                this.canBeExtended = canBeExtended;
085        }
086
087        /*
088         * (non-Javadoc)
089         * 
090         * @see org.graphstream.algorithm.generator.Generator#begin()
091         */
092        public void begin() {
093                addNode(getNodeId(0));
094                addNode(getNodeId(1));
095                addNode(getNodeId(2));
096
097                addEdge(getEdgeId(0, 1), getNodeId(0), getNodeId(1));
098                addEdge(getEdgeId(1, 2), getNodeId(1), getNodeId(2));
099                addEdge(getEdgeId(2, 0), getNodeId(2), getNodeId(0));
100
101                n = 3;
102
103                for (int i = n; i < initialRingSize; i++)
104                        increaseRing();
105
106                flushCoords();
107                makeLCF();
108        }
109
110        /*
111         * (non-Javadoc)
112         * 
113         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
114         */
115        public boolean nextEvents() {
116                if (canBeExtended) {
117                        increaseRing();
118                        makeLCF();
119                        flushCoords();
120                }
121
122                return canBeExtended;
123        }
124
125        protected void increaseRing() {
126                addNode(getNodeId(n));
127
128                delEdge(getEdgeId(n - 1, 0));
129                addEdge(getEdgeId(n - 1, n), getNodeId(n - 1), getNodeId(n));
130                addEdge(getEdgeId(n, 0), getNodeId(n), getNodeId(0));
131
132                n++;
133        }
134
135        protected void makeLCF() {
136                int i = 0;
137                int r = 0;
138                HashSet<String> added = new HashSet<String>();
139
140                while (r < lcf.repeat && i < n) {
141                        for (int k = 0; k < lcf.steps.length && i < n; k++) {
142                                int j = (i + lcf.steps[k]) % n;
143
144                                while (j < 0)
145                                        j += n;
146
147                                String edge = getEdgeId(i, j);
148
149                                if (!crossed.contains(edge) && !added.contains(edge))
150                                        addEdge(edge, getNodeId(i), getNodeId(j));
151
152                                added.add(edge);
153                                i++;
154                        }
155
156                        r++;
157                }
158
159                for (String edge : crossed) {
160                        if (!added.contains(edge))
161                                delEdge(edge);
162                }
163
164                crossed.clear();
165                crossed = added;
166        }
167
168        protected void flushCoords() {
169                double d = 2 * Math.PI / n;
170
171                for (int i = 0; i < n; i++) {
172                        sendNodeAttributeChanged(sourceId, getNodeId(i), "x", null,
173                                        Math.cos(i * d));
174                        sendNodeAttributeChanged(sourceId, getNodeId(i), "y", null,
175                                        Math.sin(i * d));
176                }
177        }
178
179        protected String getNodeId(int i) {
180                return String.format("%03d", i);
181        }
182
183        protected String getEdgeId(int i1, int i2) {
184                if (i1 > i2) {
185                        int t = i1;
186                        i1 = i2;
187                        i2 = t;
188                }
189
190                return String.format("%03d_%03d", i1, i2);
191        }
192}