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.ArrayList; 035import java.util.Random; 036 037import org.graphstream.graph.Graph; 038import org.graphstream.graph.implementations.AdjacencyListGraph; 039import org.graphstream.stream.SourceBase; 040 041/** 042 * Base graph generator. 043 * 044 * <p> 045 * This class is a base to implement generators. It it has facilities to 046 * generate edges or nodes, and provides services to add attributes on them and 047 * to choose if the edge is directed or not. 048 * </p> 049 * 050 * <p> 051 * Indeed, This generator has the ability to add randomly chosen numerical 052 * values on arbitrary attributes on edges or nodes of the graph, and to 053 * randomly choose a direction for edges. 054 * </p> 055 * 056 * <p> 057 * A list of attributes can be given for nodes and edges. In this case each new 058 * node or edge added will have this attribute and the value will be a randomly 059 * chosen number. The range in which these numbers are chosen can be specified. 060 * </p> 061 * 062 * <p> 063 * By default, edges are not oriented. It is possible to ask orientation, and in 064 * addition to ask that the direction be chosen randomly (by default, if edges 065 * must be oriented, the order given for the two nodes to connect is used). 066 * </p> 067 * 068 * @since 2007 069 */ 070public abstract class BaseGenerator extends SourceBase implements Generator { 071 072 // Attributes 073 074 /** 075 * Are edges directed ? 076 */ 077 protected boolean directed = false; 078 079 /** 080 * If directed, choose the direction randomly?. 081 */ 082 protected boolean randomlyDirected = false; 083 084 /** 085 * List of attributes to put on nodes with a randomly chosen numerical 086 * value. 087 */ 088 protected ArrayList<String> nodeAttributes = new ArrayList<String>(); 089 090 /** 091 * List of attributes to put on edges with a randomly chosen numerical 092 * value. 093 */ 094 protected ArrayList<String> edgeAttributes = new ArrayList<String>(); 095 096 /** 097 * If node attributes are added, in which range are the numbers chosen ?. 098 */ 099 protected double[] nodeAttributeRange = new double[2]; 100 101 /** 102 * If edge attributes are added, in which range are the numbers chosen ?. 103 */ 104 protected double[] edgeAttributeRange = new double[2]; 105 106 /** 107 * The random number generator. 108 */ 109 protected Random random = new Random(); 110 111 /** 112 * Set the node label attribute using the identifier?. 113 */ 114 protected boolean addNodeLabels = false; 115 116 /** 117 * Set the edge label attribute using the identifier?. 118 */ 119 protected boolean addEdgeLabels = false; 120 121 /** 122 * Flag to know if generator has to use an internal graph. Generator which 123 * want to use this feature have to use the 124 * {@link #setUseInternalGraph(boolean)} method to set this flag. 125 */ 126 private boolean useInternalGraph; 127 128 /** 129 * When {@link #useInternalGraph} is on, nodes and edges are stored in this 130 * graph. 131 */ 132 protected Graph internalGraph; 133 134 /** 135 * Used to created unique generatorId. 136 */ 137 private volatile static int generatorId; 138 139 // Constructors 140 141 /** 142 * New base graph generator. By default no attributes are added to nodes and 143 * edges, and edges are not directed. 144 */ 145 public BaseGenerator() { 146 this(false, false); 147 } 148 149 /** 150 * New base graph generator. By default no attributes are added to nodes and 151 * edges. It is possible to make edge randomly directed. 152 * 153 * @param directed 154 * If true the edges are directed. 155 * @param randomlyDirectedEdges 156 * If true edge, are directed and the direction is chosen 157 * randomly. 158 */ 159 public BaseGenerator(boolean directed, boolean randomlyDirectedEdges) { 160 super(String.format("generator-%08x", generatorId++)); 161 setDirectedEdges(directed, randomlyDirectedEdges); 162 163 nodeAttributeRange[0] = 0; 164 nodeAttributeRange[1] = 1; 165 edgeAttributeRange[0] = 0; 166 edgeAttributeRange[1] = 1; 167 } 168 169 /** 170 * New base graph generator. 171 * 172 * @param directed 173 * If true the edges are directed. 174 * @param randomlyDirectedEdges 175 * It true, edges are directed and the direction is choosed 176 * randomly. 177 * @param nodeAttribute 178 * put an attribute by that name on each node with a random 179 * numeric value. 180 * @param edgeAttribute 181 * put an attribute by that name on each edge with a random 182 * numeric value. 183 */ 184 public BaseGenerator(boolean directed, boolean randomlyDirectedEdges, 185 String nodeAttribute, String edgeAttribute) { 186 this(directed, randomlyDirectedEdges); 187 188 addNodeAttribute(nodeAttribute); 189 addEdgeAttribute(edgeAttribute); 190 } 191 192 // Commands 193 194 /** 195 * End the graph generation by finalizing it. Once the {@link #nextEvents()} 196 * method returned false (or even if you stop before), this method must be 197 * called to finish the graph. 198 * 199 * In addition, BaseGenerator adds a "clear" operations that removes all the 200 * kept edges and nodes identifiers and the associated data. 201 */ 202 public void end() { 203 clearKeptData(); 204 } 205 206 /** 207 * Set the random seed used for random number generation. 208 * 209 * @param seed 210 * The seed. 211 */ 212 public void setRandomSeed(long seed) { 213 random.setSeed(seed); 214 } 215 216 /** 217 * Allow to add label attributes on nodes. The label is the identifier of 218 * the node. 219 * 220 * @param on 221 * If true labels are added. 222 */ 223 public void addNodeLabels(boolean on) { 224 addNodeLabels = on; 225 } 226 227 /** 228 * Allow to add label attributes on edges. The label is the identifier of 229 * the edge. 230 * 231 * @param on 232 * If true labels are added. 233 */ 234 public void addEdgeLabels(boolean on) { 235 addEdgeLabels = on; 236 } 237 238 /** 239 * Make each generated edge directed or not. If the new edge created are 240 * directed, the direction is chosen randomly. 241 * 242 * @param directed 243 * It true, edge will be directed. 244 * @param randomly 245 * If true, not only edges are directed, but the direction is 246 * chosen randomly. 247 */ 248 public void setDirectedEdges(boolean directed, boolean randomly) { 249 this.directed = directed; 250 251 if (directed && randomly) 252 randomlyDirected = randomly; 253 } 254 255 /** 256 * Add this attribute on all nodes generated. This attribute will have a 257 * numerical value chosen in a range that is by default [0-1]. 258 * 259 * @param name 260 * The attribute name. 261 * @see #setNodeAttributesRange(double, double) 262 * @see #removeNodeAttribute(String) 263 */ 264 public void addNodeAttribute(String name) { 265 nodeAttributes.add(name); 266 } 267 268 /** 269 * Remove an automatic attribute for nodes. 270 * 271 * @param name 272 * The attribute name. 273 * @see #addNodeAttribute(String) 274 */ 275 public void removeNodeAttribute(String name) { 276 int pos = nodeAttributes.indexOf(name); 277 278 if (pos >= 0) 279 nodeAttributes.remove(pos); 280 } 281 282 /** 283 * Add this attribute on all edges generated. This attribute will have a 284 * numerical value chosen in a range that is by default [0-1]. 285 * 286 * @param name 287 * The attribute name. 288 * @see #setEdgeAttributesRange(double, double) 289 * @see #removeEdgeAttribute(String) 290 */ 291 public void addEdgeAttribute(String name) { 292 edgeAttributes.add(name); 293 } 294 295 /** 296 * Remove an automatic attribute for edges. 297 * 298 * @param name 299 * The attribute name. 300 * @see #addEdgeAttribute(String) 301 */ 302 public void removeEdgeAttribute(String name) { 303 int pos = edgeAttributes.indexOf(name); 304 305 if (pos >= 0) 306 edgeAttributes.remove(pos); 307 } 308 309 /** 310 * If node attributes are added automatically, choose in which range the 311 * values are choosed. 312 * 313 * @see #addNodeAttribute(String) 314 */ 315 public void setNodeAttributesRange(double low, double hi) { 316 nodeAttributeRange[0] = low; 317 nodeAttributeRange[1] = hi; 318 } 319 320 /** 321 * If edge attributes are added automatically, choose in which range the 322 * values are choosed. 323 * 324 * @see #addEdgeAttribute(String) 325 */ 326 public void setEdgeAttributesRange(double low, double hi) { 327 edgeAttributeRange[0] = low; 328 edgeAttributeRange[1] = hi; 329 } 330 331 /** 332 * Enable or disable the use of an internal graph. If enable, nodes, edges 333 * and their attributes are stored in an internal graph. 334 * 335 * This is useful if the generator needs to remember informations like node 336 * id. 337 * 338 * @param on 339 * true if the internal graph has to be enable. 340 */ 341 public void setUseInternalGraph(boolean on) { 342 useInternalGraph = on; 343 344 if (!on && internalGraph != null) { 345 internalGraph.clear(); 346 internalGraph = null; 347 } 348 349 if (on && internalGraph == null) { 350 internalGraph = new AdjacencyListGraph(getClass().getName() 351 + "-internal_graph"); 352 internalGraph.setStrict(false); 353 } 354 } 355 356 /** 357 * Flag to know if an internal graph is in use. 358 * 359 * @return true if nodes and edges are stored in an internal graph. 360 */ 361 public boolean isUsingInternalGraph() { 362 return useInternalGraph; 363 } 364 365 /** 366 * Same as {@link #addNode(String)} but specify attributes to position the 367 * node on a plane. 368 * 369 * @param id 370 * The node identifier. 371 * @param x 372 * The node abscissa. 373 * @param y 374 * The node ordinate. 375 */ 376 protected void addNode(String id, double x, double y) { 377 addNode(id); 378 sendNodeAttributeAdded(sourceId, id, "xy", new Double[] { 379 new Double(x), new Double(y) }); 380 381 if (useInternalGraph) 382 internalGraph.getNode(id).addAttribute("xy", 383 (Object) (new Double[] { new Double(x), new Double(y) })); 384 } 385 386 /** 387 * Add a node and put attributes on it if needed. 388 * 389 * @param id 390 * The new node identifier. 391 */ 392 protected void addNode(String id) { 393 sendNodeAdded(sourceId, id); 394 395 if (addNodeLabels) 396 sendNodeAttributeAdded(sourceId, id, "label", id); 397 398 if (useInternalGraph) 399 internalGraph.addNode(id); 400 401 double value; 402 403 for (String attr : nodeAttributes) { 404 value = (random.nextDouble() * (nodeAttributeRange[1] - nodeAttributeRange[0])) 405 + nodeAttributeRange[0]; 406 sendNodeAttributeAdded(sourceId, id, attr, value); 407 408 if (useInternalGraph) 409 internalGraph.getNode(id).addAttribute(attr, value); 410 } 411 } 412 413 /** 414 * Remove a node. 415 * 416 * @param id 417 * id of the node to remove 418 */ 419 protected void delNode(String id) { 420 if (useInternalGraph) 421 internalGraph.removeNode(id); 422 423 sendNodeRemoved(sourceId, id); 424 } 425 426 /** 427 * Add an edge, choosing randomly its orientation if needed and putting 428 * attribute on it if needed. 429 * 430 * @param id 431 * The edge identifier, if null, the identifier is created from 432 * the nodes identifiers. 433 * @param from 434 * The source node (can be inverted randomly with the target 435 * node). 436 */ 437 protected void addEdge(String id, String from, String to) { 438 if (directed && randomlyDirected && (random.nextFloat() > 0.5f)) { 439 String tmp = from; 440 from = to; 441 to = tmp; 442 } 443 444 if (id == null) 445 id = from + "_" + to; 446 447 sendEdgeAdded(sourceId, id, from, to, directed); 448 449 if (useInternalGraph) 450 internalGraph.addEdge(id, from, to, directed); 451 452 if (addEdgeLabels) 453 sendEdgeAttributeAdded(sourceId, id, "label", id); 454 455 for (String attr : edgeAttributes) { 456 double value = (random.nextDouble() * (edgeAttributeRange[1] - edgeAttributeRange[0])) 457 + edgeAttributeRange[0]; 458 sendEdgeAttributeAdded(sourceId, id, attr, value); 459 460 if (useInternalGraph) 461 internalGraph.getEdge(id).addAttribute(attr, value); 462 } 463 } 464 465 /** 466 * Remove an edge. 467 * 468 * @param edgeId 469 * id of the edge to remove 470 */ 471 protected void delEdge(String edgeId) { 472 sendEdgeRemoved(sourceId, edgeId); 473 474 if (useInternalGraph) 475 internalGraph.removeEdge(edgeId); 476 } 477 478 /** 479 * Clear the internal graph if {@link #useInternalGraph} is enable. 480 * 481 * This method is called in {@link #end()} to ensure the next generation 482 * will start freshly anew. 483 */ 484 protected void clearKeptData() { 485 if (useInternalGraph) 486 internalGraph.clear(); 487 } 488}