contrib/psg/src/peersim/graph/GraphAlgorithms.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 * Implements graph algorithms. The current implementation is NOT thread
  25 * safe. Some algorithms are not static, many times the result of an
  26 * algorithm can be read from non-static fields.
  27 */
  28 public class GraphAlgorithms {
  29
  30 // =================== public fields ==================================
  31 // ====================================================================
  32
  33 /** output of some algorithms is passed here */
  34 public int[] root = null;
  35 private Stack<Integer> stack = new Stack<Integer>();
  36 private int counter=0;
  37
  38 private Graph g=null;
  39
  40 public final static int WHITE=0;
  41 public final static int GREY=1;
  42 public final static int BLACK=2;
  43
  44 /** output of some algorithms is passed here */
  45 public int[] color = null;
  46
  47 /** output of some algorithms is passed here */
  48 public Set<Integer> cluster = null;
  49
  50 /** output of some algorithms is passed here */
  51 public int[] d = null;
  52
  53 // =================== private methods ================================
  54 // ====================================================================
  55
  56
  57 /**
  58 * Collects nodes accessible from node "from" using depth-first search.
  59 * Works on the array {@link #color} which must be of the same length as
  60 * the size of the graph, and must contain values according to the
  61 * following semantics:
  62 * WHITE (0): not seen yet, GREY (1): currently worked upon. BLACK
  63 * (other than 0 or 1): finished.
  64 * If a negative color is met, it is saved in the {@link #cluster} set
  65 * and is treated as black. This can be used to check if the currently
  66 * visited cluster is weakly connected to another cluster.
  67 * On exit no nodes are GREY.
  68 * The result is the modified array {@link #color} and the modified set
  69 * {@link #cluster}.
  70 */
  71 private void dfs( int from ) {
  72
  73         color[from]=GREY;
  74
  75         for(int j:g.getNeighbours(from))
  76         {
  77                 if( color[j]==WHITE )
  78                 {
  79                         dfs(j);
  80                 }
  81                 else
  82                 {
  83                         if( color[j]<0 ) cluster.add(color[j]);
  84                 }
  85         }
  86
  87         color[from]=BLACK;
  88 }
  89
  90 // --------------------------------------------------------------------
  91
  92 /**
  93 * Collects nodes accessible from node "from" using breadth-first search.
  94 * Its parameters and side-effects are identical to those of dfs.
  95 * In addition, it stores the shortest distances from "from" in {@link #d},
  96 * if it is not null. On return, <code>d[i]</code> contains the length of
  97 * the shortest path from "from" to "i", if such a path exists, or it is
  98 * unchanged (ie the original value of <code>d[i]</code> is kept,
  99 * whatever that was.
 100 * <code>d</code> must either be long enough or null.
 101 */
 102 private void bfs( int from ) {
 103
 104         List<Integer> q = new LinkedList<Integer>();
 105         int u, du;
 106
 107         q.add(from);
 108         q.add(0);
 109         if( d != null ) d[from] = 0;
 110
 111         color[from]=GREY;
 112
 113         while( ! q.isEmpty() )
 114         {
 115                 u = q.remove(0).intValue();
 116                 du = q.remove(0).intValue();
 117
 118                 for(int j:g.getNeighbours(u))
 119                 {
 120                         if( color[j]==WHITE )
 121                         {
 122                                 color[j]=GREY;
 123
 124                                 q.add(j);
 125                                 q.add(du+1);
 126                                 if( d != null ) d[j] = du+1;
 127                         }
 128                         else
 129                         {
 130                                 if( color[j]<0 )
 131                                         cluster.add(color[j]);
 132                         }
 133                 }
 134                 color[u]=BLACK;
 135         }
 136 }
 137
 138 // --------------------------------------------------------------------
 139
 140 /** The recursive part of the Tarjan algorithm. */
 141 private void tarjanVisit(int i) {
 142
 143         color[i]=counter++;
 144         root[i]=i;
 145         stack.push(i);
 146
 147         for(int j:g.getNeighbours(i))
 148         {
 149                 if( color[j]==WHITE )
 150                 {
 151                         tarjanVisit(j);
 152                 }
 153                 if( color[j]>0 && color[root[j]]<color[root[i]] )
 154                 // inComponent is false and have to update root
 155                 {
 156                         root[i]=root[j];
 157                 }
 158         }
 159
 160         int j;
 161         if(root[i]==i) //this node is the root of its cluster
 162         {
 163                 do
 164                 {
 165                         j=stack.pop();
 166                         color[j]=-color[j];
 167                         root[j]=i;
 168                 }
 169                 while(j!=i);
 170         }
 171 }
 172
 173 // =================== public methods ================================
 174 // ====================================================================
 175
 176 /** Returns the weakly connected cluster indexes with size as a value.
 177 * Cluster membership can be seen from the content of the array {@link #color};
 178 * each node has the cluster index as color. The cluster indexes carry no
 179 * information; we guarantee only that different clusters have different indexes.
 180 */
 181 public Map weaklyConnectedClusters( Graph g ) {
 182
 183         this.g=g;
 184         if( cluster == null ) cluster = new HashSet<Integer>();
 185         if( color==null || color.length<g.size() ) color = new int[g.size()];
 186
 187         // cluster numbers are negative integers
 188         int i, j, actCluster=0;
 189         for(i=0; i<g.size(); ++i) color[i]=WHITE;
 190         for(i=0; i<g.size(); ++i)
 191         {
 192                 if( color[i]==WHITE )
 193                 {
 194                         cluster.clear();
 195                         bfs(i); // dfs is recursive, for large graphs not ok
 196                         --actCluster;
 197                         for(j=0; j<g.size(); ++j)
 198                         {
 199                                 if( color[j] == BLACK ||
 200                                                 cluster.contains(color[j]) )
 201                                         color[j] = actCluster;
 202                         }
 203                 }
 204         }
 205
 206         Hashtable<Integer,Integer> ht = new Hashtable<Integer,Integer>();
 207         for(j=0; j<g.size(); ++j)
 208         {
 209                 Integer num = ht.get(color[j]);
 210                 if( num == null ) ht.put(color[j],Integer.valueOf(1));
 211                 else ht.put(color[j],num+1);
 212         }
 213
 214         return ht;
 215 }
 216
 217 // --------------------------------------------------------------------
 218
 219 /**
 220 * In <code>{@link #d}[j]</code> returns the length of the shortest path between
 221 * i and j. The value -1 indicates that j is not accessible from i.
 222 */
 223 public void dist( Graph g, int i ) {
 224
 225         this.g=g;
 226         if( d==null || d.length<g.size() ) d = new int[g.size()];
 227         if( color==null || color.length<g.size() ) color = new int[g.size()];
 228
 229         for(int j=0; j<g.size(); ++j)
 230         {
 231                 color[j]=WHITE;
 232                 d[j] = -1;
 233         }
 234
 235         bfs(i);
 236 }
 237
 238 // --------------------------------------------------------------------
 239
 240 /**
 241 * Calculates the clustering coefficient for the given node in the given
 242 * graph. The clustering coefficient is the number of edges between
 243 * the neighbours of i divided by the number of possible edges.
 244 * If the graph is directed, an exception is thrown.
 245 * If the number of neighbours is 1, returns 1. For zero neighbours
 246 * returns NAN.
 247 * @throws IllegalArgumentException if g is directed
 248 */
 249 public static double clustering( Graph g, int i ) {
 250
 251         if( g.directed() ) throw new IllegalArgumentException(
 252                 "graph is directed");
 253
 254         Object[] n = g.getNeighbours(i).toArray();
 255
 256         if( n.length==1 ) return 1.0;
 257
 258         int edges = 0;
 259
 260         for(int j=0; j<n.length; ++j)
 261         for(int k=j+1; k<n.length; ++k)
 262                 if( g.isEdge((Integer)n[j],(Integer)n[k]) ) ++edges;
 263
 264         return ((edges*2.0)/n.length)/(n.length-1);
 265 }
 266
 267 // --------------------------------------------------------------------
 268
 269 /**
 270 * Performs anti-entropy epidemic multicasting from node 0.
 271 * As a result the number of nodes that have been reached in cycle i
 272 * is put into <code>b[i]</code>.
 273 * The number of cycles performed is determined by <code>b.length</code>.
 274 * In each cycle each node contacts a random neighbour and exchanges
 275 * information. The simulation is generational: when a node contacts a neighbor
 276 * in cycle i, it sees their state as in cycle i-1, besides, all nodes update
 277 * their state at the same time point, synchronously.
 278 */
 279 public static void multicast( Graph g, int[] b, Random r ) {
 280
 281         int c1[] = new int[g.size()];
 282         int c2[] = new int[g.size()];
 283         for(int i=0; i<c1.length; ++i) c2[i]=c1[i]=WHITE;
 284         c2[0]=c1[0]=BLACK;
 285         Collection<Integer> neighbours=null;
 286         int black=1;
 287
 288         int k=0;
 289         for(; k<b.length || black<g.size(); ++k)
 290         {
 291                 for(int i=0; i<c2.length; ++i)
 292                 {
 293                         neighbours=g.getNeighbours(i);
 294                         Iterator<Integer> it=neighbours.iterator();
 295                         for(int j=r.nextInt(neighbours.size()); j>0; --j)
 296                                 it.next();
 297                         int randn = it.next();
 298
 299                         // push pull exchane with random neighbour
 300                         if( c1[i]==BLACK ) //c2[i] is black too
 301                         {
 302                                 if(c2[randn]==WHITE) ++black;
 303                                 c2[randn]=BLACK;
 304                         }
 305                         else if( c1[randn]==BLACK )
 306                         {
 307                                 if(c2[i]==WHITE) ++black;
 308                                 c2[i]=BLACK;
 309                         }
 310                 }
 311                 System.arraycopy(c2,0,c1,0,c1.length);
 312                 b[k]=black;
 313         }
 314
 315         for(; k<b.length; ++k) b[k]=g.size();
 316 }
 317
 318 // --------------------------------------------------------------------
 319
 320 /**
 321 * Performs flooding from given node.
 322 * As a result <code>b[i]</code> contains the number of nodes
 323 * reached in exactly i steps, and always <code>b[0]=1</code>.
 324 * If the maximal distance from k is lower than <code>b.length</code>,
 325 * then the remaining elements of b are zero.
 326 */
 327 public void flooding( Graph g, int[] b, int k ) {
 328
 329         dist(g, k);
 330
 331         for(int i=0; i<b.length; ++i) b[i]=0;
 332         for(int i=0; i<d.length; ++i)
 333         {
 334                 if( d[i] >= 0 && d[i] < b.length ) b[d[i]]++;
 335         }
 336 }
 337
 338 // --------------------------------------------------------------------
 339
 340 /** Returns the strongly connected cluster roots with size as a value.
 341 * Cluster membership can be seen from the content of the array {@link #root};
 342 * each node has the root of the strongly connected cluster it belongs to.
 343 * A word of caution: for large graphs that have a large diameter and that
 344 * are strongly connected (such as large rings) you can get stack overflow
 345 * because of the large depth of recursion.
 346 */
 347 //XXX implement a non-recursive version ASAP!!!
 348 public Map tarjan( Graph g ) {
 349
 350         this.g=g;
 351         stack.clear();
 352         if( root==null || root.length<g.size() ) root = new int[g.size()];
 353         if( color==null || color.length<g.size() ) color = new int[g.size()];
 354         for( int i=0; i<g.size(); ++i) color[i]=WHITE;
 355         counter = 1;
 356
 357         // color is WHITE (0): not visited
 358         // not WHITE, positive (c>1): visited as the c-th node
 359         // color is negative (c<1): inComponent true
 360         for(int i=0; i<g.size(); ++i)
 361         {
 362                 if( color[i]==WHITE ) tarjanVisit(i);
 363         }
 364         for( int i=0; i<g.size(); ++i) color[i]=0;
 365         for( int i=0; i<g.size(); ++i) color[root[i]]++;
 366         Hashtable<Integer,Integer> ht = new Hashtable<Integer,Integer>();
 367         for(int j=0; j<g.size(); ++j)
 368         {
 369                 if(color[j]>0)
 370                 {
 371                         ht.put(j,color[j]);
 372                 }
 373         }
 374
 375         return ht;
 376 }
 377
 378 }
 379