com.phoenixst.plexus.examples
Class RandomGraphFactory

java.lang.Object
  com.phoenixst.plexus.examples.RandomGraphFactory

public class RandomGraphFactory
extends Object

This class contains static factory methods for creating random graphs.

Since:

1.0

Version:

$Revision: 1.9 $

Author:

Ray A. Conner

Method Summary

static Graph	createBarabasiAlbert(int numInitialNodes, int numFinalNodes, int numEdges) Creates a random graph according to the Barabasi-Albert model.
static Graph	createStandardGraph(int n, double prob) Creates a random graph with n nodes where each pair of nodes has probability prob of having an edge between them.
static Graph	createWattsStrogatz(int n, int d, double prob) Creates a random graph according to the Watts-Strogatz model.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

createStandardGraph

public static Graph createStandardGraph(int n,
                                        double prob)

Creates a random graph with n nodes where each pair of nodes has probability prob of having an edge between them.

createWattsStrogatz

public static Graph createWattsStrogatz(int n,
                                        int d,
                                        double prob)

Creates a random graph according to the Watts-Strogatz model. The number d here is half of K in the standard literature.

Start with a circulant graph. Arrange the nodes in a circle, starting at 0 and increasing, in order, clockwise. Begin with node 0 and the edge which connects it to its nearest clockwise neighbor, which is node 1. With probability prob, reconnect this edge from node 0 to a uniformly randomly selected node, with duplicate and self edges forbidden. Repeat this process for each node, moving clockwise around the circle. Now, repeat the entire cycle, but instead choose edges which connect nodes to their second-nearest clockwise neighbor. And so on, until every one of the original edges has been considered.

createBarabasiAlbert

public static Graph createBarabasiAlbert(int numInitialNodes,
                                         int numFinalNodes,
                                         int numEdges)

Creates a random graph according to the Barabasi-Albert model.

Start with numInitialNodes nodes. At each step, add a new node which is connected to numEdges existing nodes, with preference given to nodes that are more highly connected.