public class DorogovtsevMendesGenerator extends BaseGenerator
This generator creates graph using the Dorogovtsev - Mendes algorithm. This starts by creating three nodes and tree edges, making a triangle, and then add one node at a time. Each time a node is added, an edge is chosen randomly and the node is connected via two new edges to the two extremities of the chosen edge.
This process generates a power-low degree distribution, as nodes that have more edges have more chances to be selected since their edges are more represented in the edge set.
The Dorogovtsev - Mendes algorithm always produce planar graphs.
The more this generator is iterated, the more nodes are generated. It can
therefore generate trees of any size. A each call to nextEvents()
,
a new node and two edges are added.
Graph graph = new SingleGraph("Dorogovtsev mendes"); Generator gen = new DorogovtsevMendesGenerator(); gen.addSink(graph); gen.begin(); for(int i=0; i<100; i++) { gen.nextEvents(); } gen.end(); graph.display();
This kind of graph is described, among others, in the "Evolution of networks" by Dorogovtsev and Mendes.
SourceBase.ElementType
Modifier and Type | Field and Description |
---|---|
protected int |
nodeNames
Used to generate node names.
|
addEdgeLabels, addNodeLabels, directed, edgeAttributeRange, edgeAttributes, internalGraph, nodeAttributeRange, nodeAttributes, random, randomlyDirected
attrSinks, eltsSinks, eventProcessing, eventQueue, sourceId, sourceTime
Constructor and Description |
---|
DorogovtsevMendesGenerator()
Create a new generator with default random object.
|
DorogovtsevMendesGenerator(Random random)
New generator with the given random number generator.
|
Modifier and Type | Method and Description |
---|---|
void |
begin()
Init the generator.
|
void |
end()
End the graph generation by finalizing it.
|
boolean |
nextEvents()
Step of the DorogovtsevMendes generator.
|
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 int nodeNames
public DorogovtsevMendesGenerator()
public DorogovtsevMendesGenerator(Random random)
random
- The number generator to use.public void begin()
Generator.begin()
public boolean nextEvents()
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
WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses