2 * Copyright (c) 2003-2005 The BISON Project
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.
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.
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.
19 package peersim.graph;
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
36 public class ConstUndirGraph implements Graph {
39 // ====================== private fileds ========================
40 // ==============================================================
43 protected final Graph g;
45 protected final List<Integer>[] in;
47 // ====================== public constructors ===================
48 // ==============================================================
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.
56 public ConstUndirGraph( Graph g ) {
65 in = new List[g.size()];
71 // --------------------------------------------------------------
73 /** Finds and stores incoming edges */
74 protected void initGraph() {
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)
80 for(Integer j:g.getNeighbours(i))
82 if( ! g.isEdge(j,i) ) in[j].add(i);
88 // ======================= Graph implementations ================
89 // ==============================================================
92 public boolean isEdge(int i, int j) {
94 return g.isEdge(i,j) || g.isEdge(j,i);
97 // ---------------------------------------------------------------
100 * Uses sets as collection so does not support multiple edges now, even if
101 * the underlying directed graph does.
103 public Collection<Integer> getNeighbours(int i) {
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);
111 // ---------------------------------------------------------------
113 /** Returns the node from the underlying graph */
114 public Object getNode(int i) { return g.getNode(i); }
116 // ---------------------------------------------------------------
119 * If there is an (i,j) edge, returns that, otherwise if there is a (j,i)
120 * edge, returns that, otherwise returns null.
122 public Object getEdge(int i, int j) {
124 if( g.isEdge(i,j) ) return g.getEdge(i,j);
125 if( g.isEdge(j,i) ) return g.getEdge(j,i);
129 // ---------------------------------------------------------------
131 public int size() { return g.size(); }
133 // --------------------------------------------------------------------
135 public boolean directed() { return false; }
137 // --------------------------------------------------------------------
140 public boolean setEdge( int i, int j ) {
142 throw new UnsupportedOperationException();
145 // ---------------------------------------------------------------
148 public boolean clearEdge( int i, int j ) {
150 throw new UnsupportedOperationException();
153 // ---------------------------------------------------------------
155 public int degree(int i) { return g.degree(i)+(in==null?0:in[i].size()); }
157 // ---------------------------------------------------------------
159 public static void main( String[] args ) {
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)
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)
175 for(int j=0; j<ug.size(); ++j)
176 System.err.print(ug.isEdge(i,j)?"W ":"+ ");
177 System.err.println();
180 GraphIO.writeUCINET_DL(net,System.out);
181 GraphIO.writeUCINET_DL(ug,System.out);