contrib/psg/src/peersim/graph/ConstUndirGraph.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 making any Graph an undirected graph
  25 * by making its edges bidirectional. The graph to be made undirected
  26 * is passed to the constructor. Only the reference is stored.
  27 * However, at construction time the incoming edges are stored
  28 * for each node, so if the graph
  29 * passed to the constructor changes over time then
  30 * methods {@link #getNeighbours(int)} and {@link #degree(int)}
  31 * become inconsistent (but only those).
  32 * The upside of this inconvenience is that {@link #getNeighbours} will have
  33 * constant time complexity.
  34 * @see UndirectedGraph
  35 */
  36 public class ConstUndirGraph implements Graph {
  37
  38
  39 // ====================== private fileds ========================
  40 // ==============================================================
  41
  42
  43 protected final Graph g;
  44
  45 protected final List<Integer>[] in;
  46
  47 // ====================== public constructors ===================
  48 // ==============================================================
  49
  50 /**
  51 * Initialization based on given graph. Stores the graph and if necessary
  52 * (if the graph is directed) searches for the incoming edges and stores
  53 * them too. The given graph is stored by reference (not cloned) so it should
  54 * not be modified while this object is in use.
  55 */
  56 public ConstUndirGraph( Graph g ) {
  57
  58         this.g = g;
  59         if( !g.directed() )
  60         {
  61                 in = null;
  62         }
  63         else
  64         {
  65                 in = new List[g.size()];
  66         }
  67
  68         initGraph();
  69 }
  70
  71 // --------------------------------------------------------------
  72
  73 /** Finds and stores incoming edges */
  74 protected void initGraph() {
  75
  76         final int max = g.size();
  77         for(int i=0; i<max; ++i) in[i] = new ArrayList<Integer>();
  78         for(int i=0; i<max; ++i)
  79         {
  80                 for(Integer j:g.getNeighbours(i))
  81                 {
  82                         if( ! g.isEdge(j,i) ) in[j].add(i);
  83                 }
  84         }
  85 }
  86
  87
  88 // ======================= Graph implementations ================
  89 // ==============================================================
  90
  91
  92 public boolean isEdge(int i, int j) {
  93
  94         return g.isEdge(i,j) || g.isEdge(j,i);
  95 }
  96
  97 // ---------------------------------------------------------------
  98
  99 /**
 100 * Uses sets as collection so does not support multiple edges now, even if
 101 * the underlying directed graph does.
 102 */
 103 public Collection<Integer> getNeighbours(int i) {
 104
 105         List<Integer> result = new ArrayList<Integer>();
 106         result.addAll(g.getNeighbours(i));
 107         if( in != null ) result.addAll(in[i]);
 108         return Collections.unmodifiableCollection(result);
 109 }
 110
 111 // ---------------------------------------------------------------
 112
 113 /** Returns the node from the underlying graph */
 114 public Object getNode(int i) { return g.getNode(i); }
 115
 116 // ---------------------------------------------------------------
 117
 118 /**
 119 * If there is an (i,j) edge, returns that, otherwise if there is a (j,i)
 120 * edge, returns that, otherwise returns null.
 121 */
 122 public Object getEdge(int i, int j) {
 123
 124         if( g.isEdge(i,j) ) return g.getEdge(i,j);
 125         if( g.isEdge(j,i) ) return g.getEdge(j,i);
 126         return null;
 127 }
 128
 129 // ---------------------------------------------------------------
 130
 131 public int size() { return g.size(); }
 132
 133 // --------------------------------------------------------------------
 134
 135 public boolean directed() { return false; }
 136
 137 // --------------------------------------------------------------------
 138
 139 /** not supported */
 140 public boolean setEdge( int i, int j ) {
 141
 142         throw new UnsupportedOperationException();
 143 }
 144
 145 // ---------------------------------------------------------------
 146
 147 /** not supported */
 148 public boolean clearEdge( int i, int j ) {
 149
 150         throw new UnsupportedOperationException();
 151 }
 152
 153 // ---------------------------------------------------------------
 154
 155 public int degree(int i) { return g.degree(i)+(in==null?0:in[i].size()); }
 156
 157 // ---------------------------------------------------------------
 158 /*
 159 public static void main( String[] args ) {
 160
 161         Graph net = new BitMatrixGraph(20);
 162         GraphFactory.wireKOut(net,5,new Random());
 163         ConstUndirGraph ug = new ConstUndirGraph(net);
 164         for(int i=0; i<net.size(); ++i)
 165                 System.err.println(
 166                         i+" "+net.getNeighbours(i)+" "+net.degree(i));
 167         System.err.println("============");
 168         for(int i=0; i<ug.size(); ++i)
 169                 System.err.println(i+" "+ug.getNeighbours(i)+" "+ug.degree(i));
 170         System.err.println("============");
 171         for(int i=0; i<ug.size(); ++i)
 172                 System.err.println(i+" "+ug.in[i]);
 173         for(int i=0; i<ug.size(); ++i)
 174         {
 175                 for(int j=0; j<ug.size(); ++j)
 176                         System.err.print(ug.isEdge(i,j)?"W ":"+ ");
 177                 System.err.println();
 178         }
 179
 180         GraphIO.writeUCINET_DL(net,System.out);
 181         GraphIO.writeUCINET_DL(ug,System.out);
 182 }
 183 */
 184 }
 185