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 org.graphstream.algorithm.Toolkit; 035 036/** 037 * This is a graph generator that generates dynamic random graphs. 038 * 039 * <u>The principle:</u> 040 * 041 * <p> 042 * A graph consists in a set of vertices and a set of edges. The dynamic relies 043 * on 4 kinds of steps of events: at each step: 044 * <ul> 045 * <li>a subset of nodes is removed</li> 046 * <li>a subset of nodes is added</li> 047 * <li>a subset of edges is removed (in the current version, edges that are 048 * removed are those that were attached to nodes that disappear)</li> 049 * <li>a subset of edges is added</li> 050 * </ul> 051 * </p> 052 * 053 * <p> 054 * This generator is characterized by: 055 * <ul> 056 * <li>The parameters: 057 * <ul> 058 * <li>number of vertices</li> 059 * <li>maximum mean degree</li> 060 * </ul> 061 * </li> 062 * <li>The constraints: 063 * <ul> 064 * <li>graph nervosity</li> 065 * <li>creation links rules</li> 066 * </ul> 067 * </li> 068 * <li>The metrics: 069 * <ul> 070 * <li>mean number of vertices and edges</li> 071 * <li>mean age of vertices and edges</li> 072 * <li>mean distribution of degree</li> 073 * <li>mean number of connected components</li> 074 * <li>...</li> 075 * <li>...</li> 076 * </ul> 077 * </li> 078 * </ul> 079 * </p> 080 * 081 * <p> 082 * How to build such graphs ? There exist at least one mathematical function for 083 * doing that f(step) = nbVertices*log(step)/log(step+"Pente") the larger 084 * "Pente", the softer the "pente" of the curve. Given f(step), it is possible 085 * to compute nbCreations and nbDeletions together with the graph nervosity. 086 * f(step) represents the number of vertices that should be present within the 087 * graph given the step and the value of the parameter "Pente". However, as our 088 * graph is dynamic, some vertices may be deleted while some other vertices may 089 * be added to the graph. 090 * 091 * Question: could it be possible to build a dynamic graph that reaches a stable 092 * state (stabilization of the number of vertices, and stabilization of some 093 * other properties), just by adding some constraints/characteristics on each 094 * node? 095 * 096 * @author Frédéric Guinand 097 * @since 20080616 098 */ 099public class RandomFixedDegreeDynamicGraphGenerator extends BaseGenerator { 100 /** 101 * Average number of vertices. 102 */ 103 protected int nbVertices; 104 105 /** 106 * Limit for the mean degree of nodes. 107 */ 108 protected double meanDegreeLimit; 109 110 /** 111 * Nervousness of the generator. It allows to influence the number of nodes 112 * removed at each step and so the number of new nodes added. 113 */ 114 protected double nervousness; 115 116 /** 117 * Current step of the generator. 118 */ 119 protected int step = 1; 120 121 /** 122 * Influence the number of nodes created at each step. 123 */ 124 protected int deltaStep = 100; 125 126 /** 127 * Used to generate node ids. 128 */ 129 protected int currentNodeId = 0; 130 131 /** 132 * Create a new RandomFixedDegreeDynamicGraphGenerator generator with 133 * default values for attributes. 134 * 135 * @see #RandomFixedDegreeDynamicGraphGenerator(int, double, double) 136 */ 137 public RandomFixedDegreeDynamicGraphGenerator() { 138 this(50, 5, 0.1f); 139 } 140 141 /** 142 * Create a new RandomFixedDegreeDynamicGraphGenerator generator. 143 * 144 * @param nbVertices 145 * The number of vertices. 146 * @param meanDegreeLimit 147 * The average degree. 148 * @param nervousness 149 * The nervousness. 150 */ 151 public RandomFixedDegreeDynamicGraphGenerator(int nbVertices, 152 double meanDegreeLimit, double nervousness) { 153 setUseInternalGraph(true); 154 155 this.nbVertices = nbVertices; 156 this.meanDegreeLimit = meanDegreeLimit; 157 this.nervousness = nervousness; 158 } 159 160 /** 161 * This method computes the mean degree of the graph. 162 */ 163 public double meanDegree() { 164 return 2.0 * internalGraph.getEdgeCount() 165 / (double) internalGraph.getNodeCount(); 166 } 167 168 protected String getEdgeId(String src, String trg) { 169 if (src.compareTo(trg) < 0) 170 return String.format("%s_%s", src, trg); 171 172 return String.format("%s_%s", trg, src); 173 } 174 175 /* 176 * (non-Javadoc) 177 * 178 * @see org.graphstream.algorithm.generator.Generator#begin() 179 */ 180 public void begin() { 181 step = 0; 182 } 183 184 /** 185 * Step of the generator. Some nodes will be removed according to the 186 * nervousness, then new nodes and new edges will be added. 187 * 188 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 189 */ 190 public boolean nextEvents() { 191 int nbCreations, nbSuppressions, nbCreationsEdges; 192 String dead, source, dest; 193 194 sendStepBegins(sourceId, step); 195 196 nbSuppressions = (int) (random.nextFloat() * (internalGraph 197 .getNodeCount() * nervousness)); 198 199 for (int r = 1; r <= nbSuppressions; r++) { 200 dead = Toolkit.randomNode(internalGraph, random).getId(); 201 delNode(dead); 202 } 203 204 nbCreations = (int) (random.nextFloat() * ((nbVertices - internalGraph 205 .getNodeCount()) * Math.log(step) / Math.log(step + deltaStep))); 206 207 for (int c = 1; c <= nbCreations; c++) { 208 String nodeId = String.format("%d", currentNodeId++); 209 210 addNode(nodeId); 211 } 212 213 double degreMoyen = meanDegree(); 214 215 nbCreationsEdges = (int) (random.nextFloat() * (((meanDegreeLimit - degreMoyen) * (internalGraph 216 .getNodeCount() / 2)) * Math.log(step) / Math.log(step 217 + deltaStep))); 218 219 if (internalGraph.getNodeCount() > 1) { 220 for (int c = 1; c <= nbCreationsEdges; c++) { 221 do { 222 source = Toolkit.randomNode(internalGraph, random).getId(); 223 dest = Toolkit.randomNode(internalGraph, random).getId(); 224 } while (source.equals(dest)); 225 226 String idEdge = getEdgeId(source, dest); 227 228 while (internalGraph.getEdge(idEdge) != null || source.equals(dest)) { 229 dest = Toolkit.randomNode(internalGraph, random).getId(); 230 idEdge = getEdgeId(source, dest); 231 } 232 233 addEdge(idEdge, source, dest); 234 } 235 } 236 237 step++; 238 239 return false; 240 } 241 242 /* 243 * (non-Javadoc) 244 * 245 * @see org.graphstream.algorithm.generator.Generator#end() 246 */ 247 @Override 248 public void end() { 249 super.end(); 250 } 251}