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 for representing subgraphs of any graph.
25 * The subgraph is defined the following way.
26 * The subgraph always contains all the nodes of the original underlying
27 * graph. However, it is possible to remove edges by flagging nodes as
28 * removed, in which case
29 * the edges that have at least one end on those nodes are removed.
30 * If the underlying graph changes after initialization, this class follows
33 public class SubGraphEdges implements Graph {
36 // ====================== private fields ========================
37 // ==============================================================
40 private final Graph g;
42 private final BitSet nodes;
45 // ====================== public constructors ===================
46 // ==============================================================
50 * Constructs an initially empty subgraph of g. That is, the subgraph will
53 public SubGraphEdges( Graph g ) {
56 nodes = new BitSet(g.size());
60 // ======================= Graph implementations ================
61 // ==============================================================
64 public boolean isEdge(int i, int j) {
66 return nodes.get(i) && nodes.get(j) && g.isEdge(i,j);
69 // ---------------------------------------------------------------
71 public Collection<Integer> getNeighbours(int i) {
73 List<Integer> result = new LinkedList<Integer>();
76 for(Integer in:g.getNeighbours(i))
78 if( nodes.get(in) ) result.add(in);
82 return Collections.unmodifiableCollection(result);
85 // ---------------------------------------------------------------
87 public Object getNode(int i) { return g.getNode(i); }
89 // ---------------------------------------------------------------
92 * If both i and j are within the node set of the subgraph and the original
93 * graph has an (i,j) edge, returns that edge.
95 public Object getEdge(int i, int j) {
97 if( isEdge(i,j) ) return g.getEdge(i,j);
101 // --------------------------------------------------------------------
103 public int size() { return g.size(); }
105 // --------------------------------------------------------------------
107 public boolean directed() { return g.directed(); }
109 // --------------------------------------------------------------------
112 public boolean setEdge( int i, int j ) {
114 throw new UnsupportedOperationException();
117 // ---------------------------------------------------------------
120 public boolean clearEdge( int i, int j ) {
122 throw new UnsupportedOperationException();
125 // ---------------------------------------------------------------
127 public int degree(int i) {
132 for(Integer in:g.getNeighbours(i))
134 if( nodes.get(in) ) degree++;
141 // ================= public functions =================================
142 // ====================================================================
146 * This function returns the size of the subgraph, i.e. the number of nodes
149 public int subGraphSize() { return nodes.cardinality(); }
151 // --------------------------------------------------------------------
154 * Removes given node from subgraph.
155 * @return true if the node was already in the subgraph otherwise false.
157 public boolean removeNode(int i) {
159 boolean was = nodes.get(i);
164 // --------------------------------------------------------------------
167 * Adds given node to subgraph.
168 * @return true if the node was already in the subgraph otherwise false.
170 public boolean addNode(int i) {
172 boolean was = nodes.get(i);