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 implements a graph which uses a bitmatrix as inner representation
27 public class BitMatrixGraph implements Graph {
30 // ====================== private fileds ========================
31 // ==============================================================
33 private final List<BitSet> sets;
35 private final boolean directed;
37 // ====================== public constructors ===================
38 // ==============================================================
42 * Constructs a directed graph with the given number of nodes.
43 * The graph has no edges initially. The graph is directed.
44 * @param n size of graph
46 public BitMatrixGraph( int n ) {
51 // ---------------------------------------------------------------
54 * Constructs an graph with the given number of nodes.
55 * The graph has no edges initially.
56 * @param n size of graph
57 * @param directed if true graph is directed
59 public BitMatrixGraph( int n, boolean directed ) {
61 sets = new ArrayList<BitSet>(n);
62 for(int i=0; i<n; ++i) sets.add(new BitSet());
63 this.directed = directed;
67 // ======================= Graph implementations ================
68 // ==============================================================
71 public boolean isEdge(int i, int j) {
73 return sets.get(i).get(j);
76 // ---------------------------------------------------------------
78 public Collection<Integer> getNeighbours(int i) {
80 Set<Integer> result = new HashSet<Integer>();
81 BitSet neighb = sets.get(i);
82 final int max = size();
83 for(int j=0; j<max; ++j)
85 if( neighb.get(j) ) result.add(j);
88 return Collections.unmodifiableCollection(result);
91 // ---------------------------------------------------------------
93 /** Returns null always */
94 public Object getNode(int i) { return null; }
96 // ---------------------------------------------------------------
99 * Returns null always.
101 public Object getEdge(int i, int j) { return null; }
103 // ---------------------------------------------------------------
105 public int size() { return sets.size(); }
107 // --------------------------------------------------------------------
109 public boolean directed() { return directed; }
111 // --------------------------------------------------------------------
113 public boolean setEdge(int i, int j) {
115 if( i > size() || j > size() || i<0 || j<0 ) throw new
116 IndexOutOfBoundsException();
118 BitSet neighb = sets.get(i);
119 boolean old = neighb.get(j);
122 if( !old && !directed )
124 neighb = sets.get(j);
131 // --------------------------------------------------------------------
133 public boolean clearEdge(int i, int j) {
135 if( i > size() || j > size() || i<0 || j<0 ) throw new
136 IndexOutOfBoundsException();
138 BitSet neighb = sets.get(i);
139 boolean old = neighb.get(j);
142 if( old && !directed )
144 neighb = sets.get(i);
151 // --------------------------------------------------------------------
153 public int degree(int i) {
155 BitSet neighb = sets.get(i);
156 return neighb.cardinality(); // only from jdk 1.4