edu.stanford.math.plex4.graph.random

Class HierarchicalERGraph

java.lang.Object

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

edu.stanford.math.plex4.graph.random.BinaryHierarchicalGraph

edu.stanford.math.plex4.graph.random.HierarchicalERGraph

All Implemented Interfaces:

java.io.Serializable

public class HierarchicalERGraph
extends BinaryHierarchicalGraph

Author:

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 double	erParameter
protected int	hgLeafCount
protected int	rootedGraphSize

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

debugFlag, k, maxProbability, numNodes

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

graphImplementation, implementationType

Constructor Summary

Constructors

Constructor and Description
HierarchicalERGraph(int n, int m, double maxProbability, double erParameter) Note: n and m should each be a power of 2

Method Summary

Methods

Modifier and Type	Method and Description
protected int	getERHierarchyLevelCount(int totalLevels)
double	getErParameter()
int	getHgLeafCount()
protected double[]	getProbabilities(int k, double dampingFactor) We need one probability for each potential common ancestor depth d=1..k-1.
int	getRootedGraphSize()
protected static int	roundUpToPowerOf2(int m)
java.lang.String	toString()

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

construct, constructEdges, debug, generate, getProbabilities, getTreeDepth

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

rootedGraphSize

protected int rootedGraphSize

hgLeafCount

protected int hgLeafCount

erParameter

protected double erParameter

Constructor Detail

HierarchicalERGraph

public HierarchicalERGraph(int n,
                   int m,
                   double maxProbability,
                   double erParameter)

Note: n and m should each be a power of 2

Parameters:

n - - the number of hierarchical graph leaves (this parameter is rounded up to the nearest power of 2)

m - - the size of the ER graph rooted at each hierarchical graph leaf (this parameter is rounded up to the nearest power of 2)

maxProbability -

erParameter -

Method Detail

roundUpToPowerOf2

protected static int roundUpToPowerOf2(int m)

getProbabilities

protected double[] getProbabilities(int k,
                        double dampingFactor)

We need one probability for each potential common ancestor depth d=1..k-1. They are constructed here. The ER graphs that are rooted at a leaf in the hierarchical graph are treated as additional j levels of hierarchy. Therefore, the probability annotations for the last j levels is set to a constant to simulate the ER construction.

Overrides:

getProbabilities in class BinaryHierarchicalGraph

Parameters:

k - a value such that (2^k <= n <= (2^{k+1})-1)

dampingFactor - a scaling factor in the open set (0,1)

Returns:

getERHierarchyLevelCount

protected int getERHierarchyLevelCount(int totalLevels)

toString

public java.lang.String toString()

Overrides:

toString in class BinaryHierarchicalGraph

getErParameter

public double getErParameter()

getHgLeafCount

public int getHgLeafCount()

getRootedGraphSize

public int getRootedGraphSize()