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 * A grid generator with holes. 038 * 039 * @author Guilhelm Savin 040 */ 041public class IncompleteGridGenerator extends BaseGenerator { 042 /** 043 * Current width of the grid. 044 */ 045 protected int currentWidth = 0; 046 047 /** 048 * Current height of the grid. 049 */ 050 protected int currentHeight = 0; 051 052 /** 053 * Probability of hole creation. 054 */ 055 protected float holeProbability = 0.5f; 056 057 /** 058 * Max size of holes. 059 */ 060 protected int holeMaxSize = 5; 061 062 /** 063 * Number of attempt to create a hole by step. 064 */ 065 protected int holesPerStep = 3; 066 067 /** 068 * Connect nodes diagonally. 069 */ 070 protected boolean cross = true; 071 072 /** 073 * Id of nodes that were connected to a deleted node. These nodes can not be 074 * deleted. This ensure to produce a connected graph. 075 */ 076 protected HashSet<String> unbreakable = new HashSet<String>(); 077 078 /** 079 * New generator. 080 */ 081 public IncompleteGridGenerator() { 082 this(true, 0.5f, 5, 3); 083 } 084 085 /** 086 * New generator. 087 * 088 * @param cross 089 * connect nodes diagonally 090 * @param holeProbability 091 * probability of an hole in the grid 092 * @param holeMaxSize 093 * max size of holes 094 * @param holesPerStep 095 * number of attempt to create a hole by step 096 */ 097 public IncompleteGridGenerator(boolean cross, float holeProbability, 098 int holeMaxSize, int holesPerStep) { 099 setUseInternalGraph(true); 100 101 this.cross = cross; 102 this.holeProbability = holeProbability; 103 this.holeMaxSize = holeMaxSize; 104 this.holesPerStep = holesPerStep; 105 } 106 107 protected String getNodeId(int x, int y) { 108 return String.format("%d_%d", x, y); 109 } 110 111 protected String getEdgeId(String n1, String n2) { 112 if (n1.compareTo(n2) < 0) { 113 String tmp = n2; 114 n2 = n1; 115 n1 = tmp; 116 } 117 118 return String.format("%s-%s", n1, n2); 119 } 120 121 /** 122 * Connect a node. 123 * 124 * @param x 125 * abscissa of the node to disconnect 126 * @param y 127 * ordina of the node to disconnect 128 */ 129 protected void connectNode(int x, int y) { 130 String nodeId = getNodeId(x, y); 131 String neigh; 132 133 if (x > 0) { 134 neigh = getNodeId(x - 1, y); 135 136 if (internalGraph.getNode(neigh) != null) 137 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 138 else 139 unbreakable.add(nodeId); 140 } 141 142 if (x < currentWidth - 1) { 143 neigh = getNodeId(x + 1, y); 144 145 if (internalGraph.getNode(neigh) != null) 146 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 147 else 148 unbreakable.add(nodeId); 149 } 150 151 if (y > 0) { 152 neigh = getNodeId(x, y - 1); 153 154 if (internalGraph.getNode(neigh) != null) 155 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 156 else 157 unbreakable.add(nodeId); 158 } 159 160 if (y < currentHeight - 1) { 161 neigh = getNodeId(x, y + 1); 162 163 if (internalGraph.getNode(neigh) != null) 164 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 165 else 166 unbreakable.add(nodeId); 167 } 168 169 // Cross 170 171 if (x > 0) { 172 if (y > 0) { 173 neigh = getNodeId(x - 1, y - 1); 174 175 if (internalGraph.getNode(neigh) != null) { 176 if (cross) 177 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 178 } else 179 unbreakable.add(nodeId); 180 } 181 182 if (y < currentHeight - 1) { 183 neigh = getNodeId(x - 1, y + 1); 184 185 if (internalGraph.getNode(neigh) != null) { 186 if (cross) 187 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 188 } else 189 unbreakable.add(nodeId); 190 } 191 } 192 193 if (x < currentWidth - 1) { 194 if (y > 0) { 195 neigh = getNodeId(x + 1, y - 1); 196 197 if (internalGraph.getNode(neigh) != null) { 198 if (cross) 199 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 200 } else 201 unbreakable.add(nodeId); 202 } 203 204 if (y < currentHeight - 1) { 205 neigh = getNodeId(x + 1, y + 1); 206 207 if (internalGraph.getNode(neigh) != null) { 208 if (cross) 209 addEdge(getEdgeId(nodeId, neigh), nodeId, neigh); 210 } else 211 unbreakable.add(nodeId); 212 } 213 } 214 } 215 216 /** 217 * Disconnect a node. Used to create holes. 218 * 219 * @param x 220 * abscissa of the node to disconnect 221 * @param y 222 * ordina of the node to disconnect 223 */ 224 protected void disconnectNode(int x, int y) { 225 String nodeId = getNodeId(x, y); 226 String neigh; 227 228 if (x > 0) { 229 neigh = getNodeId(x - 1, y); 230 231 if (internalGraph.getNode(neigh) != null) 232 delEdge(getEdgeId(nodeId, neigh)); 233 } 234 235 if (x < currentWidth - 1) { 236 neigh = getNodeId(x + 1, y); 237 238 if (internalGraph.getNode(neigh) != null) 239 delEdge(getEdgeId(nodeId, neigh)); 240 } 241 242 if (y > 0) { 243 neigh = getNodeId(x, y - 1); 244 245 if (internalGraph.getNode(neigh) != null) 246 delEdge(getEdgeId(nodeId, neigh)); 247 } 248 249 if (y < currentHeight - 1) { 250 neigh = getNodeId(x, y + 1); 251 252 if (internalGraph.getNode(neigh) != null) 253 delEdge(getEdgeId(nodeId, neigh)); 254 } 255 256 if (cross) { 257 if (x > 0) { 258 if (y > 0) { 259 neigh = getNodeId(x - 1, y - 1); 260 261 if (internalGraph.getNode(neigh) != null) 262 delEdge(getEdgeId(nodeId, neigh)); 263 } 264 265 if (y < currentHeight - 1) { 266 neigh = getNodeId(x - 1, y + 1); 267 268 if (internalGraph.getNode(neigh) != null) 269 delEdge(getEdgeId(nodeId, neigh)); 270 } 271 } 272 273 if (x < currentWidth - 1) { 274 if (y > 0) { 275 neigh = getNodeId(x + 1, y - 1); 276 277 if (internalGraph.getNode(neigh) != null) 278 delEdge(getEdgeId(nodeId, neigh)); 279 } 280 281 if (y < currentHeight - 1) { 282 neigh = getNodeId(x + 1, y + 1); 283 284 if (internalGraph.getNode(neigh) != null) 285 delEdge(getEdgeId(nodeId, neigh)); 286 } 287 } 288 } 289 } 290 291 /* 292 * (non-Javadoc) 293 * 294 * @see org.graphstream.algorithm.generator.Generator#begin() 295 */ 296 public void begin() { 297 298 } 299 300 /** 301 * Grow the graph. If grid dimensions are width x height, then after a call 302 * to this method dimensions will be (width+1)x(height+1). Eventually create 303 * some hopes. 304 * 305 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 306 */ 307 public boolean nextEvents() { 308 for (int i = 0; i < currentWidth; i++) { 309 addNode(getNodeId(i, currentHeight), i, currentHeight); 310 connectNode(i, currentHeight); 311 } 312 313 for (int i = 0; i < currentHeight; i++) { 314 addNode(getNodeId(currentWidth, i), currentWidth, i); 315 connectNode(currentWidth, i); 316 } 317 318 addNode(getNodeId(currentWidth, currentHeight), currentWidth, currentHeight); 319 connectNode(currentWidth, currentHeight); 320 321 currentWidth++; 322 currentHeight++; 323 324 for (int k = 0; k < holesPerStep; k++) { 325 if (random.nextFloat() < holeProbability) { 326 int x1, y1, t; 327 int sizeX, sizeY; 328 329 t = 0; 330 331 do { 332 x1 = random.nextInt(currentWidth); 333 y1 = random.nextInt(currentHeight); 334 t++; 335 } while ((internalGraph.getNode(getNodeId(x1, y1)) == null || unbreakable 336 .contains(getNodeId(x1, y1))) 337 && t < internalGraph.getNodeCount()); 338 339 if (t >= internalGraph.getNodeCount()) 340 continue; 341 342 sizeX = random.nextInt(holeMaxSize); 343 sizeY = random.nextInt(holeMaxSize - sizeX); 344 345 for (int i = 0; i < sizeX; i++) 346 for (int j = 0; j < sizeY; j++) { 347 String id = getNodeId(x1 + i, y1 + j); 348 if (internalGraph.getNode(id) != null 349 && !unbreakable.contains(id)) { 350 disconnectNode(x1 + i, y1 + j); 351 delNode(getNodeId(x1 + i, y1 + j)); 352 353 if (j == 0 && y1 > 0) 354 unbreakable.add(getNodeId(x1 + i, y1 - 1)); 355 if (j == sizeY - 1 && y1 + sizeY < currentHeight) 356 unbreakable.add(getNodeId(x1 + i, y1 + sizeY)); 357 358 if (i == 0 && x1 > 0) 359 unbreakable.add(getNodeId(x1 - 1, y1 + j)); 360 if (i == sizeX - 1 && x1 + sizeX < currentWidth) 361 unbreakable.add(getNodeId(x1 + sizeX, y1 + j)); 362 363 if (i == 0 && x1 > 0 && j == 0 && y1 > 0) 364 unbreakable.add(getNodeId(x1 - 1, y1 - 1)); 365 if (i == sizeX - 1 && x1 + sizeX < currentWidth 366 && j == sizeY - 1 367 && y1 + sizeY < currentHeight) 368 unbreakable.add(getNodeId(x1 + sizeX, y1 369 + sizeY)); 370 if (i == 0 && x1 > 0 && j == sizeY - 1 371 && y1 + sizeY < currentHeight) 372 unbreakable.add(getNodeId(x1 - 1, y1 + sizeY)); 373 if (i == sizeX - 1 && x1 + sizeX < currentWidth 374 && j == 0 && y1 > 0) 375 unbreakable.add(getNodeId(x1 + sizeX, y1 - 1)); 376 } 377 } 378 } 379 } 380 381 return true; 382 } 383 384 /* 385 * (non-Javadoc) 386 * 387 * @see org.graphstream.algorithm.generator.Generator#end() 388 */ 389 @Override 390 public void end() { 391 super.end(); 392 } 393}