contrib/psg/src/peersim/graph/UndirectedGraph.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 so
  27 * if the directed graph changes later, the undirected version will
  28 * follow that change. However, {@link #getNeighbours} has O(n) time complexity
  29 * (in other words, too slow for large graphs).
  30 * @see ConstUndirGraph
  31 */
  32 public class UndirectedGraph implements Graph {
  33
  34
  35 // ====================== private fileds ========================
  36 // ==============================================================
  37
  38
  39 private final Graph g;
  40
  41
  42 // ====================== public constructors ===================
  43 // ==============================================================
  44
  45
  46 public UndirectedGraph( Graph g ) {
  47
  48         this.g = g;
  49 }
  50
  51
  52 // ======================= Graph implementations ================
  53 // ==============================================================
  54
  55
  56 public boolean isEdge(int i, int j) {
  57
  58         return g.isEdge(i,j) || g.isEdge(j,i);
  59 }
  60
  61 // ---------------------------------------------------------------
  62
  63 /**
  64 * Uses sets as collection so does not support multiple edges now, even if
  65 * the underlying directed graph does.
  66 */
  67 public Collection<Integer> getNeighbours(int i) {
  68
  69         Set<Integer> result = new HashSet<Integer>();
  70         result.addAll(g.getNeighbours(i));
  71         final int max = g.size();
  72         for(int j=0; j<max; ++j)
  73         {
  74                 if( g.isEdge(j,i) ) result.add(j);
  75         }
  76
  77         return Collections.unmodifiableCollection(result);
  78 }
  79
  80 // ---------------------------------------------------------------
  81
  82 public Object getNode(int i) { return g.getNode(i); }
  83
  84 // ---------------------------------------------------------------
  85
  86 /**
  87 * If there is an (i,j) edge, returns that, otherwise if there is a (j,i)
  88 * edge, returns that, otherwise returns null.
  89 */
  90 public Object getEdge(int i, int j) {
  91
  92         if( g.isEdge(i,j) ) return g.getEdge(i,j);
  93         if( g.isEdge(j,i) ) return g.getEdge(j,i);
  94         return null;
  95 }
  96
  97 // ---------------------------------------------------------------
  98
  99 public int size() { return g.size(); }
 100
 101 // --------------------------------------------------------------------
 102
 103 public boolean directed() { return false; }
 104
 105 // --------------------------------------------------------------------
 106
 107 /** not supported */
 108 public boolean setEdge( int i, int j ) {
 109
 110         throw new UnsupportedOperationException();
 111 }
 112
 113 // ---------------------------------------------------------------
 114
 115 /** not supported */
 116 public boolean clearEdge( int i, int j ) {
 117
 118         throw new UnsupportedOperationException();
 119 }
 120
 121 // --------------------------------------------------------------------
 122
 123 public int degree(int i) {
 124
 125         return getNeighbours(i).size();
 126 }
 127
 128 // --------------------------------------------------------------------
 129 /*
 130 public static void main( String[] args ) {
 131
 132
 133         Graph net = null;
 134         UndirectedGraph ug = new UndirectedGraph(net);
 135         for(int i=0; i<net.size(); ++i)
 136                 System.err.println(i+" "+net.getNeighbours(i));
 137         System.err.println("============");
 138         for(int i=0; i<ug.size(); ++i)
 139                 System.err.println(i+" "+ug.getNeighbours(i));
 140         for(int i=0; i<ug.size(); ++i)
 141         {
 142                 for(int j=0; j<ug.size(); ++j)
 143                         System.err.print(ug.isEdge(i,j)?"W ":"- ");
 144                 System.err.println();
 145         }
 146
 147         GraphIO.writeGML(net,System.out);
 148 }
 149 */
 150 }
 151
 152