contrib/psg/src/peersim/reports/RandRemoval.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.reports;
  20
  21 import peersim.core.*;
  22 import peersim.config.Configuration;
  23 import peersim.graph.*;
  24 import peersim.util.IncrementalStats;
  25 import java.util.Map;
  26 import java.util.Iterator;
  27
  28 /**
  29  * It tests the network for robustness to random node removal.
  30  * It does not actually remove
  31  * nodes, it is only an observer, so can be applied several times during the
  32  * simulation. A warning though: as a side effect it <em>may
  33  * shuffle the network</em> (see {@value #PAR_N}) so if this is an issue,
  34  * it should not be used,
  35  * or only after the simulation has finished.
  36  */
  37 public class RandRemoval extends GraphObserver
  38 {
  39
  40 // ===================== fields =======================================
  41 // ====================================================================
  42
  43 // XXX remove side effect
  44 /**
  45  * This parameter defines the number of runs of the iterative removal procedure
  46  * to get statistics. Look out: if set to a value larger than 1 then as a side
  47  * effect <em>the overlay will be shuffled</em>. Defaults to 1.
  48  * @config
  49  */
  50 private static final String PAR_N = "n";
  51
  52 private final int n;
  53
  54 // ===================== initialization ================================
  55 // =====================================================================
  56
  57 /**
  58  * Standard constructor that reads the configuration parameters.
  59  * Invoked by the simulation engine.
  60  * @param name the configuration prefix for this class
  61  */
  62 public RandRemoval(String name)
  63 {
  64         super(name);
  65         n = Configuration.getInt(name + "." + PAR_N, 1);
  66 }
  67
  68 // ====================== methods ======================================
  69 // =====================================================================
  70
  71 /**
  72 * Prints results of node removal tests. The following experiment is
  73 * repeated {@value #PAR_N} times. From the graph 50%, 51%, ..., 99% of the nodes
  74 * are removed at random. For all percentages it is calculated what is
  75 * the maximal
  76 * clustersize (weakly connected clusters) and the number of
  77 * clusters in the remaining graph.
  78 * These values are averaged over the experiments, and for all 50 different
  79 * percentage values a line is printed that contains the respective averages,
  80 * first the average maximal cluster size, followed by the average number
  81 * of clusters.
  82 * @return always false
  83 */
  84 public boolean execute()
  85 {
  86         if( n < 1 ) return false;
  87         updateGraph();
  88
  89         System.out.println(name + ":");
  90
  91         final int size = Network.size();
  92         final int steps = 50;
  93         IncrementalStats[] maxClust = new IncrementalStats[steps];
  94         IncrementalStats[] clustNum = new IncrementalStats[steps];
  95         for (int i = 0; i < steps; ++i) {
  96                 maxClust[i] = new IncrementalStats();
  97                 clustNum[i] = new IncrementalStats();
  98         }
  99         for (int j = 0; j < n; ++j) {
 100                 PrefixSubGraph sg = new PrefixSubGraph(g);
 101                 IncrementalStats stats = new IncrementalStats();
 102                 for (int i = 0; i < steps; i++) {
 103                         sg.setSize(size / 2 - i * (size / 100));
 104                         Map clst = ga.weaklyConnectedClusters(sg);
 105                         stats.reset();
 106                         Iterator it = clst.values().iterator();
 107                         while (it.hasNext()) {
 108                                 stats.add(((Integer) it.next()).intValue());
 109                         }
 110                         maxClust[i].add(stats.getMax());
 111                         clustNum[i].add(clst.size());
 112                 }
 113                 if( j+1 < n ) Network.shuffle();
 114         }
 115         for (int i = 0; i < steps; ++i) {
 116                 System.out.println(maxClust[i].getAverage() + " "
 117                                 + clustNum[i].getAverage());
 118         }
 119         return false;
 120 }
 121
 122 }