contrib/psg/src/peersim/graph/NeighbourListGraph.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 a graph which uses the neighbour list representation.
  25 * No multiple edges are allowed. The implementation also supports the
  26 * growing of the graph. This is very useful when the number of nodes is
  27 * not known in advance or when we construct a graph reading a file.
  28 */
  29 public class NeighbourListGraph implements Graph, java.io.Serializable {
  30
  31 // =================== private fields ============================
  32 // ===============================================================
  33
  34 /** Contains the objects associated with the node indeces.*/
  35 private final ArrayList<Object> nodes;
  36
  37 /**
  38 * Contains the indices of the nodes. The vector "nodes" contains this
  39 * information implicitly but this way we can find indexes in log time at
  40 * the cost of memory (node that the edge lists typically use much more memory
  41 * than this anyway). Note that the nodes vector is still necessary to
  42 * provide constant access to nodes based on indexes.
  43 */
  44 private final HashMap<Object,Integer> nodeindex;
  45
  46 /** Contains sets of node indexes. If "nodes" is not null, indices are
  47 * defined by "nodes", otherwise they correspond to 0,1,... */
  48 private final ArrayList<Set<Integer>> neighbors;
  49
  50 /** Indicates if the graph is directed. */
  51 private final boolean directed;
  52
  53 // =================== public constructors ======================
  54 // ===============================================================
  55
  56 /**
  57 * Constructs an empty graph. That is, the graph has zero nodes, but any
  58 * number of nodes and edges can be added later.
  59 * @param directed if true the graph will be directed
  60 */
  61 public NeighbourListGraph( boolean directed ) {
  62
  63         nodes = new ArrayList<Object>(1000);
  64         neighbors = new ArrayList<Set<Integer>>(1000);
  65         nodeindex = new HashMap<Object,Integer>(1000);
  66         this.directed = directed;
  67 }
  68
  69 // ---------------------------------------------------------------
  70
  71 /**
  72 * Constructs a graph with a fixed size without edges. If the graph is
  73 * constructed this way, it is not possible to associate objects to nodes,
  74 * nor it is possible to grow the graph using {@link #addNode}.
  75 * @param directed if true the graph will be directed
  76 */
  77 public NeighbourListGraph( int size, boolean directed ) {
  78
  79         nodes = null;
  80         neighbors = new ArrayList<Set<Integer>>(size);
  81         for(int i=0; i<size; ++i) neighbors.add(new HashSet<Integer>());
  82         nodeindex = null;
  83         this.directed = directed;
  84 }
  85
  86 // =================== public methods =============================
  87 // ================================================================
  88
  89 /**
  90 * If the given object is not associated with a node yet, adds a new
  91 * node. Returns the index of the node. If the graph was constructed to have
  92 * a specific size, it is not possible to add nodes and therefore calling
  93 * this method will throw an exception.
  94 * @throws NullPointerException if the size was specified at construction time.
  95 */
  96 public int addNode( Object o ) {
  97
  98         Integer index = nodeindex.get(o);
  99         if( index == null )
 100         {
 101                 index = nodes.size();
 102                 nodes.add(o);
 103                 neighbors.add(new HashSet<Integer>());
 104                 nodeindex.put(o,index);
 105         }
 106
 107         return index;
 108 }
 109
 110
 111 // =================== graph implementations ======================
 112 // ================================================================
 113
 114
 115 public boolean setEdge( int i, int j ) {
 116
 117         boolean ret = neighbors.get(i).add(j);
 118         if( ret && !directed ) neighbors.get(j).add(i);
 119         return ret;
 120 }
 121
 122 // ---------------------------------------------------------------
 123
 124 public boolean clearEdge( int i, int j ) {
 125
 126         boolean ret = neighbors.get(i).remove(j);
 127         if( ret && !directed ) neighbors.get(j).remove(i);
 128         return ret;
 129 }
 130
 131 // ---------------------------------------------------------------
 132
 133 public boolean isEdge(int i, int j) {
 134
 135         return neighbors.get(i).contains(j);
 136 }
 137
 138 // ---------------------------------------------------------------
 139
 140 public Collection<Integer> getNeighbours(int i) {
 141
 142         return Collections.unmodifiableCollection(neighbors.get(i));
 143 }
 144
 145 // ---------------------------------------------------------------
 146
 147 /** If the graph was gradually grown using {@link #addNode}, returns the
 148 * object associated with the node, otherwise null */
 149 public Object getNode(int i) { return (nodes==null?null:nodes.get(i)); }
 150
 151 // ---------------------------------------------------------------
 152
 153 /**
 154 * Returns null always.
 155 */
 156 public Object getEdge(int i, int j) { return null; }
 157
 158 // ---------------------------------------------------------------
 159
 160 public int size() { return neighbors.size(); }
 161
 162 // --------------------------------------------------------------------
 163
 164 public boolean directed() { return directed; }
 165
 166 // --------------------------------------------------------------------
 167
 168 public int degree(int i) { return neighbors.get(i).size(); }
 169 }
 170
 171
 172
 173