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.
21 import peersim.graph.Graph;
22 import java.util.Collection;
23 import java.util.ArrayList;
24 import java.util.Collections;
27 * This class is an adaptor which makes a {@link Linkable} protocol layer
28 * look like a graph. It is useful because it allows the application of many
29 * graph algorithms and graph topology initialization methods.
30 * If the overlay network changes after creating this object, the changes
31 * will be reflected. However, if the nodes are reshuffled (see
32 * {@link Network#shuffle}), or if the node list changes (addition/removal),
33 * then the behaviour becomes unspecified.
35 * The indices of nodes are from 0 to Network.size()-1.
37 * The fail state of nodes has an effect on the graph: all nodes are included
38 * but edges are included only if both ends are up. This expresses the fact
39 * that this graph is in fact defined by the "can communicate with" relation.
41 public class OverlayGraph implements Graph {
44 // ====================== fields ================================
45 // ==============================================================
48 * The protocol ID that selects the Linkable protocol to convert to a graph.
50 public final int protocolID;
53 * Tells if the graph should be wired in an undirected way.
54 * Method {@link #directed} returns true always, this affects only
55 * method {@link #setEdge}: if false, then the opposite edge is set too.
57 public final boolean wireDirected;
59 // ====================== public constructors ===================
60 // ==============================================================
63 * @param protocolID The protocol on which this adaptor is supposed
66 public OverlayGraph( int protocolID ) {
68 this.protocolID = protocolID;
72 // --------------------------------------------------------------
75 * @param protocolID The protocol on which this adaptor is supposed
77 * @param wireDirected specifies if {@link #setEdge} would wire the
80 public OverlayGraph( int protocolID, boolean wireDirected ) {
82 this.protocolID = protocolID;
83 this.wireDirected = wireDirected;
87 // ======================= Graph implementations ================
88 // ==============================================================
91 public boolean isEdge(int i, int j) {
94 ((Linkable)Network.node[i].getProtocol(protocolID)
95 ).contains(Network.node[j]) &&
96 Network.node[j].isUp() &&
97 Network.node[i].isUp();
100 // ---------------------------------------------------------------
103 * Returns those neighbors that are up. If node i is not up, it returns
106 public Collection<Integer> getNeighbours(int i) {
108 Linkable lble=(Linkable)Network.node[i].getProtocol(protocolID);
109 ArrayList<Integer> al = new ArrayList<Integer>(lble.degree());
110 if( Network.node[i].isUp() )
112 for(int j=0; j<lble.degree(); ++j)
114 final Node n = lble.getNeighbor(j);
115 // if accessible, we include it
116 if(n.isUp()) al.add(Integer.valueOf(n.getIndex()));
119 return Collections.unmodifiableList(al);
122 // ---------------------------------------------------------------
124 /** Returns <code>Network.node[i]</code> */
125 public Object getNode(int i) { return Network.node[i]; }
127 // ---------------------------------------------------------------
130 * Returns null always
132 public Object getEdge(int i, int j) { return null; }
134 // ---------------------------------------------------------------
136 /** Returns <code>Network.size()</code> */
137 public int size() { return Network.size(); }
139 // --------------------------------------------------------------------
141 /** Returns always true */
142 public boolean directed() { return true; }
144 // --------------------------------------------------------------------
148 * In some cases this behaves strangely. Namely, when node i or j is not up,
149 * but is not dead (e.g. it can be down temporarily).
150 * In such situations the relevant link is made, but afterwards
151 * getEdge(i,j) will NOT return true, only when the fail state has changed back
154 * <p>Conceptually one can think of it as a successful operation which is
155 * immediately overruled by the dynamics of the underlying overlay network.
156 * Let's not forget that this class is an adaptor only.
159 * The behaviour of this method is affected by parameter {@link #wireDirected}.
160 * If it is false, then the opposite edge is set too.
162 public boolean setEdge( int i, int j ) {
163 // XXX slightly unintuitive behavior but makes sense when understood
166 ((Linkable)Network.node[j].getProtocol(protocolID)
167 ).addNeighbor(Network.node[i]);
171 ((Linkable)Network.node[i].getProtocol(protocolID)
172 ).addNeighbor(Network.node[j]);
175 // ---------------------------------------------------------------
178 public boolean clearEdge( int i, int j ) {
180 throw new UnsupportedOperationException();
183 // ---------------------------------------------------------------
186 * Returns number of neighbors that are up. If node i is down, returns 0.
188 public int degree(int i) {
190 if( !Network.node[i].isUp() ) return 0;
191 Linkable lble=(Linkable)Network.node[i].getProtocol(protocolID);
192 int numNeighbours = 0;
193 for(int j=0; j<lble.degree(); ++j)
195 final Node n = lble.getNeighbor(j);
196 // if accessible, we count it
197 if(n.isUp()) numNeighbours++;
199 return numNeighbours;
203 // ========================= other methods =======================
204 // ===============================================================
208 * Returns number of neighbors that are either up or down.
209 * If node i is down, returns 0.
211 public int fullDegree(int i) {
213 if( !Network.node[i].isUp() ) return 0;
214 Linkable lble=(Linkable)Network.node[i].getProtocol(protocolID);
215 return lble.degree();