X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/ff6cb26262ba25fefdf1265628265a75d790ebd6..200986a368bbbbb5df459d43cbc7f5ef3d7678db:/contrib/psg/src/peersim/graph/GraphFactory.java

diff --git a/contrib/psg/src/peersim/graph/GraphFactory.java b/contrib/psg/src/peersim/graph/GraphFactory.java
new file mode 100644
index 0000000000..81857cc0e0
--- /dev/null
+++ b/contrib/psg/src/peersim/graph/GraphFactory.java
@@ -0,0 +1,300 @@
+/*
+ * 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);
+}
+*/
+}
+