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}