contrib/psg/src/peersim/reports/BallExpansion.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.config.*;
  22 import peersim.core.*;
  23 import peersim.util.*;
  24
  25 /**
  26  * Control to observe the ball expansion, that is,
  27  * the number of nodes that are
  28  * accessible from a given node in at most 1, 2, etc steps.
  29  */
  30 public class BallExpansion extends GraphObserver
  31 {
  32
  33 // ===================== fields =======================================
  34 // ====================================================================
  35
  36 /**
  37  * This parameter defines the maximal distance we care about.
  38  * In other words, two nodes are further away, they will not be taken
  39  * into account when calculating statistics.
  40  * <p>
  41  * Defaults to the
  42  * network size (which means all distances are taken into account).
  43  * Note that this default is normally way too much; many low diameter graphs
  44  * have only short distances between the nodes. Setting a short
  45  * (but sufficient) distance saves memory.
  46  * Also note that the <em>initial</em> network
  47  * size is used if no value is given which might not be what you want if e.g. the
  48  * network is growing.
  49  * @config
  50  */
  51 private static final String PAR_MAXD = "maxd";
  52
  53 /**
  54  * The number of nodes to print info about.
  55  * Defaults to 1000. If larger than the current network size, then the
  56  * current network size is used.
  57  * @config
  58  */
  59 private static final String PAR_N = "n";
  60
  61 /**
  62  * If defined, statistics are printed instead over the minimal path lengths. Not
  63  * defined by default.
  64  * @config
  65  */
  66 private static final String PAR_STATS = "stats";
  67
  68 private final int maxd;
  69
  70 private final int n;
  71
  72 private final boolean stats;
  73
  74 /** working variable */
  75 private final int[] b;
  76
  77 private final RandPermutation rp = new RandPermutation(CommonState.r);
  78
  79 // ===================== initialization ================================
  80 // =====================================================================
  81
  82 /**
  83  * Standard constructor that reads the configuration parameters.
  84  * Invoked by the simulation engine.
  85  * @param name the configuration prefix for this class
  86  */
  87 public BallExpansion(String name)
  88 {
  89         super(name);
  90         maxd = Configuration.getInt(name + "." + PAR_MAXD, Network.size());
  91         n = Configuration.getInt(name + "." + PAR_N, 1000);
  92         stats = Configuration.contains(name + "." + PAR_STATS);
  93         b = new int[maxd];
  94 }
  95
  96 // ====================== methods ======================================
  97 // =====================================================================
  98
  99 /**
 100 * Prints information about ball expansion. It uses {@value #PAR_N} nodes to
 101 * collect statistics.
 102 * If parameter {@value #PAR_STATS} is defined then the output is
 103 * produced by {@link IncrementalStats#toString}, over the values of minimal
 104 * distances from the given number of nodes to all other nodes in the network.
 105 * If at least one node is unreachable from any selected starting node, then
 106 * the path length is taken as infinity and statistics are calculated
 107 * accordingly. In that case, {@link IncrementalStats#getMaxCount()} returns
 108 * the number of nodes of "infinite distance", that is, the number of
 109 * unreachable nodes.
 110 * Otherwise one line is printed for all nodes we observe, containing the
 111 * number of nodes at distance 1, 2, etc, separated by spaces.
 112 * In this output format, unreachable nodes are simply ignored, but of course
 113 * the sum of the numbers in one line can be used to detect partitioning if
 114 * necessary.
 115 * Finally, note that the {@value #PAR_N} nodes are not guaranteed to be the
 116 * same nodes over consecutive calls to this method.
 117 * @return always false
 118 */
 119 public boolean execute() {
 120
 121         updateGraph();
 122         System.out.print(name + ": ");
 123         rp.reset(g.size());
 124         if (stats)
 125         {
 126                 IncrementalStats is = new IncrementalStats();
 127                 for (int i = 0; i < n && i < g.size(); ++i)
 128                 {
 129                         ga.dist(g, rp.next());
 130                         for (int j=0; j<g.size(); j++)
 131                         {
 132                                 if (ga.d[j] > 0)
 133                                         is.add(ga.d[j]);
 134                                 else if (ga.d[j] == -1)
 135                                         is.add(Double.POSITIVE_INFINITY);
 136                                 // deliberately left ga.d[j]==0 out, as we don't
 137                                 // want to count trivial distance to oneself.
 138                         }
 139                 }
 140                 System.out.println(is);
 141         }
 142         else
 143         {
 144                 System.out.println();
 145                 for (int i = 0; i < n && i < g.size(); ++i)
 146                 {
 147                         ga.flooding(g, b, rp.next());
 148                         int j = 0;
 149                         while (j < b.length && b[j] > 0)
 150                         {
 151                                 System.out.print(b[j++] + " ");
 152                         }
 153                         System.out.println();
 154                 }
 155         }
 156         return false;
 157 }
 158
 159 }