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 static java.lang.Math.*;
035
036/**
037 * A generator following the small-world model of Watts and Strogatz.
038 * 
039 * <p>
040 * This generator creates small-world graphs of arbitrary size.
041 * </p>
042 * 
043 * <p>
044 * This model
045 * generates a ring of n nodes where each node is connected to its k nearest
046 * neighbours in the ring (k/2 on each side, which means k must be even).
047 * Then it process each node of the ring in order following the ring, and "rewiring"
048 * each of their edges toward the not yet processed nodes with randomly chosen nodes
049 * with a probability beta. 
050 * </p>
051 *
052 * <h2>Usage</h2>
053 *
054 * <p>
055 * You must provide values for n, k and beta at construction time. You must ensure
056 * that k is event, that n >> k >> log(n) >> 1. Furthermore, beta being a probability
057 * it must be between 0 and 1.
058 * </p>
059 * 
060 * <p>
061 * By default, the generator will produce a placement for nodes using the ``xyz``
062 * attribute.
063 * </p>
064 * 
065 * <p>
066 * This generator will produce the ring of nodes once {@link #begin()} has been
067 * called. Then calling {@link #nextEvents()} will rewire one node at a time
068 * return true until each node is processed, in which case it returns false.
069 * You must then call {@link #end()}. 
070 * </p>
071 * 
072 * <h2>Example</h2>
073 * 
074 * <pre>
075 * Graph graph = new SingleGraph("This is a small world!");
076 * Generator gen = new WattsStrogatzGenerator(20, 2, 0.5);
077 * 
078 * gen.addSink(graph);
079 * gen.begin();
080 * while(gen.nextEvents()) {}
081 * gen.end();
082 * 
083 * graph.display(false); // Node position is provided.
084 * </pre>
085 * 
086 * <h2>Reference</h2>
087 * 
088 * <p>
089 * This generator is based on the Watts-Strogatz model.
090 * </p>
091 * 
092 * @reference Watts, D.J. and Strogatz, S.H.
093 *            "Collective dynamics of 'small-world' networks". Nature 393
094 *            (6684): 409–10. doi:10.1038/30918. PMID 9623998. 1998.
095 */
096public class WattsStrogatzGenerator extends BaseGenerator {
097        /** The number of nodes to generate. */
098        protected int n;
099
100        /** Base degree of each node. */
101        protected int k;
102
103        /** Probability to "rewire" an edge. */
104        protected double beta;
105
106        /** Current rewired node, used to allo nextEvents() iteration. */
107        protected int current;
108
109        /**
110         * New Watts-Strogatz generator.
111         * 
112         * @param n
113         *            The number of nodes to generate.
114         * @param k
115         *            The base degree of each node.
116         * @param beta
117         *            Probability to "rewire" an edge.
118         */
119        public WattsStrogatzGenerator(int n, int k, double beta) {
120                setUseInternalGraph(true);
121
122                if (n <= k)
123                        throw new RuntimeException("parameter n must be >> k");
124                if (beta < 0 || beta > 1)
125                        throw new RuntimeException("parameter beta must be between 0 and 1");
126                if (k % 2 != 0)
127                        throw new RuntimeException("parameter k must be even");
128                if (k < 2)
129                        throw new RuntimeException("parameter k must be >= 2");
130
131                this.n = n;
132                this.k = k;
133                this.beta = beta;
134        }
135
136        public void begin() {
137                double step = (2 * PI) / n;
138                double x = 0;
139
140                for (int i = 0; i < n; i++) {
141                        addNode(nodeId(i), cos(x), sin(x));
142                        x += step;
143                }
144
145                // Add the circle links.
146
147                int kk = k / 2;
148
149                for (int i = 0; i < n; i++) {
150                        for (int j = 1; j <= kk; j++) {
151                                int jj = (i + j) % n;
152                                addEdge(edgeId(i, jj), nodeId(i), nodeId(jj));
153                        }
154                }
155
156                current = 0;
157        }
158
159        public boolean nextEvents() {
160                int kk = k / 2;
161
162                if (current < n) {
163                        for (int j = 1; j <= kk; j++) {
164                                int jj = (current + j) % n;
165
166                                if (random.nextDouble() < beta) {
167                                        delEdge(edgeId(current, jj));
168                                        int newTarget = chooseNewNode(current, jj);
169                                        String edgeId = edgeId(current, newTarget);
170
171                                        if (internalGraph.getEdge(edgeId) == null)
172                                                addEdge(edgeId, nodeId(current), nodeId(newTarget));
173                                }
174                        }
175
176                        current += 1;
177
178                        return true;
179                } else {
180                        return false;
181                }
182        }
183
184        @Override
185        public void end() {
186                super.end();
187        }
188
189        protected String nodeId(int id) {
190                return String.format("%d", id);
191        }
192
193        protected String edgeId(int from, int to) {
194                if (from > to) {
195                        to += from;
196                        from = to - from;
197                        to -= from;
198                }
199
200                return String.format("%d_%d", from, to);
201        }
202
203        protected int chooseNewNode(int avoid, int old) {
204                int newId = 0;
205                boolean exists = true;
206
207                do {
208                        newId = random.nextInt(n);
209                        exists = internalGraph.getEdge(edgeId(avoid, newId)) != null;
210                } while (newId == avoid || exists);
211
212                return newId;
213        }
214}