contrib/psg/src/peersim/graph/SubGraphEdges.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 subgraphs of any graph.
  25 * The subgraph is defined the following way.
  26 * The subgraph always contains all the nodes of the original underlying
  27 * graph. However, it is possible to remove edges by flagging nodes as
  28 * removed, in which case
  29 * the edges that have at least one end on those nodes are removed.
  30 * If the underlying graph changes after initialization, this class follows
  31 * the change.
  32 */
  33 public class SubGraphEdges implements Graph {
  34
  35
  36 // ====================== private fields ========================
  37 // ==============================================================
  38
  39
  40 private final Graph g;
  41
  42 private final BitSet nodes;
  43
  44
  45 // ====================== public constructors ===================
  46 // ==============================================================
  47
  48
  49 /**
  50 * Constructs an initially empty subgraph of g. That is, the subgraph will
  51 * contain no nodes.
  52 */
  53 public SubGraphEdges( Graph g ) {
  54
  55         this.g = g;
  56         nodes = new BitSet(g.size());
  57 }
  58
  59
  60 // ======================= Graph implementations ================
  61 // ==============================================================
  62
  63
  64 public boolean isEdge(int i, int j) {
  65
  66         return nodes.get(i) && nodes.get(j) && g.isEdge(i,j);
  67 }
  68
  69 // ---------------------------------------------------------------
  70
  71 public Collection<Integer> getNeighbours(int i) {
  72
  73         List<Integer> result = new LinkedList<Integer>();
  74         if( nodes.get(i) )
  75         {
  76                 for(Integer in:g.getNeighbours(i))
  77                 {
  78                         if( nodes.get(in) ) result.add(in);
  79                 }
  80         }
  81
  82         return Collections.unmodifiableCollection(result);
  83 }
  84
  85 // ---------------------------------------------------------------
  86
  87 public Object getNode(int i) { return g.getNode(i); }
  88
  89 // ---------------------------------------------------------------
  90
  91 /**
  92 * If both i and j are within the node set of the subgraph and the original
  93 * graph has an (i,j) edge, returns that edge.
  94 */
  95 public Object getEdge(int i, int j) {
  96
  97         if( isEdge(i,j) ) return g.getEdge(i,j);
  98         return null;
  99 }
 100
 101 // --------------------------------------------------------------------
 102
 103 public int size() { return g.size(); }
 104
 105 // --------------------------------------------------------------------
 106
 107 public boolean directed() { return g.directed(); }
 108
 109 // --------------------------------------------------------------------
 110
 111 /** not supported */
 112 public boolean setEdge( int i, int j ) {
 113
 114         throw new UnsupportedOperationException();
 115 }
 116
 117 // ---------------------------------------------------------------
 118
 119 /** not supported */
 120 public boolean clearEdge( int i, int j ) {
 121
 122         throw new UnsupportedOperationException();
 123 }
 124
 125 // ---------------------------------------------------------------
 126
 127 public int degree(int i) {
 128
 129         int degree=0;
 130         if( nodes.get(i) )
 131         {
 132                 for(Integer in:g.getNeighbours(i))
 133                 {
 134                         if( nodes.get(in) ) degree++;
 135                 }
 136         }
 137         return degree;
 138 }
 139
 140
 141 // ================= public functions =================================
 142 // ====================================================================
 143
 144
 145 /**
 146 * This function returns the size of the subgraph, i.e. the number of nodes
 147 * in the subgraph.
 148 */
 149 public int subGraphSize() { return nodes.cardinality(); }
 150
 151 // --------------------------------------------------------------------
 152
 153 /**
 154 * Removes given node from subgraph.
 155 * @return true if the node was already in the subgraph otherwise false.
 156 */
 157 public boolean removeNode(int i) {
 158
 159         boolean was = nodes.get(i);
 160         nodes.clear(i);
 161         return was;
 162 }
 163
 164 // --------------------------------------------------------------------
 165
 166 /**
 167 * Adds given node to subgraph.
 168 * @return true if the node was already in the subgraph otherwise false.
 169 */
 170 public boolean addNode(int i) {
 171
 172         boolean was = nodes.get(i);
 173         nodes.set(i);
 174         return was;
 175 }
 176 }
 177