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.Collections; 035import java.util.HashMap; 036import java.util.HashSet; 037import java.util.LinkedList; 038import java.util.Map; 039import java.util.Set; 040import java.util.concurrent.atomic.AtomicInteger; 041 042import org.graphstream.graph.Graph; 043import org.graphstream.graph.implementations.DefaultGraph; 044 045import static java.lang.Math.min; 046import static java.lang.Math.pow; 047import static java.lang.Math.atan; 048 049/** 050 * Generate a <b>social</b> dynamic graph. Graph is composed of high-connected 051 * group of nodes, modeling organizations, and few connections between 052 * organizations. 053 * 054 * This is done by creating <i>points of interest</i>. Nodes can be interested 055 * by these points or loose them interest. When two nodes are interested by at 056 * least one common point, then there are connected. 057 * 058 * Some probabilities can be set defining the following events : 059 * <ul> 060 * <li>remove a node ;</li> 061 * <li>add a node ;</li> 062 * <li>remove a point of interest ;</li> 063 * <li>add a point of interest.</li> 064 * </ul> 065 * 066 * Initial parameters are : 067 * <ul> 068 * <li>initial count of points of interest ;</li> 069 * <li>initial count of nodes ;</li> 070 * </ul> 071 * 072 * @author Guilhelm Savin 073 * 074 */ 075public class PointsOfInterestGenerator extends BaseGenerator { 076 /** 077 * Defines a point of interest. It is just a set of <i>addicted</i> nodes. 078 */ 079 protected class PointOfInterest { 080 /** 081 * Set of nodes interested by this point. 082 */ 083 Set<Addict> addict; 084 085 PointOfInterest() { 086 addict = new HashSet<Addict>(); 087 } 088 089 /** 090 * Registers a node as an addict of this point. The node will be linked 091 * to all nodes already addict of this point. The list of points of 092 * interest of the node will be updated. 093 * 094 * @param addictA 095 * the addicted node 096 */ 097 void newAddict(Addict addictA) { 098 if (!addict.contains(addictA)) { 099 for (Addict addictB : addict) 100 addictA.link(addictB); 101 102 addict.add(addictA); 103 addictA.pointsOfInterest.add(this); 104 } 105 } 106 107 /** 108 * Unregisters a node. The node will be unlinked to all nodes already 109 * addict of this point. The list of points of interest of the node will 110 * be updated. 111 * 112 * @param addictA 113 * the addicted node 114 */ 115 void delAddict(Addict addictA) { 116 if (addict.contains(addictA)) { 117 addict.remove(addictA); 118 addictA.pointsOfInterest.remove(this); 119 120 for (Addict addictB : addict) 121 addictA.unlink(addictB); 122 } 123 } 124 125 /** 126 * Check is a node is addict of this point. 127 * 128 * @param a 129 * the addict 130 * @return true if a is addict of this point 131 */ 132 boolean isAddict(Addict a) { 133 return addict.contains(a); 134 } 135 } 136 137 protected static class AddictNeighbor { 138 AtomicInteger counter; 139 boolean connected; 140 141 public AddictNeighbor() { 142 this.counter = new AtomicInteger(0); 143 this.connected = false; 144 } 145 146 public AddictNeighbor(AtomicInteger i) { 147 this.counter = i; 148 this.connected = false; 149 } 150 151 int incrementAndGet() { 152 return counter.incrementAndGet(); 153 } 154 155 int decrementAndGet() { 156 return counter.decrementAndGet(); 157 } 158 159 boolean isConnected() { 160 return connected; 161 } 162 } 163 164 /** 165 * Defines data of a node. We have to keep id of the node and to backup 166 * points of interest of this node and neighbor of the node. 167 */ 168 protected class Addict { 169 /** 170 * Id of the node. 171 */ 172 String id; 173 174 /** 175 * List of points of interest of this node. 176 */ 177 LinkedList<PointOfInterest> pointsOfInterest; 178 179 /** 180 * List of neighbors. 181 */ 182 Map<Addict, AddictNeighbor> neighbor; 183 184 Addict(String id) { 185 this.id = id; 186 pointsOfInterest = new LinkedList<PointOfInterest>(); 187 neighbor = new HashMap<Addict, AddictNeighbor>(); 188 } 189 190 /** 191 * Defines a step for a node. Node will iterate over points-of-interest. 192 * For each point p, if node is already interest by p, node will check 193 * if it is still interested by this point (according to 194 * <i>lostInterestProbability</i> probability). Else, node will checked 195 * if it can be interested by p, according to 196 * <i>haveInterestProbability</i> probability and its points count (the 197 * probability will decrease when the count of points increases). 198 */ 199 void step() { 200 // 201 // Avoid that all nodes are interested by the same point. 202 // 203 Collections.shuffle( 204 PointsOfInterestGenerator.this.pointsOfInterest, random); 205 206 for (PointOfInterest poi : PointsOfInterestGenerator.this.pointsOfInterest) { 207 if (pointsOfInterest.contains(poi)) { 208 if (random.nextFloat() < lostInterestProbability) 209 poi.delAddict(this); 210 } else { 211 double p = atan(20.0 212 * min(pointsOfInterest.size(), 213 averagePointsOfInterestCount) 214 / (double) averagePointsOfInterestCount - 10); 215 p = (p - atan(-10)) / (atan(10) - atan(-10)); 216 217 if (random.nextFloat() < haveInterestProbability * (1 - p))// pow( 218 // haveInterestProbability, 219 // 1.2 220 // * 221 // pointsOfInterest.size() 222 // ) 223 // ) 224 poi.newAddict(this); 225 } 226 } 227 } 228 229 /** 230 * Link this node to another. Both nodes will share a common counter. 231 * Links these two nodes will increase the counter and so unlink will 232 * decrease the counter. If counter not exists, it is initialized and 233 * edge is created. Else, if counter is equal to zero, counter is 234 * removed and edge is removed too. 235 * 236 * @param a 237 * the node to link 238 */ 239 void link(Addict a) { 240 if (!neighbor.containsKey(a)) { 241 AddictNeighbor an = new AddictNeighbor(); 242 neighbor.put(a, an); 243 a.neighbor.put(this, an); 244 } 245 246 AddictNeighbor an = neighbor.get(a); 247 248 if (an.incrementAndGet() >= linksNeededToCreateEdge 249 && !an.connected) { 250 if (random.nextDouble() < pow(linkProbability, 251 1.0 / (double) (an.counter.get() 252 - linksNeededToCreateEdge + 1))) { 253 an.connected = true; 254 PointsOfInterestGenerator.this.addEdge(getEdgeId(id, a.id), 255 id, a.id); 256 } 257 } 258 } 259 260 /** 261 * Unlink this node with another. Links-counter between these two nodes 262 * is decreased and edge is removed is needed. 263 * 264 * @param a 265 * the node to unlink 266 */ 267 void unlink(Addict a) { 268 if (neighbor.containsKey(a)) { 269 if (neighbor.get(a).decrementAndGet() < linksNeededToCreateEdge) { 270 neighbor.remove(a); 271 a.neighbor.remove(this); 272 PointsOfInterestGenerator.this.delEdge(getEdgeId(id, a.id)); 273 } 274 } 275 } 276 277 /** 278 * Unlink all neighbor. 279 */ 280 void fullUnlink() { 281 for (Addict a : neighbor.keySet()) { 282 a.neighbor.remove(this); 283 PointsOfInterestGenerator.this.delEdge(getEdgeId(id, a.id)); 284 } 285 286 neighbor.clear(); 287 } 288 } 289 290 protected static String getEdgeId(String nodeA, String nodeB) { 291 return nodeA.compareTo(nodeB) < 0 ? String.format("%s---%s", nodeA, 292 nodeB) : String.format("%s---%s", nodeB, nodeA); 293 } 294 295 public static enum Parameter { 296 INITIAL_PEOPLE_COUNT, ADD_PEOPLE_PROBABILITY, DEL_PEOPLE_PROBABILITY, INITIAL_POINT_OF_INTEREST_COUNT, AVERAGE_POINTS_OF_INTEREST_COUNT, ADD_POINT_OF_INTEREST_PROBABILITY, DEL_POINT_OF_INTEREST_PROBABILITY, HAVE_INTEREST_PROBABILITY, LOST_INTEREST_PROBABILITY, LINKS_NEEDED_TO_CREATE_EDGE, LINK_PROBABILITY 297 } 298 299 /** 300 * Initial count of nodes. 301 */ 302 protected int initialPeopleCount; 303 304 /** 305 * Probability to add a node during a step. 306 */ 307 protected float addPeopleProbability; 308 309 /** 310 * Probability to remove a node during a step. 311 */ 312 protected float delPeopleProbability; 313 314 /** 315 * Probability that a node becomes interested in a point-of-interest it was 316 * not already interested. 317 */ 318 protected float haveInterestProbability; 319 320 /** 321 * Probability that a node looses its interest for a point-of-interest. 322 */ 323 protected float lostInterestProbability; 324 325 /** 326 * Initial count of point-of-interest. 327 */ 328 protected int initialPointOfInterestCount; 329 330 /** 331 * Probability to add a new point-of-interest. 332 */ 333 protected float addPointOfInterestProbability; 334 335 /** 336 * Probability to remove a point-of-interest. 337 */ 338 protected float delPointOfInterestProbability; 339 340 /** 341 * Average points of interest by addict. 342 */ 343 protected float averagePointsOfInterestCount; 344 345 protected int linksNeededToCreateEdge; 346 347 protected float linkProbability; 348 349 /** 350 * List of addicts. 351 */ 352 protected LinkedList<Addict> addicts; 353 /** 354 * List of point-of-interest. 355 */ 356 protected LinkedList<PointOfInterest> pointsOfInterest; 357 358 private long currentId; 359 360 private long currentStep; 361 362 public PointsOfInterestGenerator() { 363 setUseInternalGraph(false); 364 365 initialPeopleCount = 500; 366 addPeopleProbability = delPeopleProbability = 0.001f; 367 368 haveInterestProbability = 0.001f; 369 lostInterestProbability = 0.005f; 370 371 initialPointOfInterestCount = 15; 372 addPointOfInterestProbability = delPointOfInterestProbability = 0.001f; 373 374 linkProbability = 0.3f; 375 averagePointsOfInterestCount = 3; 376 linksNeededToCreateEdge = 2; 377 378 addicts = new LinkedList<Addict>(); 379 pointsOfInterest = new LinkedList<PointOfInterest>(); 380 381 currentStep = 0; 382 } 383 384 public void setParameter(Parameter p, Object value) { 385 switch (p) { 386 case INITIAL_PEOPLE_COUNT: 387 this.initialPeopleCount = (Integer) value; 388 break; 389 case ADD_PEOPLE_PROBABILITY: 390 this.addPeopleProbability = (Float) value; 391 break; 392 case DEL_PEOPLE_PROBABILITY: 393 this.delPeopleProbability = (Float) value; 394 break; 395 case INITIAL_POINT_OF_INTEREST_COUNT: 396 this.initialPointOfInterestCount = (Integer) value; 397 break; 398 case AVERAGE_POINTS_OF_INTEREST_COUNT: 399 this.averagePointsOfInterestCount = (Float) value; 400 break; 401 case ADD_POINT_OF_INTEREST_PROBABILITY: 402 this.addPointOfInterestProbability = (Float) value; 403 break; 404 case DEL_POINT_OF_INTEREST_PROBABILITY: 405 this.delPointOfInterestProbability = (Float) value; 406 break; 407 case HAVE_INTEREST_PROBABILITY: 408 this.haveInterestProbability = (Float) value; 409 break; 410 case LOST_INTEREST_PROBABILITY: 411 this.lostInterestProbability = (Float) value; 412 break; 413 case LINKS_NEEDED_TO_CREATE_EDGE: 414 this.linksNeededToCreateEdge = (Integer) value; 415 break; 416 case LINK_PROBABILITY: 417 this.linkProbability = ((Number) value).floatValue(); 418 break; 419 } 420 } 421 422 /** 423 * Add initial count of points of interest, and initial count of people. 424 * 425 * @see org.graphstream.algorithm.generator.Generator#begin() 426 */ 427 public void begin() { 428 pointsOfInterest.clear(); 429 430 for (int i = 0; i < initialPointOfInterestCount; i++) 431 addPointOfInterest(); 432 433 for (int i = 0; i < initialPeopleCount; i++) 434 addAddict(); 435 } 436 437 /** 438 * Step of the generator. Try to remove a node according to the 439 * {@link #delPeopleProbability}. Try to add a node according to the 440 * {@link #addPeopleProbability}. Try to remove a point of interest 441 * according to the {@link #delPointOfInterestProbability}. Try to add a 442 * point of interest according to the {@link #addPointOfInterestProbability} 443 * . Then, step of <i>addicts</i>. 444 * 445 * @see PointsOfInterestGenerator.Addict#step() 446 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 447 */ 448 public boolean nextEvents() { 449 sendStepBegins(sourceId, currentStep++); 450 451 if (random.nextDouble() < delPeopleProbability) 452 killSomeone(); 453 454 if (random.nextDouble() < addPeopleProbability) 455 addAddict(); 456 457 if (random.nextDouble() < delPointOfInterestProbability) 458 removeRandomPointOfInterest(); 459 460 if (random.nextDouble() < addPointOfInterestProbability) 461 addPointOfInterest(); 462 463 for (Addict a : addicts) 464 a.step(); 465 466 return true; 467 } 468 469 /* 470 * (non-Javadoc) 471 * 472 * @see org.graphstream.algorithm.generator.Generator#end() 473 */ 474 @Override 475 public void end() { 476 super.end(); 477 } 478 479 protected void addPointOfInterest() { 480 pointsOfInterest.add(new PointOfInterest()); 481 } 482 483 protected void removePointOfInterest(PointOfInterest poi) { 484 pointsOfInterest.remove(poi); 485 486 for (Addict a : poi.addict) 487 poi.delAddict(a); 488 } 489 490 protected void removeRandomPointOfInterest() { 491 pointsOfInterest.remove(random.nextInt(pointsOfInterest.size())); 492 } 493 494 protected void addAddict() { 495 Addict a = new Addict(String.format("%08x", currentId++)); 496 497 addicts.add(a); 498 addNode(a.id); 499 } 500 501 protected void killAddict(Addict a) { 502 while (a.pointsOfInterest.size() > 0) 503 a.pointsOfInterest.peek().delAddict(a); 504 505 a.fullUnlink(); 506 507 addicts.remove(a); 508 delNode(a.id); 509 510 a.id = null; 511 a.pointsOfInterest.clear(); 512 a.pointsOfInterest = null; 513 } 514 515 protected void killSomeone() { 516 killAddict(addicts.get(random.nextInt(addicts.size()))); 517 } 518 519 public static void main(String... args) { 520 PointsOfInterestGenerator gen = new PointsOfInterestGenerator(); 521 522 gen.setParameter(Parameter.INITIAL_PEOPLE_COUNT, 300); 523 gen.setParameter(Parameter.ADD_PEOPLE_PROBABILITY, 0.01f); 524 gen.setParameter(Parameter.DEL_PEOPLE_PROBABILITY, 0.01f); 525 gen.setParameter(Parameter.INITIAL_POINT_OF_INTEREST_COUNT, 30); 526 gen.setParameter(Parameter.AVERAGE_POINTS_OF_INTEREST_COUNT, 5.0f); 527 gen.setParameter(Parameter.ADD_POINT_OF_INTEREST_PROBABILITY, 0.0f); 528 gen.setParameter(Parameter.DEL_POINT_OF_INTEREST_PROBABILITY, 0.0f); 529 gen.setParameter(Parameter.HAVE_INTEREST_PROBABILITY, 0.1f); 530 gen.setParameter(Parameter.LOST_INTEREST_PROBABILITY, 0.001f); 531 gen.setParameter(Parameter.LINKS_NEEDED_TO_CREATE_EDGE, 2); 532 gen.setParameter(Parameter.LINK_PROBABILITY, 0.05f); 533 534 Graph g = new DefaultGraph("theGraph"); 535 gen.addSink(g); 536 537 String stylesheet = "graph { " + " fill-color: white;" 538 + " padding: 50px;" + "}" + "node { " + " fill-color: black;" 539 + "}" + "edge {" + " fill-color: black;" + "}"; 540 541 g.addAttribute("ui.stylesheet", stylesheet); 542 g.addAttribute("ui.quality"); 543 // g.addAttribute( "ui.antialias" ); 544 545 g.display(); 546 547 gen.begin(); 548 549 while (true) { 550 gen.nextEvents(); 551 552 try { 553 Thread.sleep(60); 554 } catch (Exception e) { 555 e.printStackTrace(); 556 } 557 } 558 } 559}