com.phoenixst.plexus.examples

Class 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 GraphcreateBarabasiAlbert(int numInitialNodes, int numFinalNodes, int numEdges)
Creates a random graph according to the Barabasi-Albert model.
static GraphcreateStandardGraph(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 GraphcreateWattsStrogatz(int n, int d, double prob)
Creates a random graph according to the Watts-Strogatz model.

Method Detail

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.

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.

See the Plexus project home, hosted by SourceForge.
Copyright B) 1994-2006, by Phoenix Software Technologists, Inc. and others. All Rights Reserved. Use is subject to license terms.