org.graphstream.algorithm.generator
Class DorogovtsevMendesGenerator

java.lang.Object
  extended by org.graphstream.stream.SourceBase
      extended by org.graphstream.algorithm.generator.BaseGenerator
          extended by org.graphstream.algorithm.generator.DorogovtsevMendesGenerator
All Implemented Interfaces:
Generator, org.graphstream.stream.Source

public class DorogovtsevMendesGenerator
extends BaseGenerator

Dorogovtsev - Mendes graph generator.

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.

Usage

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.

Complexity

At each step only one node and two edges are added.

Example

 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();
 

References

This kind of graph is described, among others, in the "Evolution of networks" by Dorogovtsev and Mendes.

Since:
20070117
Scientific Reference :
S. N. Dorogovtsev and J. F. F. Mendes, "Evolution of networks", in Adv. Phys. 51, 2002, 1079--1187,  arXiv:cond-mat/0106144v2

Nested Class Summary
 
Nested classes/interfaces inherited from class org.graphstream.stream.SourceBase
org.graphstream.stream.SourceBase.ElementType
 
Constructor Summary
DorogovtsevMendesGenerator()
          Create a new generator with default random object.
DorogovtsevMendesGenerator(Random random)
          New generator with the given random number generator.
 
Method Summary
 void begin()
          Init the generator.
 void end()
          End the graph generation by finalizing it.
 boolean nextEvents()
          Step of the DorogovtsevMendes generator.
 
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

DorogovtsevMendesGenerator

public DorogovtsevMendesGenerator()
Create a new generator with default random object.


DorogovtsevMendesGenerator

public DorogovtsevMendesGenerator(Random random)
New generator with the given random number generator.

Parameters:
random - The number generator to use.
Method Detail

begin

public void begin()
Init the generator. An initial full graph of three nodes is build here.

See Also:
Generator.begin()

nextEvents

public boolean nextEvents()
Step of the DorogovtsevMendes generator. Add a new node n, then an edge is chosen randomly and its extremities are connected to the new node n.

Returns:
true while there are elements to add to the graph.
See Also:
Generator.nextEvents()

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


Copyright © 2013. All Rights Reserved.