+++ /dev/null
-/*
- * Copyright (c) 2003-2005 The BISON Project
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Lesser General Public License version 2 as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- *
- */
-
-package peersim.graph;
-
-import java.util.*;
-
-/**
-* Contains static methods for wiring certain kinds of graphs. The general
-* contract of all methods is that they accept any graph and add edges
-* as specified in the documentation.
-*/
-public class GraphFactory {
-
-/** Disable instance construction */
-private GraphFactory() {}
-
-// ===================== public static methods ======================
-// ==================================================================
-
-/**
-* Wires a ring lattice.
-* The added connections are defined as follows. If k is even, links to
-* i-k/2, i-k/2+1, ..., i+k/2 are added (but not to i), thus adding an
-* equal number of predecessors and successors.
-* If k is odd, then we add one more successors than predecessors.
-* For example, for k=4: 2 predecessors, 2 successors.
-* For k=5: 2 predecessors, 3 successors.
-* For k=1: each node is linked only to its successor.
-* All values are understood mod n to make the lattice circular, where n is the
-* number of nodes in g.
-* @param g the graph to be wired
-* @param k lattice parameter
-* @return returns g for convenience
-*/
-public static Graph wireRingLattice(Graph g, int k) {
-
- final int n = g.size();
-
- int pred = k/2;
- int succ = k-pred;
-
- for(int i=0; i<n; ++i)
- for(int j=-pred; j<=succ; ++j)
- {
- if( j==0 ) continue;
- final int v = (i+j+n)%n;
- g.setEdge(i,v);
- }
- return g;
-}
-
-// -------------------------------------------------------------------
-
-/**
-* Watts-Strogatz model. A bit modified though: by default assumes a directed
-* graph. This means that directed
-* links are re-wired, and the undirected edges in the original (undirected)
-* lattice are modeled
-* by double directed links pointing in opposite directions. Rewiring is done
-* with replacement, so the possibility of wiring two links to the same target
-* is positive (though very small).
-* <p>
-* Note that it is possible to pass an undirected graph as a parameter. In that
-* case the output is the directed graph produced by the method, converted to
-* an undirected graph by dropping directionality of the edges. This graph is
-* still not from the original undirected WS model though.
-* @param g the graph to be wired
-* @param k lattice parameter: this is the out-degree of a node in the
-* ring lattice before rewiring
-* @param p the probability of rewiring each
-* @param r source of randomness
-* @return returns g for convenience
-*/
-public static Graph wireWS( Graph g, int k, double p, Random r ) {
-//XXX unintuitive to call it WS due to the slight mods
- final int n = g.size();
- for(int i=0; i<n; ++i)
- for(int j=-k/2; j<=k/2; ++j)
- {
- if( j==0 ) continue;
- int newedge = (i+j+n)%n;
- if( r.nextDouble() < p )
- {
- newedge = r.nextInt(n-1);
- if( newedge >= i ) newedge++; // random _other_ node
- }
- g.setEdge(i,newedge);
- }
- return g;
-}
-
-// -------------------------------------------------------------------
-
-/**
-* Random graph. Generates randomly k directed edges out of each node.
-* The neighbors
-* (edge targets) are chosen randomly without replacement from the nodes of the
-* graph other than the source node (i.e. no loop edge is added).
-* If k is larger than N-1 (where N is the number of nodes) then k is set to
-* be N-1 and a complete graph is returned.
-* @param g the graph to be wired
-* @param k samples to be drawn for each node
-* @param r source of randomness
-* @return returns g for convenience
-*/
-public static Graph wireKOut( Graph g, int k, Random r ) {
-
- final int n = g.size();
- if( n < 2 ) return g;
- if( n <= k ) k=n-1;
- int[] nodes = new int[n];
- for(int i=0; i<nodes.length; ++i) nodes[i]=i;
- for(int i=0; i<n; ++i)
- {
- int j=0;
- while(j<k)
- {
- int newedge = j+r.nextInt(n-j);
- int tmp = nodes[j];
- nodes[j] = nodes[newedge];
- nodes[newedge] = tmp;
- if( nodes[j] != i )
- {
- g.setEdge(i,nodes[j]);
- j++;
- }
- }
- }
- return g;
-}
-
-// -------------------------------------------------------------------
-
-/**
-* A sink star.
-* Wires a sink star topology adding a link to 0 from all other nodes.
-* @param g the graph to be wired
-* @return returns g for convenience
-*/
-public static Graph wireStar( Graph g ) {
-
- final int n = g.size();
- for(int i=1; i<n; ++i) g.setEdge(i,0);
- return g;
-}
-
-// -------------------------------------------------------------------
-
-/**
-* A regular rooted tree.
-* Wires a regular rooted tree. The root is 0, it has links to 1,...,k.
-* In general, node i has links to i*k+1,...,i*k+k.
-* @param g the graph to be wired
-* @param k the number of outgoing links of nodes in the tree (except
-* leaves that have zero out-links, and exactly one node that might have
-* less than k).
-* @return returns g for convenience
-*/
-public static Graph wireRegRootedTree( Graph g, int k ) {
-
- if( k==0 ) return g;
- final int n = g.size();
- int i=0; // node we wire
- int j=1; // next free node to link to
- while(j<n)
- {
- for(int l=0; l<k && j<n; ++l,++j) g.setEdge(i,j);
- ++i;
- }
- return g;
-}
-
-// -------------------------------------------------------------------
-
-/**
-* A hypercube.
-* Wires a hypercube.
-* For a node i the following links are added: i xor 2^0, i xor 2^1, etc.
-* this define a log(graphsize) dimensional hypercube (if the log is an
-* integer).
-* @param g the graph to be wired
-* @return returns g for convenience
-*/
-public static Graph wireHypercube( Graph g ) {
-
- final int n = g.size();
- if(n<=1) return g;
- final int highestone = Integer.highestOneBit(n-1); // not zero
- for(int i=0; i<n; ++i)
- {
- int mask = highestone;
- while(mask>0)
- {
- int j = i^mask;
- if(j<n) g.setEdge(i,j);
- mask = mask >> 1;
- }
-
- }
- return g;
-}
-
-// -------------------------------------------------------------------
-
-/**
-* This contains the implementation of the Barabasi-Albert model
-* of growing scale free networks. The original model is described in
-* <a href="http://arxiv.org/abs/cond-mat/0106096">
-http://arxiv.org/abs/cond-mat/0106096</a>.
-* It also works if the graph is directed, in which case the model is a
-* variation of the BA model
-* described in <a href="http://arxiv.org/pdf/cond-mat/0408391">
-http://arxiv.org/pdf/cond-mat/0408391</a>. In both cases, the number of the
-* initial set of nodes is the same as the degree parameter, and no links are
-* added. The first added node is connected to all of the initial nodes,
-* and after that the BA model is used normally.
-* @param k the number of edges that are generated for each new node, also
-* the number of initial nodes (that have no edges).
-* @param r the randomness to be used
-* @return returns g for convenience
-*/
-public static Graph wireScaleFreeBA( Graph g, int k, Random r ) {
-
- final int nodes = g.size();
- if( nodes <= k ) return g;
-
- // edge i has ends (ends[2*i],ends[2*i+1])
- int[] ends = new int[2*k*(nodes-k)];
-
- // Add initial edges from k to 0,1,...,k-1
- for(int i=0; i < k; i++)
- {
- g.setEdge(k,i);
- ends[2*i]=k;
- ends[2*i+1]=i;
- }
-
- int len = 2*k; // edges drawn so far is len/2
- for(int i=k+1; i < nodes; i++) // over the remaining nodes
- {
- for (int j=0; j < k; j++) // over the new edges
- {
- int target;
- do
- {
- target = ends[r.nextInt(len)];
- int m=0;
- while( m<j && ends[len+2*m+1]!=target) ++m;
- if(m==j) break;
- // we don't check in the graph because
- // this wire method should accept graphs
- // that already have edges.
- }
- while(true);
- g.setEdge(i,target);
- ends[len+2*j]=i;
- ends[len+2*j+1]=target;
- }
- len += 2*k;
- }
-
- return g;
-}
-
-// -------------------------------------------------------------------
-/*
-public static void main(String[] pars) {
-
- int n = Integer.parseInt(pars[0]);
- //int k = Integer.parseInt(pars[1]);
- Graph g = new BitMatrixGraph(n);
-
- //wireWS(g,20,.1,new Random());
- //GraphIO.writeChaco(new UndirectedGraph(g),System.out);
-
- //wireScaleFreeBA(g,3,new Random());
- //wireKOut(g,k,new Random());
- //wireRegRootedTree(g,k);
- wireHypercube(g);
- GraphIO.writeNeighborList(g,System.out);
-}
-*/
-}
-
