contrib/psg/src/peersim/core/OverlayGraph.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.core;
  20
  21 import peersim.graph.Graph;
  22 import java.util.Collection;
  23 import java.util.ArrayList;
  24 import java.util.Collections;
  25
  26 /**
  27 * This class is an adaptor which makes a {@link Linkable} protocol layer
  28 * look like a graph. It is useful because it allows the application of many
  29 * graph algorithms and graph topology initialization methods.
  30 * If the overlay network changes after creating this object, the changes
  31 * will be reflected. However, if the nodes are reshuffled (see
  32 * {@link Network#shuffle}), or if the node list changes (addition/removal),
  33 * then the behaviour becomes unspecified.
  34 *
  35 * The indices of nodes are from 0 to Network.size()-1.
  36 *
  37 * The fail state of nodes has an effect on the graph: all nodes are included
  38 * but edges are included only if both ends are up. This expresses the fact
  39 * that this graph is in fact defined by the "can communicate with" relation.
  40 */
  41 public class OverlayGraph implements Graph {
  42
  43
  44 // ====================== fields ================================
  45 // ==============================================================
  46
  47 /**
  48 * The protocol ID that selects the Linkable protocol to convert to a graph.
  49 */
  50 public final int protocolID;
  51
  52 /**
  53 * Tells if the graph should be wired in an undirected way.
  54 * Method {@link #directed} returns true always, this affects only
  55 * method {@link #setEdge}: if false, then the opposite edge is set too.
  56 */
  57 public final boolean wireDirected;
  58
  59 // ====================== public constructors ===================
  60 // ==============================================================
  61
  62 /**
  63 * @param protocolID The protocol on which this adaptor is supposed
  64 * to operate.
  65 */
  66 public OverlayGraph( int protocolID ) {
  67
  68         this.protocolID = protocolID;
  69         wireDirected = true;
  70 }
  71
  72 // --------------------------------------------------------------
  73
  74 /**
  75 * @param protocolID The protocol on which this adaptor is supposed
  76 * to operate.
  77 * @param wireDirected specifies if {@link #setEdge} would wire the
  78 * opposite edge too.
  79 */
  80 public OverlayGraph( int protocolID, boolean wireDirected ) {
  81
  82         this.protocolID = protocolID;
  83         this.wireDirected = wireDirected;
  84 }
  85
  86
  87 // ======================= Graph implementations ================
  88 // ==============================================================
  89
  90
  91 public boolean isEdge(int i, int j) {
  92
  93         return
  94                 ((Linkable)Network.node[i].getProtocol(protocolID)
  95                 ).contains(Network.node[j]) &&
  96                 Network.node[j].isUp() &&
  97                 Network.node[i].isUp();
  98 }
  99
 100 // ---------------------------------------------------------------
 101
 102 /**
 103 * Returns those neighbors that are up. If node i is not up, it returns
 104 * an empty list.
 105 */
 106 public Collection<Integer> getNeighbours(int i) {
 107
 108         Linkable lble=(Linkable)Network.node[i].getProtocol(protocolID);
 109         ArrayList<Integer> al = new ArrayList<Integer>(lble.degree());
 110         if( Network.node[i].isUp() )
 111         {
 112                 for(int j=0; j<lble.degree(); ++j)
 113                 {
 114                         final Node n = lble.getNeighbor(j);
 115                         // if accessible, we include it
 116                         if(n.isUp()) al.add(Integer.valueOf(n.getIndex()));
 117                 }
 118         }
 119         return Collections.unmodifiableList(al);
 120 }
 121
 122 // ---------------------------------------------------------------
 123
 124 /** Returns <code>Network.node[i]</code> */
 125 public Object getNode(int i) { return Network.node[i]; }
 126
 127 // ---------------------------------------------------------------
 128
 129 /**
 130 * Returns null always
 131 */
 132 public Object getEdge(int i, int j) { return null; }
 133
 134 // ---------------------------------------------------------------
 135
 136 /** Returns <code>Network.size()</code> */
 137 public int size() { return Network.size(); }
 138
 139 // --------------------------------------------------------------------
 140
 141 /** Returns always true */
 142 public boolean directed() { return true; }
 143
 144 // --------------------------------------------------------------------
 145
 146 /**
 147 * Sets given edge.
 148 * In some cases this behaves strangely. Namely, when node i or j is not up,
 149 * but is not dead (e.g. it can be down temporarily).
 150 * In such situations the relevant link is made, but afterwards
 151 * getEdge(i,j) will NOT return true, only when the fail state has changed back
 152 * to OK.
 153 *
 154 * <p>Conceptually one can think of it as a successful operation which is
 155 * immediately overruled by the dynamics of the underlying overlay network.
 156 * Let's not forget that this class is an adaptor only.
 157 *
 158 * <p>
 159 * The behaviour of this method is affected by parameter {@link #wireDirected}.
 160 * If it is false, then the opposite edge is set too.
 161 */
 162 public boolean setEdge( int i, int j ) {
 163 // XXX slightly unintuitive behavior but makes sense when understood
 164
 165         if( !wireDirected )
 166                 ((Linkable)Network.node[j].getProtocol(protocolID)
 167                 ).addNeighbor(Network.node[i]);
 168
 169
 170         return
 171                 ((Linkable)Network.node[i].getProtocol(protocolID)
 172                 ).addNeighbor(Network.node[j]);
 173 }
 174
 175 // ---------------------------------------------------------------
 176
 177 /** Not supported */
 178 public boolean clearEdge( int i, int j ) {
 179
 180         throw new UnsupportedOperationException();
 181 }
 182
 183 // ---------------------------------------------------------------
 184
 185 /**
 186 * Returns number of neighbors that are up. If node i is down, returns 0.
 187 */
 188 public int degree(int i) {
 189
 190         if( !Network.node[i].isUp() ) return 0;
 191         Linkable lble=(Linkable)Network.node[i].getProtocol(protocolID);
 192         int numNeighbours = 0;
 193         for(int j=0; j<lble.degree(); ++j)
 194         {
 195                 final Node n = lble.getNeighbor(j);
 196                 // if accessible, we count it
 197                 if(n.isUp()) numNeighbours++;
 198         }
 199         return numNeighbours;
 200 }
 201
 202
 203 // ========================= other methods =======================
 204 // ===============================================================
 205
 206
 207 /**
 208 * Returns number of neighbors that are either up or down.
 209 * If node i is down, returns 0.
 210 */
 211 public int fullDegree(int i) {
 212
 213         if( !Network.node[i].isUp() ) return 0;
 214         Linkable lble=(Linkable)Network.node[i].getProtocol(protocolID);
 215         return lble.degree();
 216 }
 217
 218
 219 }
 220
 221