org.graphstream.algorithm.generator

Class RandomFixedDegreeDynamicGraphGenerator

java.lang.Object

org.graphstream.stream.SourceBase

org.graphstream.algorithm.generator.BaseGenerator

org.graphstream.algorithm.generator.RandomFixedDegreeDynamicGraphGenerator

All Implemented Interfaces:

Generator, org.graphstream.stream.Source

public class RandomFixedDegreeDynamicGraphGenerator
extends BaseGenerator

This is a graph generator that generates dynamic random graphs. The principle:

A graph consists in a set of vertices and a set of edges. The dynamic relies on 4 kinds of steps of events: at each step:

• a subset of nodes is removed
• a subset of nodes is added
• a subset of edges is removed (in the current version, edges that are removed are those that were attached to nodes that disappear)
• a subset of edges is added

This generator is characterized by:

• The parameters:
  • number of vertices
  • maximum mean degree
• The constraints:
  • graph nervosity
  • creation links rules
• The metrics:
  • mean number of vertices and edges
  • mean age of vertices and edges
  • mean distribution of degree
  • mean number of connected components
  • ...
  • ...

How to build such graphs ? There exist at least one mathematical function for doing that f(step) = nbVertices*log(step)/log(step+"Pente") the larger "Pente", the softer the "pente" of the curve. Given f(step), it is possible to compute nbCreations and nbDeletions together with the graph nervosity. f(step) represents the number of vertices that should be present within the graph given the step and the value of the parameter "Pente". However, as our graph is dynamic, some vertices may be deleted while some other vertices may be added to the graph. Question: could it be possible to build a dynamic graph that reaches a stable state (stabilization of the number of vertices, and stabilization of some other properties), just by adding some constraints/characteristics on each node?

Since:

20080616

Author:

Frédéric Guinand

Nested Class Summary

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

org.graphstream.stream.SourceBase.ElementType

Constructor Summary

Constructors

Constructor and Description
RandomFixedDegreeDynamicGraphGenerator() Create a new RandomFixedDegreeDynamicGraphGenerator generator with default values for attributes.
RandomFixedDegreeDynamicGraphGenerator(int nbVertices, double meanDegreeLimit, double nervousness) Create a new RandomFixedDegreeDynamicGraphGenerator generator.

Method Summary

Modifier and Type	Method and Description
void	begin() Begin the graph generation.
void	end() End the graph generation by finalizing it.
double	meanDegree() This method computes the mean degree of the graph.
boolean	nextEvents() Step of the generator.

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

addEdgeAttribute, addEdgeAttribute, addEdgeAttribute, addEdgeLabels, addNodeAttribute, addNodeAttribute, addNodeAttribute, addNodeLabels, isUsingInternalGraph, removeEdgeAttribute, removeNodeAttribute, setDirectedEdges, 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

RandomFixedDegreeDynamicGraphGenerator

public RandomFixedDegreeDynamicGraphGenerator()

Create a new RandomFixedDegreeDynamicGraphGenerator generator with default values for attributes.

See Also:

RandomFixedDegreeDynamicGraphGenerator(int, double, double)

RandomFixedDegreeDynamicGraphGenerator

public RandomFixedDegreeDynamicGraphGenerator(int nbVertices,
                                              double meanDegreeLimit,
                                              double nervousness)

Create a new RandomFixedDegreeDynamicGraphGenerator generator.

Parameters:

nbVertices - The number of vertices.

meanDegreeLimit - The average degree.

nervousness - The nervousness.

Method Detail

meanDegree

public double meanDegree()

This method computes the mean degree of the graph.

begin

public void begin()

Description copied from interface: Generator

Begin the graph generation. This usually is the place for initialization of the generator. After calling this method, call the Generator.nextEvents() method to add elements to the graph.

nextEvents

public boolean nextEvents()

Step of the generator. Some nodes will be removed according to the nervousness, then new nodes and new edges will be added.

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