contrib/psg/src/peersim/graph/PrefixSubGraph.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 * This class is an adaptor for representing special subgraphs of any graph.
  25 * It can represent the subgraphs spanned by the nodes 0,...,i where
  26 * i is less than or equal to n-1, the last node of the original graph.
  27 * The underlying graph is stored by reference. This means that if the
  28 * graph changes, then these changes will be reflected by this class as well.
  29 * Besides, the size of the prefix can be changed at will at any time
  30 * using {@link #setSize}.
  31 */
  32 public class PrefixSubGraph implements Graph {
  33
  34
  35 // ====================== private fileds ========================
  36 // ==============================================================
  37
  38
  39 private final Graph g;
  40
  41 /** The graph represents the subgraph defined by nodes 0,...,prefSize */
  42 private int prefSize;
  43
  44
  45 // ====================== public constructors ===================
  46 // ==============================================================
  47
  48
  49 /**
  50 * Constructs an initially max size subgraph of g. That is, the subgraph will
  51 * contain all nodes.
  52 */
  53 public PrefixSubGraph( Graph g ) {
  54
  55         this.g = g;
  56         prefSize = g.size();
  57 }
  58
  59
  60 // ======================= Graph implementations ================
  61 // ==============================================================
  62
  63
  64 public boolean isEdge(int i, int j) {
  65
  66         if( i<0 || i>=prefSize ) throw new IndexOutOfBoundsException();
  67         if( j<0 || j>=prefSize ) throw new IndexOutOfBoundsException();
  68         return g.isEdge(i,j);
  69 }
  70
  71 // ---------------------------------------------------------------
  72
  73 public Collection<Integer> getNeighbours(int i) {
  74
  75         if( i<0 || i>=prefSize ) throw new IndexOutOfBoundsException();
  76
  77         List<Integer> result = new LinkedList<Integer>();
  78         for(Integer j:g.getNeighbours(i))
  79         {
  80                 if( j < prefSize ) result.add(j);
  81         }
  82
  83         return Collections.unmodifiableCollection(result);
  84 }
  85
  86 // ---------------------------------------------------------------
  87
  88 public Object getNode(int i) {
  89
  90         if( i<0 || i>=prefSize ) throw new IndexOutOfBoundsException();
  91         return g.getNode(i);
  92 }
  93
  94 // ---------------------------------------------------------------
  95
  96 /**
  97 * Returns the edge in the original graph if both i and j are smaller than
  98 * size().
  99 */
 100 public Object getEdge(int i, int j) {
 101
 102         if( isEdge(i,j) ) return g.getEdge(i,j);
 103         return null;
 104 }
 105
 106 // --------------------------------------------------------------------
 107
 108 public int size() { return prefSize; }
 109
 110 // --------------------------------------------------------------------
 111
 112 public boolean directed() { return g.directed(); }
 113
 114 // --------------------------------------------------------------------
 115
 116 /** not supported */
 117 public boolean setEdge( int i, int j ) {
 118
 119         throw new UnsupportedOperationException();
 120 }
 121
 122 // ---------------------------------------------------------------
 123
 124 /** not supported */
 125 public boolean clearEdge( int i, int j ) {
 126
 127         throw new UnsupportedOperationException();
 128 }
 129
 130 // ---------------------------------------------------------------
 131
 132 public int degree(int i) {
 133
 134         if( i<0 || i>=prefSize ) throw new IndexOutOfBoundsException();
 135         return g.degree(i);
 136 }
 137
 138
 139 // ================= public functions =================================
 140 // ====================================================================
 141
 142
 143 /**
 144 * Sets the size of the subgraph. If i is negative, it is changed to 0 and
 145 * if it is larger than the underlying graph size, it is changed to the
 146 * underlying graph size (set at construction time).
 147 * @return old size.
 148 */
 149 public int setSize(int i) {
 150
 151         int was = prefSize;
 152         if( i < 0 ) i = 0;
 153         if( i > g.size() ) i=g.size();
 154         prefSize=i;
 155         return was;
 156 }
 157 }
 158