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.HashSet; 036import java.util.Iterator; 037import java.util.List; 038import java.util.Set; 039 040import org.graphstream.algorithm.util.RandomTools; 041 042/** 043 * Random graph generator. 044 * <p> 045 * This generator creates random graphs of any size <em>n</em> with given 046 * average degree <em>k</em> and binomial degree distribution 047 * <em>B(n, k / (n - 1))</em>. Calling {@link #begin()} creates a clique of size 048 * <em>k</em>. Each call of {@link #nextEvents()} removes a small fraction of 049 * existing edges, adds a new node and connects it randomly with some of the old 050 * nodes. 051 * </p> 052 * 053 * <p> 054 * After <em>n - k</em> steps we obtain a Erdős–Rényí random 055 * graph <em>G(n, p)</em> with <em>p = k / (n - 1)</em>. In other words the 056 * result is the same as if we started with <em>n</em> isolated nodes and 057 * connected each pair of them with probability <em>p</em>. 058 * </p> 059 * 060 * <p> 061 * This generator can work in "non-destructive" mode controlled by a 062 * constructor parameter called <code>allowRemove</code> with default value 063 * <code>true</code>. If this parameter is <code>false</code>, existing edges 064 * are never removed. The obtained graph has the same average degree, but 065 * different degree distribution. This distribution is asymmetric, more 066 * stretched than the binomial distribution, with a peak on the left of the 067 * average degree. This mode is slightly faster and more memory-efficient. Use 068 * it if you do not want edges to be removed and if you do not care about the 069 * degree distribution. 070 * </p> 071 * 072 * <p> 073 * This generator has the ability to add randomly chosen numerical values on 074 * arbitrary attributes on edges or nodes of the graph, and to randomly choose a 075 * direction for edges. For more information see {@link BaseGenerator}. 076 * </p> 077 * 078 * <h2>Example</h2> 079 * 080 * <pre> 081 * Graph graph = new SingleGraph("Random"); 082 * Generator gen = new RandomGenerator(); 083 * gen.addSinkg(graph); 084 * gen.begin(); 085 * while (graph.getNodeCount() < 100 && gen.nextEvents()); 086 * gen.end(); 087 * graph.display(); 088 * </pre> 089 */ 090public class RandomGenerator extends BaseGenerator { 091 /** 092 * the average degree 093 */ 094 protected double averageDegree; 095 /** 096 * Can we remove existing edges? 097 */ 098 protected boolean allowRemove; 099 /** 100 * List storing edge ids. Used to choose edges to remove 101 */ 102 protected List<String> edgeIds; 103 /** 104 * For drawing random subsets 105 */ 106 protected Set<Integer> subset; 107 108 /** 109 * The number of nodes generated so far. 110 */ 111 protected int nodeCount; 112 113 /** 114 * Creates a generator with default average degree of 1. 115 */ 116 public RandomGenerator() { 117 this(1, true, false); 118 } 119 120 /** 121 * Creates a generator with given average degree. 122 * 123 * @param averageDegree 124 * The average degree of the resulting graph. 125 * @throws IllegalArgumentException 126 * if <code>averageDegree</code> is negative 127 */ 128 public RandomGenerator(double averageDegree) { 129 this(averageDegree, true, false); 130 } 131 132 /** 133 * Creates a generator with given average degree. 134 * 135 * @param averageDegree 136 * The average degree of the resulting graph. 137 * @param allowRemove 138 * If true, some existing edges are removed at each step. 139 * @throws IllegalArgumentException 140 * if <code>averageDegree</code> is negative 141 */ 142 public RandomGenerator(double averageDegree, boolean allowRemove) { 143 this(averageDegree, allowRemove, false); 144 } 145 146 /** 147 * Creates a generator with given average degree. 148 * 149 * @param averageDegree 150 * The average degree of the resulting graph. 151 * @param allowRemove 152 * If true, some existing edges are removed at each step. 153 * @param directed 154 * If true, generated edges are directed. 155 * @throws IllegalArgumentException 156 * if <code>averageDegree</code> is negative 157 */ 158 public RandomGenerator(double averageDegree, boolean allowRemove, 159 boolean directed) { 160 super(directed, true); 161 init(averageDegree, allowRemove); 162 } 163 164 /** 165 * Creates a generator with given average degree 166 * 167 * @param averageDegree 168 * The average degree of the resulting graph. 169 * @param allowRemove 170 * If true, some existing edges are removed at each step. 171 * @param directed 172 * If true, generated edges are directed. 173 * @param nodeAttribute 174 * An attribute with this name and a random numeric value is put 175 * on each node. 176 * @param edgeAttribute 177 * An attribute with this name and a random numeric value is put 178 * on each edge. 179 * @throws IllegalArgumentException 180 * if <code>averageDegree</code> is negative 181 */ 182 public RandomGenerator(double averageDegree, boolean allowRemove, 183 boolean directed, String nodeAttribute, String edgeAttribute) { 184 super(directed, true, nodeAttribute, edgeAttribute); 185 init(averageDegree, allowRemove); 186 } 187 188 /** 189 * Starts the generator. A clique of size equal to the average degree is 190 * added. 191 * 192 * @see org.graphstream.algorithm.generator.Generator#begin() 193 * @complexity O(k<sup>2</sup>) where k is the average degree 194 */ 195 public void begin() { 196 if (allowRemove) 197 edgeIds = new ArrayList<String>(); 198 subset = new HashSet<Integer>(); 199 for (nodeCount = 0; nodeCount <= (int) averageDegree; nodeCount++) 200 addNode(nodeCount + ""); 201 for (int i = 0; i < nodeCount; i++) 202 for (int j = i + 1; j < nodeCount; j++) { 203 String edgeId = i + "_" + j; 204 addEdge(edgeId, i + "", j + ""); 205 if (allowRemove) 206 edgeIds.add(edgeId); 207 } 208 } 209 210 /** 211 * If edge removing is allowed, removes a small fraction of the existing 212 * edges. Then adds a new node and connects it randomly with some of the 213 * existing nodes. 214 * @return <code>true</code> 215 * 216 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 217 * @complexity Each call of this method takes on average O(k) steps, where k 218 * is the average degree. Thus generating a graph with n nodes 219 * will take O(nk) time. The space complexity is O(nk) if edge 220 * removing is allowed and O(k) otherwise. 221 */ 222 public boolean nextEvents() { 223 double addProbability = averageDegree / nodeCount; 224 if (allowRemove) 225 removeExistingEdges(1.0 / nodeCount); 226 else 227 addProbability /= 2; 228 addNode(nodeCount + ""); 229 addNewEdges(addProbability); 230 nodeCount++; 231 return true; 232 } 233 234 /* 235 * (non-Javadoc) 236 * 237 * @see org.graphstream.algorithm.generator.BaseGenerator#end() 238 */ 239 @Override 240 public void end() { 241 super.end(); 242 if (allowRemove) { 243 edgeIds.clear(); 244 edgeIds = null; 245 } 246 subset.clear(); 247 subset = null; 248 } 249 250 /** 251 * Constructor helper 252 * 253 * @param averageDegree 254 * The average degree of the resulting graph. 255 * @param allowRemove 256 * If true, some existing edges are removed at each step. 257 */ 258 protected void init(double averageDegree, boolean allowRemove) { 259 if (averageDegree < 0) 260 throw new IllegalArgumentException( 261 "The average degree must be non negative"); 262 this.averageDegree = averageDegree; 263 this.allowRemove = allowRemove; 264 } 265 266 /** 267 * nextEvents helper. Adds edges between the freshly created node and the 268 * old nodes. 269 * 270 * @param p 271 * probability to add each possible edge 272 */ 273 protected void addNewEdges(double p) { 274 RandomTools.randomPsubset(nodeCount, p, subset, random); 275 String nodeId = nodeCount + ""; 276 for (int i : subset) { 277 String edgeId = i + "_" + nodeId; 278 addEdge(edgeId, i + "", nodeId); 279 if (allowRemove) 280 edgeIds.add(edgeId); 281 } 282 } 283 284 /** 285 * nextEvents helper. Removes existing edges. 286 * 287 * @param p 288 * probability to remove each existing edge. 289 */ 290 protected void removeExistingEdges(double p) { 291 RandomTools.randomPsubset(edgeIds.size(), p, subset, random); 292 // Now we can't just remove all the edges with indices in the subset 293 // because 294 // (1) indices change after each removal and (2) shifting will increase 295 // the complexity up to n^2 296 // Instead we are filling the gaps with the elements in the end of the 297 // list 298 int last = edgeIds.size() - 1; 299 while (!subset.isEmpty()) { 300 if (subset.contains(last)) { 301 subset.remove(last); 302 delEdge(edgeIds.get(last)); 303 } else { 304 Iterator<Integer> it = subset.iterator(); 305 int i = it.next(); 306 it.remove(); 307 delEdge(edgeIds.get(i)); 308 edgeIds.set(i, edgeIds.get(last)); 309 } 310 edgeIds.remove(last); 311 last--; 312 } 313 } 314}