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 * Generator for square grids of any size.
036 * 
037 * <p>
038 * This generate square grid graphs of any size with each node not on the
039 * border of the graph having four neighbours for regular grids or
040 * height neighbours for cross grids. The nodes at each of the four
041 * corners of the grid consequently have only two or three (cross)
042 * neighbours. The nodes on the side of the grid have three or five (cross)
043 * neighbours.
044 * </p>
045 * 
046 * <p>
047 * The generated grid can be closed as a torus, meaning that there is
048 * no border nodes will exist, therefore all nodes will have the same
049 * degree four or height (cross).
050 * </p>
051 * 
052 * <h2>Usage</h2>
053 * 
054 * <p>
055 * At the contrary of most generators, this generator does not produce
056 * only one node when you call {@link #nextEvents()}. It adds a row
057 * and column to the grid, making the side of the square grow by one.
058 * Therfore if you call the {@link #nextEvents()} methode n times you
059 * will have n^2 nodes.
060 * </p>
061 * 
062 * <p>
063 * You can indicate at construction time if the graph will be a regular
064 * grid (no argument) or if it must be a cross-grid (first boolean argument to
065 * true) and a tore (second boolean argument to true).
066 * </p>
067 * 
068 * <p>
069 * A constructor with a third boolean parameter allows to indicate that nodes
070 * must have a ``xyz`` attribute to position them or not. This is the default
071 * behaviour. 
072 * </p>
073 * 
074 * <h2>Complexity</h2>
075 * 
076 * At each call to {@link #nextEvents()} ((n+1)*2) new nodes are generated
077 * with n the size of a side of the grid.
078 * 
079 * <h2>Example</h2>
080 * 
081 * <pre>
082 * Graph graph = new SingleGraph("grid");
083 * Generator gen = new GridGenerator();
084 * 
085 * gen.addSink(graph);
086 * gen.begin();
087 * for(int i=0; i<10; i++) {
088 *              gen.nextEvents();
089 * }
090 * gen.end();
091 * 
092 * // Nodes already have a position.
093 * graph.display(false);
094 * </pre>
095 * 
096 * @since 2007
097 */
098public class GridGenerator extends BaseGenerator {
099        /**
100         * Create diagonal links.
101         */
102        protected boolean cross = false;
103
104        /**
105         * Close the grid as a tore.
106         */
107        protected boolean tore = false;
108
109        /**
110         * generate x and y attributes on a plane.
111         */
112        protected boolean generateXY = true;
113
114        /**
115         * Current width and height of the grid.
116         */
117        protected int currentSize = 0;
118
119        /**
120         * Used to generate edge names.
121         */
122        protected int edgeNames = 0;
123
124        /**
125         * New grid generator. By default no diagonal links are made and the grid is
126         * not a tore.
127         */
128        public GridGenerator() {
129                this(false, false);
130        }
131
132        /**
133         * New grid generator.
134         * 
135         * @param cross
136         *            Create diagonal links?.
137         * @param tore
138         *            Close the grid as a tore?.
139         */
140        public GridGenerator(boolean cross, boolean tore) {
141                this(cross, tore, false);
142        }
143
144        /**
145         * New grid generator.
146         * 
147         * @param cross
148         *            Create diagonal links?
149         * @param tore
150         *            Close the grid as a tore?
151         * @param generateXY
152         *            Generate coordinates of nodes.
153         */
154        public GridGenerator(boolean cross, boolean tore, boolean generateXY) {
155                this(cross, tore, false, false);
156        }
157
158        /**
159         * New grid generator.
160         * 
161         * @param cross
162         *            Create diagonal links ?
163         * @param tore
164         *            Close the grid as a tore ?
165         * @param generateXY
166         *            Generate coordinates of nodes.
167         * @param directed
168         *            Are edges directed ?
169         */
170        public GridGenerator(boolean cross, boolean tore, boolean generateXY,
171                        boolean directed) {
172                this.cross = cross;
173                this.tore = tore;
174                this.generateXY = generateXY;
175                this.directed = directed;
176        }
177
178        /**
179         * Add an initial node.
180         * 
181         * @see org.graphstream.algorithm.generator.Generator#begin()
182         */
183        public void begin() {
184                addNode(nodeName(0, 0), 0, 0);
185        }
186
187        /**
188         * Grow the graph. If grid dimensions are width x height, then after a call
189         * to this method dimensions will be (width+1)x(height+1).
190         * 
191         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
192         */
193        public boolean nextEvents() {
194                currentSize++;
195
196                for (int y = 0; y < currentSize; ++y) {
197                        String id = nodeName(currentSize, y);
198
199                        addNode(id, currentSize, y);
200                        addEdge(Integer.toString(edgeNames++),
201                                        nodeName(currentSize - 1, y), id);
202
203                        if (y > 0) {
204                                addEdge(Integer.toString(edgeNames++),
205                                                nodeName(currentSize, y - 1), id);
206
207                                if (cross) {
208                                        addEdge(Integer.toString(edgeNames++),
209                                                        nodeName(currentSize - 1, y - 1), id);
210                                        addEdge(Integer.toString(edgeNames++),
211                                                        nodeName(currentSize, y - 1),
212                                                        nodeName(currentSize - 1, y));
213                                }
214                        }
215                }
216
217                for (int x = 0; x <= currentSize; ++x) {
218                        String id = nodeName(x, currentSize);
219
220                        addNode(id, x, currentSize);
221                        addEdge(Integer.toString(edgeNames++),
222                                        nodeName(x, currentSize - 1), id);
223
224                        if (x > 0) {
225                                addEdge(Integer.toString(edgeNames++),
226                                                nodeName(x - 1, currentSize), id);
227
228                                if (cross) {
229                                        addEdge(Integer.toString(edgeNames++),
230                                                        nodeName(x - 1, currentSize - 1), id);
231                                        addEdge(Integer.toString(edgeNames++),
232                                                        nodeName(x - 1, currentSize),
233                                                        nodeName(x, currentSize - 1));
234                                }
235                        }
236                }
237
238                return true;
239        }
240
241        /**
242         * If grid is a tore, a call to this method will close the tore.
243         * 
244         * @see org.graphstream.algorithm.generator.Generator#end()
245         */
246        @Override
247        public void end() {
248                if (tore) {
249                        if (currentSize > 0) {
250                                for (int y = 0; y <= currentSize; ++y) {
251                                        addEdge(Integer.toString(edgeNames++),
252                                                        nodeName(currentSize, y), nodeName(0, y));
253
254                                        if (cross) {
255                                                if (y > 0) {
256                                                        addEdge(Integer.toString(edgeNames++),
257                                                                        nodeName(currentSize, y),
258                                                                        nodeName(0, y - 1));
259                                                        addEdge(Integer.toString(edgeNames++),
260                                                                        nodeName(currentSize, y - 1),
261                                                                        nodeName(0, y));
262                                                }
263                                        }
264                                }
265
266                                for (int x = 0; x <= currentSize; ++x) {
267                                        addEdge(Integer.toString(edgeNames++),
268                                                        nodeName(x, currentSize), nodeName(x, 0));
269
270                                        if (cross) {
271                                                if (x > 0) {
272                                                        addEdge(Integer.toString(edgeNames++),
273                                                                        nodeName(x, currentSize),
274                                                                        nodeName(x - 1, 0));
275                                                        addEdge(Integer.toString(edgeNames++),
276                                                                        nodeName(x - 1, currentSize),
277                                                                        nodeName(x, 0));
278                                                }
279                                        }
280                                }
281
282                                if (cross) {
283                                        addEdge(Integer.toString(edgeNames++),
284                                                        nodeName(currentSize, 0), nodeName(0, currentSize));
285                                        addEdge(Integer.toString(edgeNames++), nodeName(0, 0),
286                                                        nodeName(currentSize, currentSize));
287                                }
288                        }
289                }
290                
291                super.end();
292        }
293
294        protected String nodeName(int x, int y) {
295                return Integer.toString(x) + "_" + Integer.toString(y);
296        }
297}