2 * Copyright (c) 2003-2005 The BISON Project
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.
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.
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.
19 package peersim.reports;
21 import peersim.config.*;
22 import peersim.core.*;
23 import peersim.util.*;
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.
30 public class BallExpansion extends GraphObserver
33 // ===================== fields =======================================
34 // ====================================================================
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.
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
51 private static final String PAR_MAXD = "maxd";
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.
59 private static final String PAR_N = "n";
62 * If defined, statistics are printed instead over the minimal path lengths. Not
66 private static final String PAR_STATS = "stats";
68 private final int maxd;
72 private final boolean stats;
74 /** working variable */
75 private final int[] b;
77 private final RandPermutation rp = new RandPermutation(CommonState.r);
79 // ===================== initialization ================================
80 // =====================================================================
83 * Standard constructor that reads the configuration parameters.
84 * Invoked by the simulation engine.
85 * @param name the configuration prefix for this class
87 public BallExpansion(String 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);
96 // ====================== methods ======================================
97 // =====================================================================
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
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
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
119 public boolean execute() {
122 System.out.print(name + ": ");
126 IncrementalStats is = new IncrementalStats();
127 for (int i = 0; i < n && i < g.size(); ++i)
129 ga.dist(g, rp.next());
130 for (int j=0; j<g.size(); 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.
140 System.out.println(is);
144 System.out.println();
145 for (int i = 0; i < n && i < g.size(); ++i)
147 ga.flooding(g, b, rp.next());
149 while (j < b.length && b[j] > 0)
151 System.out.print(b[j++] + " ");
153 System.out.println();