contrib/psg/src/peersim/graph/GraphFactory.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.graph;
  20
  21 import java.util.*;
  22
  23 /**
  24 * Contains static methods for wiring certain kinds of graphs. The general
  25 * contract of all methods is that they accept any graph and add edges
  26 * as specified in the documentation.
  27 */
  28 public class GraphFactory {
  29
  30 /** Disable instance construction */
  31 private GraphFactory() {}
  32
  33 // ===================== public static methods ======================
  34 // ==================================================================
  35
  36 /**
  37 * Wires a ring lattice.
  38 * The added connections are defined as follows. If k is even, links to
  39 * i-k/2, i-k/2+1, ..., i+k/2 are added (but not to i), thus adding an
  40 * equal number of predecessors and successors.
  41 * If k is odd, then we add one more successors than predecessors.
  42 * For example, for k=4: 2 predecessors, 2 successors.
  43 * For k=5: 2 predecessors, 3 successors.
  44 * For k=1: each node is linked only to its successor.
  45 * All values are understood mod n to make the lattice circular, where n is the
  46 * number of nodes in g.
  47 * @param g the graph to be wired
  48 * @param k lattice parameter
  49 * @return returns g for convenience
  50 */
  51 public static Graph wireRingLattice(Graph g, int k) {
  52
  53         final int n = g.size();
  54
  55         int pred = k/2;
  56         int succ = k-pred;
  57
  58         for(int i=0; i<n; ++i)
  59         for(int j=-pred; j<=succ; ++j)
  60         {
  61                 if( j==0 ) continue;
  62                 final int v = (i+j+n)%n;
  63                 g.setEdge(i,v);
  64         }
  65         return g;
  66 }
  67
  68 // -------------------------------------------------------------------
  69
  70 /**
  71 * Watts-Strogatz model. A bit modified though: by default assumes a directed
  72 * graph. This means that directed
  73 * links are re-wired, and the undirected edges in the original (undirected)
  74 * lattice are modeled
  75 * by double directed links pointing in opposite directions. Rewiring is done
  76 * with replacement, so the possibility of wiring two links to the same target
  77 * is positive (though very small).
  78 * <p>
  79 * Note that it is possible to pass an undirected graph as a parameter. In that
  80 * case the output is the directed graph produced by the method, converted to
  81 * an undirected graph by dropping directionality of the edges. This graph is
  82 * still not from the original undirected WS model though.
  83 * @param g the graph to be wired
  84 * @param k lattice parameter: this is the out-degree of a node in the
  85 * ring lattice before rewiring
  86 * @param p the probability of rewiring each
  87 * @param r source of randomness
  88 * @return returns g for convenience
  89 */
  90 public static Graph wireWS( Graph g, int k, double p, Random r ) {
  91 //XXX unintuitive to call it WS due to the slight mods
  92         final int n = g.size();
  93         for(int i=0; i<n; ++i)
  94         for(int j=-k/2; j<=k/2; ++j)
  95         {
  96                 if( j==0 ) continue;
  97                 int newedge = (i+j+n)%n;
  98                 if( r.nextDouble() < p )
  99                 {
 100                         newedge = r.nextInt(n-1);
 101                         if( newedge >= i ) newedge++; // random _other_ node
 102                 }
 103                 g.setEdge(i,newedge);
 104         }
 105         return g;
 106 }
 107
 108 // -------------------------------------------------------------------
 109
 110 /**
 111 * Random graph. Generates randomly k directed edges out of each node.
 112 * The neighbors
 113 * (edge targets) are chosen randomly without replacement from the nodes of the
 114 * graph other than the source node (i.e. no loop edge is added).
 115 * If k is larger than N-1 (where N is the number of nodes) then k is set to
 116 * be N-1 and a complete graph is returned.
 117 * @param g the graph to be wired
 118 * @param k samples to be drawn for each node
 119 * @param r source of randomness
 120 * @return returns g for convenience
 121 */
 122 public static Graph wireKOut( Graph g, int k, Random r ) {
 123
 124         final int n = g.size();
 125         if( n < 2 ) return g;
 126         if( n <= k ) k=n-1;
 127         int[] nodes = new int[n];
 128         for(int i=0; i<nodes.length; ++i) nodes[i]=i;
 129         for(int i=0; i<n; ++i)
 130         {
 131                 int j=0;
 132                 while(j<k)
 133                 {
 134                         int newedge = j+r.nextInt(n-j);
 135                         int tmp = nodes[j];
 136                         nodes[j] = nodes[newedge];
 137                         nodes[newedge] = tmp;
 138                         if( nodes[j] != i )
 139                         {
 140                                 g.setEdge(i,nodes[j]);
 141                                 j++;
 142                         }
 143                 }
 144         }
 145         return g;
 146 }
 147
 148 // -------------------------------------------------------------------
 149
 150 /**
 151 * A sink star.
 152 * Wires a sink star topology adding a link to 0 from all other nodes.
 153 * @param g the graph to be wired
 154 * @return returns g for convenience
 155 */
 156 public static Graph wireStar( Graph g ) {
 157
 158         final int n = g.size();
 159         for(int i=1; i<n; ++i) g.setEdge(i,0);
 160         return g;
 161 }
 162
 163 // -------------------------------------------------------------------
 164
 165 /**
 166 * A regular rooted tree.
 167 * Wires a regular rooted tree. The root is 0, it has links to 1,...,k.
 168 * In general, node i has links to i*k+1,...,i*k+k.
 169 * @param g the graph to be wired
 170 * @param k the number of outgoing links of nodes in the tree (except
 171 * leaves that have zero out-links, and exactly one node that might have
 172 * less than k).
 173 * @return returns g for convenience
 174 */
 175 public static Graph wireRegRootedTree( Graph g, int k ) {
 176
 177         if( k==0 ) return g;
 178         final int n = g.size();
 179         int i=0; // node we wire
 180         int j=1; // next free node to link to
 181         while(j<n)
 182         {
 183                 for(int l=0; l<k && j<n; ++l,++j) g.setEdge(i,j);
 184                 ++i;
 185         }
 186         return g;
 187 }
 188
 189 // -------------------------------------------------------------------
 190
 191 /**
 192 * A hypercube.
 193 * Wires a hypercube.
 194 * For a node i the following links are added: i xor 2^0, i xor 2^1, etc.
 195 * this define a log(graphsize) dimensional hypercube (if the log is an
 196 * integer).
 197 * @param g the graph to be wired
 198 * @return returns g for convenience
 199 */
 200 public static Graph wireHypercube( Graph g ) {
 201
 202         final int n = g.size();
 203         if(n<=1) return g;
 204         final int highestone = Integer.highestOneBit(n-1); // not zero
 205         for(int i=0; i<n; ++i)
 206         {
 207                 int mask = highestone;
 208                 while(mask>0)
 209                 {
 210                         int j = i^mask;
 211                         if(j<n) g.setEdge(i,j);
 212                         mask = mask >> 1;
 213                 }
 214
 215         }
 216         return g;
 217 }
 218
 219 // -------------------------------------------------------------------
 220
 221 /**
 222 * This contains the implementation of the Barabasi-Albert model
 223 * of growing scale free networks. The original model is described in
 224 * <a href="http://arxiv.org/abs/cond-mat/0106096">
 225 http://arxiv.org/abs/cond-mat/0106096</a>.
 226 * It also works if the graph is directed, in which case the model is a
 227 * variation of the BA model
 228 * described in <a href="http://arxiv.org/pdf/cond-mat/0408391">
 229 http://arxiv.org/pdf/cond-mat/0408391</a>. In both cases, the number of the
 230 * initial set of nodes is the same as the degree parameter, and no links are
 231 * added. The first added node is connected to all of the initial nodes,
 232 * and after that the BA model is used normally.
 233 * @param k the number of edges that are generated for each new node, also
 234 * the number of initial nodes (that have no edges).
 235 * @param r the randomness to be used
 236 * @return returns g for convenience
 237 */
 238 public static Graph wireScaleFreeBA( Graph g, int k, Random r ) {
 239
 240         final int nodes = g.size();
 241         if( nodes <= k ) return g;
 242
 243         // edge i has ends (ends[2*i],ends[2*i+1])
 244         int[] ends = new int[2*k*(nodes-k)];
 245
 246         // Add initial edges from k to 0,1,...,k-1
 247         for(int i=0; i < k; i++)
 248         {
 249                 g.setEdge(k,i);
 250                 ends[2*i]=k;
 251                 ends[2*i+1]=i;
 252         }
 253
 254         int len = 2*k; // edges drawn so far is len/2
 255         for(int i=k+1; i < nodes; i++) // over the remaining nodes
 256         {
 257                 for (int j=0; j < k; j++) // over the new edges
 258                 {
 259                         int target;
 260                         do
 261                         {
 262                                 target = ends[r.nextInt(len)];
 263                                 int m=0;
 264                                 while( m<j && ends[len+2*m+1]!=target) ++m;
 265                                 if(m==j) break;
 266                                 // we don't check in the graph because
 267                                 // this wire method should accept graphs
 268                                 // that already have edges.
 269                         }
 270                         while(true);
 271                         g.setEdge(i,target);
 272                         ends[len+2*j]=i;
 273                         ends[len+2*j+1]=target;
 274                 }
 275                 len += 2*k;
 276         }
 277
 278         return g;
 279 }
 280
 281 // -------------------------------------------------------------------
 282 /*
 283 public static void main(String[] pars) {
 284
 285         int n = Integer.parseInt(pars[0]);
 286         //int k = Integer.parseInt(pars[1]);
 287         Graph g = new BitMatrixGraph(n);
 288
 289         //wireWS(g,20,.1,new Random());
 290         //GraphIO.writeChaco(new UndirectedGraph(g),System.out);
 291
 292         //wireScaleFreeBA(g,3,new Random());
 293         //wireKOut(g,k,new Random());
 294         //wireRegRootedTree(g,k);
 295         wireHypercube(g);
 296         GraphIO.writeNeighborList(g,System.out);
 297 }
 298 */
 299 }
 300