contrib/psg/src/peersim/graph/FastUndirGraph.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 /*
  20  * Created on Jan 30, 2005 by Spyros Voulgaris
  21  *
  22  */
  23 package peersim.graph;
  24
  25 import java.util.ArrayList;
  26 import java.util.BitSet;
  27
  28 /**
  29 * Speeds up {@link ConstUndirGraph#isEdge} by storing the links in an
  30 * adjacency matrix (in fact in a triangle).
  31 * Its memory consumption is huge but it's much faster if the isEdge method
  32 * of the original underlying graph is slow.
  33 */
  34 public class FastUndirGraph extends ConstUndirGraph
  35 {
  36
  37 private BitSet[] triangle;
  38
  39
  40 // ======================= initializarion ==========================
  41 // =================================================================
  42
  43
  44 /** Calls super constructor */
  45 public FastUndirGraph(Graph graph)
  46 {
  47         super(graph);
  48 }
  49
  50 // -----------------------------------------------------------------
  51
  52 protected void initGraph()
  53 {
  54         final int max = g.size();
  55         triangle = new BitSet[max];
  56         for (int i=0; i<max; ++i)
  57         {
  58                 in[i] = new ArrayList<Integer>();
  59                 triangle[i] = new BitSet(i);
  60         }
  61
  62         for(int i=0; i<max; ++i)
  63         {
  64                 for(Integer out:g.getNeighbours(i))
  65                 {
  66                         int j=out.intValue();
  67                         if( ! g.isEdge(j,i) )
  68                                 in[j].add(i);
  69                         // But always add the link to the triangle
  70                         if (i>j) // make sure i>j
  71                                 triangle[i].set(j);
  72                         else
  73                                 triangle[j].set(i);
  74                 }
  75         }
  76 }
  77
  78
  79 // ============================ Graph functions ====================
  80 // =================================================================
  81
  82
  83 public boolean isEdge(int i, int j)
  84 {
  85         // make sure i>j
  86         if (i<j)
  87         {
  88                 int ii=i;
  89                 i=j;
  90                 j=ii;
  91         }
  92         return triangle[i].get(j);
  93 }
  94 }
  95