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}