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 * Contains static methods for wiring certain kinds of graphs. The general
25 * contract of all methods is that they accept any graph and add edges
26 * as specified in the documentation.
28 public class GraphFactory {
30 /** Disable instance construction */
31 private GraphFactory() {}
33 // ===================== public static methods ======================
34 // ==================================================================
37 * Wires a ring lattice.
38 * The added connections are defined as follows. If k is even, links to
39 * i-k/2, i-k/2+1, ..., i+k/2 are added (but not to i), thus adding an
40 * equal number of predecessors and successors.
41 * If k is odd, then we add one more successors than predecessors.
42 * For example, for k=4: 2 predecessors, 2 successors.
43 * For k=5: 2 predecessors, 3 successors.
44 * For k=1: each node is linked only to its successor.
45 * All values are understood mod n to make the lattice circular, where n is the
46 * number of nodes in g.
47 * @param g the graph to be wired
48 * @param k lattice parameter
49 * @return returns g for convenience
51 public static Graph wireRingLattice(Graph g, int k) {
53 final int n = g.size();
58 for(int i=0; i<n; ++i)
59 for(int j=-pred; j<=succ; ++j)
62 final int v = (i+j+n)%n;
68 // -------------------------------------------------------------------
71 * Watts-Strogatz model. A bit modified though: by default assumes a directed
72 * graph. This means that directed
73 * links are re-wired, and the undirected edges in the original (undirected)
75 * by double directed links pointing in opposite directions. Rewiring is done
76 * with replacement, so the possibility of wiring two links to the same target
77 * is positive (though very small).
79 * Note that it is possible to pass an undirected graph as a parameter. In that
80 * case the output is the directed graph produced by the method, converted to
81 * an undirected graph by dropping directionality of the edges. This graph is
82 * still not from the original undirected WS model though.
83 * @param g the graph to be wired
84 * @param k lattice parameter: this is the out-degree of a node in the
85 * ring lattice before rewiring
86 * @param p the probability of rewiring each
87 * @param r source of randomness
88 * @return returns g for convenience
90 public static Graph wireWS( Graph g, int k, double p, Random r ) {
91 //XXX unintuitive to call it WS due to the slight mods
92 final int n = g.size();
93 for(int i=0; i<n; ++i)
94 for(int j=-k/2; j<=k/2; ++j)
97 int newedge = (i+j+n)%n;
98 if( r.nextDouble() < p )
100 newedge = r.nextInt(n-1);
101 if( newedge >= i ) newedge++; // random _other_ node
103 g.setEdge(i,newedge);
108 // -------------------------------------------------------------------
111 * Random graph. Generates randomly k directed edges out of each node.
113 * (edge targets) are chosen randomly without replacement from the nodes of the
114 * graph other than the source node (i.e. no loop edge is added).
115 * If k is larger than N-1 (where N is the number of nodes) then k is set to
116 * be N-1 and a complete graph is returned.
117 * @param g the graph to be wired
118 * @param k samples to be drawn for each node
119 * @param r source of randomness
120 * @return returns g for convenience
122 public static Graph wireKOut( Graph g, int k, Random r ) {
124 final int n = g.size();
125 if( n < 2 ) return g;
127 int[] nodes = new int[n];
128 for(int i=0; i<nodes.length; ++i) nodes[i]=i;
129 for(int i=0; i<n; ++i)
134 int newedge = j+r.nextInt(n-j);
136 nodes[j] = nodes[newedge];
137 nodes[newedge] = tmp;
140 g.setEdge(i,nodes[j]);
148 // -------------------------------------------------------------------
152 * Wires a sink star topology adding a link to 0 from all other nodes.
153 * @param g the graph to be wired
154 * @return returns g for convenience
156 public static Graph wireStar( Graph g ) {
158 final int n = g.size();
159 for(int i=1; i<n; ++i) g.setEdge(i,0);
163 // -------------------------------------------------------------------
166 * A regular rooted tree.
167 * Wires a regular rooted tree. The root is 0, it has links to 1,...,k.
168 * In general, node i has links to i*k+1,...,i*k+k.
169 * @param g the graph to be wired
170 * @param k the number of outgoing links of nodes in the tree (except
171 * leaves that have zero out-links, and exactly one node that might have
173 * @return returns g for convenience
175 public static Graph wireRegRootedTree( Graph g, int k ) {
178 final int n = g.size();
179 int i=0; // node we wire
180 int j=1; // next free node to link to
183 for(int l=0; l<k && j<n; ++l,++j) g.setEdge(i,j);
189 // -------------------------------------------------------------------
194 * For a node i the following links are added: i xor 2^0, i xor 2^1, etc.
195 * this define a log(graphsize) dimensional hypercube (if the log is an
197 * @param g the graph to be wired
198 * @return returns g for convenience
200 public static Graph wireHypercube( Graph g ) {
202 final int n = g.size();
204 final int highestone = Integer.highestOneBit(n-1); // not zero
205 for(int i=0; i<n; ++i)
207 int mask = highestone;
211 if(j<n) g.setEdge(i,j);
219 // -------------------------------------------------------------------
222 * This contains the implementation of the Barabasi-Albert model
223 * of growing scale free networks. The original model is described in
224 * <a href="http://arxiv.org/abs/cond-mat/0106096">
225 http://arxiv.org/abs/cond-mat/0106096</a>.
226 * It also works if the graph is directed, in which case the model is a
227 * variation of the BA model
228 * described in <a href="http://arxiv.org/pdf/cond-mat/0408391">
229 http://arxiv.org/pdf/cond-mat/0408391</a>. In both cases, the number of the
230 * initial set of nodes is the same as the degree parameter, and no links are
231 * added. The first added node is connected to all of the initial nodes,
232 * and after that the BA model is used normally.
233 * @param k the number of edges that are generated for each new node, also
234 * the number of initial nodes (that have no edges).
235 * @param r the randomness to be used
236 * @return returns g for convenience
238 public static Graph wireScaleFreeBA( Graph g, int k, Random r ) {
240 final int nodes = g.size();
241 if( nodes <= k ) return g;
243 // edge i has ends (ends[2*i],ends[2*i+1])
244 int[] ends = new int[2*k*(nodes-k)];
246 // Add initial edges from k to 0,1,...,k-1
247 for(int i=0; i < k; i++)
254 int len = 2*k; // edges drawn so far is len/2
255 for(int i=k+1; i < nodes; i++) // over the remaining nodes
257 for (int j=0; j < k; j++) // over the new edges
262 target = ends[r.nextInt(len)];
264 while( m<j && ends[len+2*m+1]!=target) ++m;
266 // we don't check in the graph because
267 // this wire method should accept graphs
268 // that already have edges.
273 ends[len+2*j+1]=target;
281 // -------------------------------------------------------------------
283 public static void main(String[] pars) {
285 int n = Integer.parseInt(pars[0]);
286 //int k = Integer.parseInt(pars[1]);
287 Graph g = new BitMatrixGraph(n);
289 //wireWS(g,20,.1,new Random());
290 //GraphIO.writeChaco(new UndirectedGraph(g),System.out);
292 //wireScaleFreeBA(g,3,new Random());
293 //wireKOut(g,k,new Random());
294 //wireRegRootedTree(g,k);
296 GraphIO.writeNeighborList(g,System.out);