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;
035
036/**
037 * Scale-free tree generator using the preferential attachment rule as
038 * defined in the Barabási-Albert model.
039 * 
040 * <p>
041 * THIS GENERATOR IS DEPRECATED, USE THE {@link BarabasiAlbertGenerator} INSTEAD.
042 * </p>
043 * 
044 * <p>
045 * This is a very simple graph generator that generates a tree using the
046 * preferential attachment rule defined in the Barabási-Albert model: nodes are
047 * generated one by one, and each time attached by an edge to another node that
048 * has more chance to chosen if it already has lots of nodes attached to it.
049 * </p>
050 * 
051 * <p>
052 * The more this generator is iterated, the more nodes are generated. It can
053 * therefore generate trees of any size.
054 * </p>
055 * 
056 * @reference Albert-László Barabási & Réka Albert
057 *            "Emergence of scaling in random networks". Science 286: 509–512.
058 *            October 1999. doi:10.1126/science.286.5439.509.
059 * 
060 * @since 20061128
061 */
062@Deprecated
063public class PreferentialAttachmentGenerator extends BaseGenerator {
064        /**
065         * Degree of each node.
066         */
067        protected ArrayList<Integer> degrees;
068
069        /**
070         * Maximal degree at time t.
071         */
072        protected int degreeMax = 0;
073
074        /**
075         * Number of edges.
076         */
077        protected int edgesCount = 0;
078
079        /**
080         * New generator.
081         */
082        public PreferentialAttachmentGenerator() {
083                directed = false;
084        }
085
086        /**
087         * Start the generator. A single node is added.
088         * 
089         * @see org.graphstream.algorithm.generator.Generator#begin()
090         */
091        public void begin() {
092                this.degrees = new ArrayList<Integer>();
093                this.degreeMax = 0;
094
095                addNode("0");
096                degrees.add(0);
097        }
098
099        /**
100         * Step of the generator. Add a node and try to connect it with some others.
101         * 
102         * The complexity of this method is O(n) with n the number of nodes actually
103         * in the graph.
104         * 
105         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
106         */
107        public boolean nextEvents() {
108                // Generate a new node.
109
110                int index = degrees.size();
111                String id = Integer.toString(index);
112
113                addNode(id);
114                degrees.add(0);
115
116                // Compute the attachment probability of each previously added node
117
118                int sumDeg = edgesCount * 2;
119
120                // Choose the node to attach to.
121
122                double sumProba = 0;
123                double rnd = random.nextDouble();
124                int otherIdx = -1;
125
126                for(int i = 0; i < index; ++i) {
127                        double proba = sumDeg == 0 ? 1 : degrees.get(i) / ((double) sumDeg);
128
129                        sumProba += proba;
130
131                        if (sumProba > rnd) {
132                                otherIdx = i;
133                                i = index;// Stop the loop.
134                        }
135                }
136
137                // Attach to the other node.
138
139                if (otherIdx >= 0) {
140                        String oid = Integer.toString(otherIdx);
141                        String eid = id + "_" + oid;
142
143                        addEdge(eid, oid, id);
144                        edgesCount++;
145                        degrees.set(otherIdx, degrees.get(otherIdx) + 1);
146                        degrees.set(index, degrees.get(index) + 1);
147                } else {
148                        System.err.printf("PreferentialAttachmentGenerator: Aieuu!%n");
149                }
150
151                // It is always possible to add an element.
152
153                return true;
154        }
155
156        /**
157         * Clean degrees.
158         * 
159         * @see org.graphstream.algorithm.generator.Generator#end()
160         */
161        @Override
162        public void end() {
163                degrees.clear();
164                degrees = null;
165                degreeMax = 0;
166                super.end();
167        }
168}