contrib/psg/src/peersim/dynamics/WireScaleFreeDM.java

   1 /*
   2  * Copyright (c) 2003-2005 The BISON Project
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  */
  18
  19 package peersim.dynamics;
  20
  21 import peersim.graph.Graph;
  22 import peersim.config.*;
  23 import peersim.core.*;
  24
  25 /**
  26  * Wires a scale free graph using a method described in
  27  * <a href="http://xxx.lanl.gov/abs/cond-mat/0106144">this paper</a>.
  28  * It is an incremental technique, where the new nodes are connected to
  29  * the two ends of an edge that is already in the network.
  30  * This model always wires undirected links.
  31  */
  32 public class WireScaleFreeDM extends WireGraph {
  33
  34
  35 //--------------------------------------------------------------------------
  36 // Constants
  37 //--------------------------------------------------------------------------
  38
  39 /**
  40  * The number of edges added to each new
  41  * node (apart from those forming the initial network) is twice this
  42  * value.
  43  * @config
  44  */
  45 private static final String PAR_EDGES = "k";
  46
  47
  48 //--------------------------------------------------------------------------
  49 // Fields
  50 //--------------------------------------------------------------------------
  51
  52
  53 /** The number of edges created for a new node is 2*k. */
  54 private final int k;
  55
  56
  57 //--------------------------------------------------------------------------
  58 // Constructor
  59 //--------------------------------------------------------------------------
  60
  61 /**
  62  * Standard constructor that reads the configuration parameters.
  63  * Invoked by the simulation engine.
  64  * @param prefix the configuration prefix for this class
  65  */
  66 public WireScaleFreeDM(String prefix)
  67 {
  68         super(prefix);
  69         k = Configuration.getInt(prefix + "." + PAR_EDGES);
  70 }
  71
  72
  73 //--------------------------------------------------------------------------
  74 // Methods
  75 //--------------------------------------------------------------------------
  76
  77 /**
  78  * Wires a scale free graph using a method described in
  79  * <a href="http://xxx.lanl.gov/abs/cond-mat/0106144">this paper</a>.
  80  * It is an incremental technique, where the new nodes are connected to
  81  * the two ends of an edge that is already in the network.
  82  * This model always wires undirected links.
  83 */
  84 public void wire(Graph g) {
  85
  86         int nodes=g.size();
  87         int[] links = new int[4*k*nodes];
  88
  89         // Initial number of nodes connected as a clique
  90         int clique = (k > 3 ? k : 3);
  91
  92         // Add initial edges, to form a clique
  93         int len=0;
  94         for (int i=0; i < clique; i++)
  95         for (int j=0; j < clique; j++)
  96         {
  97                 if (i != j)
  98                 {
  99                         g.setEdge(i,j);
 100                         g.setEdge(j,i);
 101                         links[len*2] = i;
 102                         links[len*2+1] = j;
 103                         len++;
 104                 }
 105         }
 106
 107         for (int i=clique; i < nodes; i++)
 108         for (int l=0; l < k; l++)
 109         {
 110                 int edge = CommonState.r.nextInt(len);
 111                 int m = links[edge*2];
 112                 int j = links[edge*2+1];
 113                 g.setEdge(i, m);
 114                 g.setEdge(m, i);
 115                 g.setEdge(j, m);
 116                 g.setEdge(m, j);
 117                 links[len*2] = i;
 118                 links[len*2+1] = m;
 119                 len++;
 120                 links[len*2] = j;
 121                 links[len*2+1] = m;
 122                 len++;
 123         }
 124 }
 125
 126 }