edu.stanford.math.plex4.graph.random

Class PrescribedDegrees

java.lang.Object

edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

edu.stanford.math.plex4.graph.random.PrescribedDegrees

All Implemented Interfaces:

java.io.Serializable

public class PrescribedDegrees
extends GraphInstanceGenerator

Implements a random prescribed degree graph by the algorithm presented in J.Blitstein and P.Diaconis

Author:

Santiago Akle, Tim Harrington

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

GraphInstanceGenerator.ImplementationType

Field Summary

Fields

Modifier and Type	Field and Description
protected int[]	degreeSequence
protected int	numNodes

Fields inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

graphImplementation, implementationType

Constructor Summary

Constructors

Constructor and Description
PrescribedDegrees(int[] degreeSequence)

Method Summary

Methods

Modifier and Type	Method and Description
protected static boolean	erdosGallaiCriteria(int[] d, int k) Checks the Erdos-Gallai criteria for a particular value of k.
AbstractUndirectedGraph	generate() Implements "Sequential Algorithm For Random Graph with Given Degrees" from "A SEQUENTIAL IMPORTANCE SAMPLING ALGORITHM FOR GENERATING RANDOM GRAPHS WITH PRESCRIBED DEGREES" By Joseph Blitzstein and Persi Diaconis
protected int[]	getCandidateList(int[] d, int i, AbstractUndirectedGraph graph) Computes the set of j!=i such that multiminus(d,i,j) is graphical and (i,j) is not already an edge.
protected double[]	getProbabilityPartition(int[] d) Constructs a partition p of [0,1] such that p[i+1]-p[i] is proportional to the degree of node i in the list d.
static boolean	isGraphical(int[] d) Determines if a degree sequence is realizable using the Erdos-Gallai Criteria
static int	minPositivePosition(int[] arr) Returns the first index of the smallest positive element or -1 if there are no positive entries
protected int[]	multiMinus(int[] ds, int i, int j) Returns the array ds with 1 subtracted from the i-th element and 1 subtracted from the j-th element.
java.lang.String	toString()
protected int	whichSegmentHasX(double[] p, double x) Returns the segment i such that x is in [p[i],p[i+1]].

Methods inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

initializeGraph, setImplementationType

Methods inherited from class java.lang.Object

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

Field Detail

degreeSequence

protected int[] degreeSequence

numNodes

protected int numNodes

Constructor Detail

PrescribedDegrees

public PrescribedDegrees(int[] degreeSequence)

Method Detail

generate

public AbstractUndirectedGraph generate()

Implements "Sequential Algorithm For Random Graph with Given Degrees" from "A SEQUENTIAL IMPORTANCE SAMPLING ALGORITHM FOR GENERATING RANDOM GRAPHS WITH PRESCRIBED DEGREES" By Joseph Blitzstein and Persi Diaconis

Specified by:

generate in class GraphInstanceGenerator

Parameters:

argd -

erdosGallaiCriteria

protected static boolean erdosGallaiCriteria(int[] d,
                          int k)

Checks the Erdos-Gallai criteria for a particular value of k.

Parameters:

d -

k -

Returns:

isGraphical

public static boolean isGraphical(int[] d)

Determines if a degree sequence is realizable using the Erdos-Gallai Criteria

Parameters:

degreeSequence -

Returns:

True if there exists at least one graph with this degree sequence.

whichSegmentHasX

protected int whichSegmentHasX(double[] p,
                   double x)

Returns the segment i such that x is in [p[i],p[i+1]]. The partition p has n+1 values representing n segments. Therefore the returned value will always be between 0 and n-1.

Parameters:

p -

x -

Returns:

getCandidateList

protected int[] getCandidateList(int[] d,
                     int i,
                     AbstractUndirectedGraph graph)

Computes the set of j!=i such that multiminus(d,i,j) is graphical and (i,j) is not already an edge.

Parameters:

d -

i -

Returns:

getProbabilityPartition

protected double[] getProbabilityPartition(int[] d)

Constructs a partition p of [0,1] such that p[i+1]-p[i] is proportional to the degree of node i in the list d. The return value p satisfies p[i] <= p[i+1], p[0]==0, and p[end] = 1.

Parameters:

d - degree sequence

Returns:

multiMinus

protected int[] multiMinus(int[] ds,
               int i,
               int j)

Returns the array ds with 1 subtracted from the i-th element and 1 subtracted from the j-th element.

Parameters:

ds -

i -

j -

Returns:

minPositivePosition

public static int minPositivePosition(int[] arr)

Returns the first index of the smallest positive element or -1 if there are no positive entries

Parameters:

arr -

Returns:

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object