public class RandomGenerator extends BaseGenerator
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
.
Graph graph = new SingleGraph("Random"); Generator gen = new RandomGenerator(); gen.addSinkg(graph); gen.begin(); while (graph.getNodeCount() < 100 && gen.nextEvents()); gen.end(); graph.display();
SourceBase.ElementType
Modifier and Type | Field and Description |
---|---|
protected boolean |
allowRemove
Can we remove existing edges?
|
protected double |
averageDegree
the average degree
|
protected List<String> |
edgeIds
List storing edge ids.
|
protected int |
nodeCount
The number of nodes generated so far.
|
protected Set<Integer> |
subset
For drawing random subsets
|
addEdgeLabels, addNodeLabels, directed, edgeAttributeRange, edgeAttributes, internalGraph, nodeAttributeRange, nodeAttributes, random, randomlyDirected
attrSinks, eltsSinks, eventProcessing, eventQueue, sourceId, sourceTime
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
|
Modifier and Type | Method and Description |
---|---|
protected void |
addNewEdges(double p)
nextEvents helper.
|
void |
begin()
Starts the generator.
|
void |
end()
End the graph generation by finalizing it.
|
protected void |
init(double averageDegree,
boolean allowRemove)
Constructor helper
|
boolean |
nextEvents()
If edge removing is allowed, removes a small fraction of the existing
edges.
|
protected void |
removeExistingEdges(double p)
nextEvents helper.
|
addEdge, addEdgeAttribute, addEdgeLabels, addNode, addNode, addNodeAttribute, addNodeLabels, clearKeptData, delEdge, delNode, isUsingInternalGraph, removeEdgeAttribute, removeNodeAttribute, setDirectedEdges, setEdgeAttributesRange, setNodeAttributesRange, setRandomSeed, setUseInternalGraph
addAttributeSink, addElementSink, addSink, attributeSinks, clearAttributeSinks, clearElementSinks, clearSinks, elementSinks, manageEvents, 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
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
addAttributeSink, addElementSink, addSink, clearAttributeSinks, clearElementSinks, clearSinks, removeAttributeSink, removeElementSink, removeSink
protected double averageDegree
protected boolean allowRemove
protected int nodeCount
public RandomGenerator()
public RandomGenerator(double averageDegree)
averageDegree
- The average degree of the resulting graph.IllegalArgumentException
- if averageDegree
is negativepublic RandomGenerator(double averageDegree, boolean allowRemove)
averageDegree
- The average degree of the resulting graph.allowRemove
- If true, some existing edges are removed at each step.IllegalArgumentException
- if averageDegree
is negativepublic RandomGenerator(double averageDegree, boolean allowRemove, boolean directed)
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.IllegalArgumentException
- if averageDegree
is negativepublic RandomGenerator(double averageDegree, boolean allowRemove, boolean directed, String nodeAttribute, String edgeAttribute)
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.IllegalArgumentException
- if averageDegree
is negativepublic void begin()
Generator.begin()
public boolean nextEvents()
true
Generator.nextEvents()
public void end()
BaseGenerator
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.end
in interface Generator
end
in class BaseGenerator
protected void init(double averageDegree, boolean allowRemove)
averageDegree
- The average degree of the resulting graph.allowRemove
- If true, some existing edges are removed at each step.protected void addNewEdges(double p)
p
- probability to add each possible edgeprotected void removeExistingEdges(double p)
p
- probability to remove each existing edge.WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses