org.graphstream.algorithm.generator

Class RandomGenerator

java.lang.Object

org.graphstream.stream.SourceBase

org.graphstream.algorithm.generator.BaseGenerator

org.graphstream.algorithm.generator.RandomGenerator

All Implemented Interfaces:

Generator, org.graphstream.stream.Source

public class RandomGenerator
extends BaseGenerator

Random graph generator.

This generator creates random graphs of any size n with given average degree k and binomial degree distribution B(n, k / (n - 1)). Calling begin() creates a clique of size k. Each call of nextEvents() removes a small fraction of existing edges, adds a new node and connects it randomly with some of the old nodes.

After n - k steps we obtain a Erdős–Rényí random graph G(n, p) with p = k / (n - 1). In other words the result is the same as if we started with n isolated nodes and connected each pair of them with probability p.

This generator can work in "non-destructive" mode controlled by a constructor parameter called allowRemove with default value true. If this parameter is false, existing edges are never removed. The obtained graph has the same average degree, but different degree distribution. This distribution is asymmetric, more stretched than the binomial distribution, with a peak on the left of the average degree. This mode is slightly faster and more memory-efficient. Use it if you do not want edges to be removed and if you do not care about the degree distribution.

This generator has the ability to add randomly chosen numerical values on arbitrary attributes on edges or nodes of the graph, and to randomly choose a direction for edges. For more information see BaseGenerator.

Example

 Graph graph = new SingleGraph("Random");
 Generator gen = new RandomGenerator();
 gen.addSinkg(graph);
 gen.begin();
 while (graph.getNodeCount() < 100 && gen.nextEvents());
 gen.end();
 graph.display();
 

Nested Class Summary

Nested classes/interfaces inherited from class org.graphstream.stream.SourceBase

org.graphstream.stream.SourceBase.ElementType

Constructor Summary

Constructors

Constructor and Description
RandomGenerator() Creates a generator with default average degree of 1.
RandomGenerator(double averageDegree) Creates a generator with given average degree.
RandomGenerator(double averageDegree, boolean allowRemove) Creates a generator with given average degree.
RandomGenerator(double averageDegree, boolean allowRemove, boolean directed) Creates a generator with given average degree.
RandomGenerator(double averageDegree, boolean allowRemove, boolean directed, String nodeAttribute, String edgeAttribute) Creates a generator with given average degree

Method Summary

Methods

Modifier and Type	Method and Description
void	begin() Starts the generator.
void	end() End the graph generation by finalizing it.
boolean	nextEvents() If edge removing is allowed, removes a small fraction of the existing edges.

Methods inherited from class org.graphstream.algorithm.generator.BaseGenerator

addEdgeAttribute, addEdgeLabels, addNodeAttribute, addNodeLabels, isUsingInternalGraph, removeEdgeAttribute, removeNodeAttribute, setDirectedEdges, setEdgeAttributesRange, setNodeAttributesRange, setRandomSeed, setUseInternalGraph

Methods inherited from class org.graphstream.stream.SourceBase

addAttributeSink, addElementSink, addSink, attributeSinks, clearAttributeSinks, clearElementSinks, clearSinks, elementSinks, removeAttributeSink, removeElementSink, removeSink, sendAttributeChangedEvent, sendAttributeChangedEvent, sendEdgeAdded, sendEdgeAdded, sendEdgeAttributeAdded, sendEdgeAttributeAdded, sendEdgeAttributeChanged, sendEdgeAttributeChanged, sendEdgeAttributeRemoved, sendEdgeAttributeRemoved, sendEdgeRemoved, sendEdgeRemoved, sendGraphAttributeAdded, sendGraphAttributeAdded, sendGraphAttributeChanged, sendGraphAttributeChanged, sendGraphAttributeRemoved, sendGraphAttributeRemoved, sendGraphCleared, sendGraphCleared, sendNodeAdded, sendNodeAdded, sendNodeAttributeAdded, sendNodeAttributeAdded, sendNodeAttributeChanged, sendNodeAttributeChanged, sendNodeAttributeRemoved, sendNodeAttributeRemoved, sendNodeRemoved, sendNodeRemoved, sendStepBegins, sendStepBegins

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graphstream.stream.Source

addAttributeSink, addElementSink, addSink, clearAttributeSinks, clearElementSinks, clearSinks, removeAttributeSink, removeElementSink, removeSink

Constructor Detail

RandomGenerator

public RandomGenerator()

Creates a generator with default average degree of 1.

RandomGenerator

public RandomGenerator(double averageDegree)

Creates a generator with given average degree.

Parameters:

averageDegree - The average degree of the resulting graph.

Throws:

IllegalArgumentException - if averageDegree is negative

RandomGenerator

public RandomGenerator(double averageDegree,
               boolean allowRemove)

Creates a generator with given average degree.

Parameters:

averageDegree - The average degree of the resulting graph.

allowRemove - If true, some existing edges are removed at each step.

Throws:

IllegalArgumentException - if averageDegree is negative

RandomGenerator

public RandomGenerator(double averageDegree,
               boolean allowRemove,
               boolean directed)

Creates a generator with given average degree.

Parameters:

averageDegree - The average degree of the resulting graph.

allowRemove - If true, some existing edges are removed at each step.

directed - If true, generated edges are directed.

Throws:

IllegalArgumentException - if averageDegree is negative

RandomGenerator

public RandomGenerator(double averageDegree,
               boolean allowRemove,
               boolean directed,
               String nodeAttribute,
               String edgeAttribute)

Creates a generator with given average degree

Parameters:

averageDegree - The average degree of the resulting graph.

allowRemove - If true, some existing edges are removed at each step.

directed - If true, generated edges are directed.

nodeAttribute - An attribute with this name and a random numeric value is put on each node.

edgeAttribute - An attribute with this name and a random numeric value is put on each edge.

Throws:

IllegalArgumentException - if averageDegree is negative

Method Detail

begin

public void begin()

Starts the generator. A clique of size equal to the average degree is added.

See Also:

Generator.begin()

Computational Complexity :

O(k²) where k is the average degree

nextEvents

public boolean nextEvents()

If edge removing is allowed, removes a small fraction of the existing edges. Then adds a new node and connects it randomly with some of the existing nodes.

Returns:

true

See Also:

Generator.nextEvents()

Computational Complexity :

Each call of this method takes on average O(k) steps, where k is the average degree. Thus generating a graph with n nodes will take O(nk) time. The space complexity is O(nk) if edge removing is allowed and O(k) otherwise.

end

public void end()

Description copied from class: BaseGenerator

End the graph generation by finalizing it. Once the Generator.nextEvents() method returned false (or even if you stop before), this method must be called to finish the graph. In addition, BaseGenerator adds a "clear" operations that removes all the kept edges and nodes identifiers and the associated data.

Specified by:

end in interface Generator

Overrides:

end in class BaseGenerator