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}