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.Set;
037
038/**
039 * Scale-free graph generator using the preferential attachment rule as defined
040 * in the Barabási-Albert model.
041 * 
042 * <p>
043 * This is a very simple graph generator that generates a graph using the
044 * preferential attachment rule defined in the Barabási-Albert model: nodes are
045 * generated one by one, and each time attached by one or more edges other
046 * nodes. The other nodes are chosen using a biased random selection giving more
047 * chance to a node if it has a high degree.
048 * </p>
049 * 
050 * <h2>Usage</h2>
051 * 
052 * <p>
053 * The more this generator is iterated, the more nodes are generated. It can
054 * therefore generate graphs of any size. One node is generated at each call to
055 * {@link #nextEvents()}. At each node added at least one new edge is added. The
056 * number of edges added at each step is given by the
057 * {@link #getMaxLinksPerStep()}. However by default the generator creates a
058 * number of edges per new node chosen randomly between 1 and
059 * {@link #getMaxLinksPerStep()}. To have exactly this number of edges at each
060 * new node, use {@link #setExactlyMaxLinksPerStep(boolean)}.
061 * </p>
062 * 
063 * <h2>Complexity</h2>
064 * 
065 * For each new step, the algorithm act in O(n) with n the number of
066 * nodes if 1 max edge per new node is created, else the complexity
067 * is O(nm) if m max edge per new node is created.
068 * 
069 * <h2>Example</h2>
070 * 
071 * <pre>
072 * Graph graph = new SingleGraph("Barabàsi-Albert");
073 * // Between 1 and 3 new links per node added.
074 * Generator gen = new BarabasiAlbertGenerator(3);
075 * // Generate 100 nodes:
076 * gen.addSink(graph); 
077 * gen.begin();
078 * for(int i=0; i<100; i++) {
079 *              gen.nextEvents();
080 * }
081 * gen.end();
082 * graph.display();
083 * </pre>
084 * 
085 * @reference Albert-László Barabási & Réka Albert
086 *            "Emergence of scaling in random networks", Science 286: 509–512.
087 *            October 1999. doi:10.1126/science.286.5439.509.
088 */
089public class BarabasiAlbertGenerator extends BaseGenerator {
090        /**
091         * Degree of each node.
092         */
093        protected ArrayList<Integer> degrees;
094
095        /**
096         * The maximum number of links created when a new node is added.
097         */
098        protected int maxLinksPerStep;
099
100        /**
101         * Does the generator generates exactly {@link #maxLinksPerStep}.
102         */
103        protected boolean exactlyMaxLinksPerStep = false;
104        
105        /**
106         * The sum of degrees of all nodes
107         */
108        protected int sumDeg;
109        
110        /**
111         * The sum of degrees of nodes not connected to the new node
112         */
113        protected int sumDegRemaining;
114        
115        /**
116         * Set of indices of nodes connected to the new node
117         */
118        protected Set<Integer> connected;
119
120        /**
121         * New generator.
122         */
123        public BarabasiAlbertGenerator() {
124                this(1, false);
125        }
126
127        public BarabasiAlbertGenerator(int maxLinksPerStep) {
128                this(maxLinksPerStep, false);
129        }
130
131        public BarabasiAlbertGenerator(int maxLinksPerStep,
132                        boolean exactlyMaxLinksPerStep) {
133                this.directed = false;
134                this.maxLinksPerStep = maxLinksPerStep;
135                this.exactlyMaxLinksPerStep = exactlyMaxLinksPerStep;
136        }
137
138        /**
139         * Maximum number of edges created when a new node is added.
140         * 
141         * @return The maximum number of links per step.
142         */
143        public int getMaxLinksPerStep() {
144                return maxLinksPerStep;
145        }
146
147        /**
148         * True if the generator produce exactly {@link #getMaxLinksPerStep()}, else
149         * it produce a random number of links ranging between 1 and
150         * {@link #getMaxLinksPerStep()}.
151         * 
152         * @return Does the generator generates exactly
153         *         {@link #getMaxLinksPerStep()}.
154         */
155        public boolean produceExactlyMaxLinkPerStep() {
156                return exactlyMaxLinksPerStep;
157        }
158
159        /**
160         * Set how many edge (maximum) to create for each new node added.
161         * 
162         * @param max
163         *            The new maximum, it must be strictly greater than zero.
164         */
165        public void setMaxLinksPerStep(int max) {
166                maxLinksPerStep = max > 0 ? max : 1;
167        }
168
169        /**
170         * Set if the generator produce exactly {@link #getMaxLinksPerStep()}
171         * (true), else it produce a random number of links ranging between 1 and
172         * {@link #getMaxLinksPerStep()} (false).
173         * 
174         * @param on
175         *            Does the generator generates exactly
176         *            {@link #getMaxLinksPerStep()}.
177         */
178        public void setExactlyMaxLinksPerStep(boolean on) {
179                exactlyMaxLinksPerStep = on;
180        }
181
182        /**
183         * Start the generator. Two nodes connected by edge are added.
184         * 
185         * @see org.graphstream.algorithm.generator.Generator#begin()
186         */
187        public void begin() {
188                addNode("0");
189                addNode("1");
190                addEdge("0_1", "0", "1");
191                degrees = new ArrayList<Integer>();
192                degrees.add(1);
193                degrees.add(1);
194                sumDeg = 2;
195                connected = new HashSet<Integer>();
196        }
197
198        /**
199         * Step of the generator. Add a node and try to connect it with some others.
200         * 
201         * The number of links is randomly chosen between 1 and the maximum number
202         * of links per step specified in {@link #setMaxLinksPerStep(int)}.
203         * 
204         * The complexity of this method is O(n) with n the number of nodes if the
205         * number of edges created per new node is 1, else it is O(nm) with m the
206         * number of edges generated per node.
207         * 
208         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
209         */
210        public boolean nextEvents() {
211                // Generate a new node.
212                int nodeCount = degrees.size();
213                String newId = nodeCount + "";
214                addNode(newId);
215
216                // Attach to how many existing nodes?
217                int n = maxLinksPerStep;
218                if (!exactlyMaxLinksPerStep)
219                        n = random.nextInt(n) + 1;
220                n = Math.min(n, nodeCount);
221
222                // Choose the nodes to attach to.
223                sumDegRemaining = sumDeg;
224                for (int i = 0; i < n; i++)
225                        chooseAnotherNode();
226                
227                for (int i : connected) {
228                        addEdge(newId + "_" + i, newId, i + "");
229                        degrees.set(i, degrees.get(i) + 1);
230                }
231                connected.clear();
232                degrees.add(n);
233                sumDeg += 2 * n;
234
235                // It is always possible to add an element.
236                return true;
237        }
238        
239        /**
240         * Choose randomly one of the remaining nodes 
241         */
242        protected void chooseAnotherNode() {
243                int r = random.nextInt(sumDegRemaining);
244                int runningSum = 0;
245                int i = 0;
246                while (runningSum <= r) {
247                        if (!connected.contains(i))
248                                runningSum += degrees.get(i);
249                        i++;
250                }
251                i--;
252                connected.add(i);
253                sumDegRemaining -= degrees.get(i);
254        }
255
256
257        /**
258         * Clean degrees.
259         * 
260         * @see org.graphstream.algorithm.generator.Generator#end()
261         */
262        @Override
263        public void end() {
264                degrees.clear();
265                degrees = null;
266                connected = null;
267                super.end();
268        }
269}