graphfactory.java

peersim仿真chord协议的测试过的环境

/*
 * 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);
}
*/
}