- java.lang.Object
-
- org.jgrapht.generate.DirectedScaleFreeGraphGenerator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
GraphGenerator<V,E,V>
public class DirectedScaleFreeGraphGenerator<V,E> extends java.lang.Object implements GraphGenerator<V,E,V>
A generator for directed scale-free graphs.This generator creates a directed scale-free graph according to a power law, as described in Bollobás et al. The paper can be cited as Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. "Directed scale-free graphs." Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2003.
In This generator, the graph continues to grow one edge per step, according to the probabilities alpha, beta, and gamma (which sum up to 1).
- alpha is the probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.
- beta is the probability that the new edge is from an existing vertex v to an existing vertex w, where v and w are chosen independently, v according to d_out + delta_out, and w according to d_in + delta_in.
- gamma is the probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.
In their original paper, the graph continues to grow according to a certain power law until a certain number of edges is reached irrespective to the number of nodes.
However, because the target number of edges is not known beforehand, in this implementation, we added another feature that enables the user to grow the curve according to that power law until the target number of edges or target number of nodes is reached.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
DirectedScaleFreeGraphGenerator.Direction
An enum to indicate the vertex selection using its inDegree or outDegree
-
Field Summary
Fields Modifier and Type Field Description private boolean
allowingMultipleEdges
Control whether the generated graph may contain loops.private boolean
allowingSelfLoops
Control whether the generated graph many contain multiple (parallel) edges between the same two verticesprivate float
alpha
probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in criterion.private float
alphaPlusBeta
The probability that the new edge is (from a new vertex v to an existing vertex w) plus the probability that the new edge is (from an existing vertex v to an existing vertex w), where v and w are chosen independently, v according to d_out + delta_out, and w according to d_in + delta_in criteria.private float
deltaIn
In-degree bias used for Alpha and Betaprivate float
deltaOut
Out-degree bias used for Beta and Gammaprivate int
maxFailures
Maximum number of consecutive failed attempts to add an edge.private java.util.Random
rng
private int
targetEdges
Target total number of edges to reach.private int
targetNodes
Target total number of targetNodes to reach.
This has lower priority thantargetEdges
.
-
Constructor Summary
Constructors Constructor Description DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes)
Constructs a Generator.DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, long seed)
Constructs a Generator using a seed for the random number generator.DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, long seed, boolean allowingMultipleEdges, boolean allowingSelfLoops)
Constructs a Generator using a seed for the random number generator and sets the two relaxation optionsallowingMultipleEdges
andallowingSelfLoops
.DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, java.util.Random rng)
Construct a new generator using the provided random number generator.DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, java.util.Random rng, boolean allowingMultipleEdges, boolean allowingSelfLoops)
Construct a new generator using the provided random number generator and sets the two relaxation optionsallowingMultipleEdges
andallowingSelfLoops
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
generateGraph(Graph<V,E> target, java.util.Map<java.lang.String,V> resultMap)
Generates an instance of theGraph
.int
getMaxFailures()
Returns the maximum allowed number of consecutive failed attempts to add an edge.boolean
isAllowingMultipleEdges()
Returns whether the generated graph may contain multiple (parallel) edges between the same two vertices.boolean
isAllowingSelfLoops()
Returns whether the generated graph may contain multiple (parallel) edges between the same two verticesprivate V
pickAVertex(Graph<V,E> target, java.util.Set<V> allNewNodes, java.util.Set<E> allNewEdgesSet, DirectedScaleFreeGraphGenerator.Direction direction, float bias)
Select a vertex from the currently available vertices, using the passed bias.void
setAllowingMultipleEdges(boolean allowingMultipleEdges)
Sets whether the generated graph may contain multiple (parallel) edges between the same two verticesvoid
setAllowingSelfLoops(boolean allowingSelfLoops)
Sets whether the generated graph may contain multiple (parallel) edges between the same two verticesvoid
setMaxFailures(int maxFailures)
Sets the maximum allowed number of consecutive failed attempts to add an edge (must be non negative).-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface org.jgrapht.generate.GraphGenerator
generateGraph
-
-
-
-
Field Detail
-
rng
private final java.util.Random rng
-
alpha
private final float alpha
probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in criterion.
-
alphaPlusBeta
private final float alphaPlusBeta
The probability that the new edge is (from a new vertex v to an existing vertex w) plus the probability that the new edge is (from an existing vertex v to an existing vertex w), where v and w are chosen independently, v according to d_out + delta_out, and w according to d_in + delta_in criteria. This equals 1 - gamma. Gamma refers to the probability that the new edge is from an existing vertex v to a new vertex w.
-
deltaIn
private final float deltaIn
In-degree bias used for Alpha and Beta
-
deltaOut
private final float deltaOut
Out-degree bias used for Beta and Gamma
-
targetEdges
private final int targetEdges
Target total number of edges to reach. It has a higher priority thantargetNodes
. Zero is a valid value.
If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore,targetNodes
will be considered instead. Otherwise,targetEdges
will be considered andtargetEdges
will be ignored.
-
targetNodes
private final int targetNodes
Target total number of targetNodes to reach.
This has lower priority thantargetEdges
. It will not be used unlesstargetEdges
given is a negative number.
-
maxFailures
private int maxFailures
Maximum number of consecutive failed attempts to add an edge.
-
allowingMultipleEdges
private boolean allowingMultipleEdges
Control whether the generated graph may contain loops.
-
allowingSelfLoops
private boolean allowingSelfLoops
Control whether the generated graph many contain multiple (parallel) edges between the same two vertices
-
-
Constructor Detail
-
DirectedScaleFreeGraphGenerator
public DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes)
Constructs a Generator.- Parameters:
alpha
- The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.gamma
- The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.deltaIn
- The in-degree bias used for Alpha and Beta.deltaOut
- The out-degree bias used for Beta and Gamma.targetEdges
- Target total number of edges to reach. It has a higher priority thantargetNodes
. Zero is a valid value.
If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore,targetNodes
will be considered instead. Otherwise,targetEdges
will be considered andtargetEdges
will be ignored.targetNodes
- Target number of nodes to reach. Zero is a valid value.
This parameter has lower priority thantargetEdges
and will be used only iftargetEdges
given is a negative number.
-
DirectedScaleFreeGraphGenerator
public DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, long seed)
Constructs a Generator using a seed for the random number generator.- Parameters:
alpha
- The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.gamma
- The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.deltaIn
- The in-degree bias used for Alpha and Beta.deltaOut
- The out-degree bias used for Beta and Gamma.targetEdges
- Target total number of edges to reach. It has a higher priority thantargetNodes
. Zero is a valid value.
If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore,targetNodes
will be considered instead. Otherwise,targetEdges
will be considered andtargetEdges
will be ignored.targetNodes
- Target number of nodes to reach. Zero is a valid value.
This parameter has lower priority thantargetEdges
and will be used only iftargetEdges
given is a negative number.seed
- The seed to feed to the random number generator.
-
DirectedScaleFreeGraphGenerator
public DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, long seed, boolean allowingMultipleEdges, boolean allowingSelfLoops)
Constructs a Generator using a seed for the random number generator and sets the two relaxation optionsallowingMultipleEdges
andallowingSelfLoops
.- Parameters:
alpha
- The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.gamma
- The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.deltaIn
- The in-degree bias used for Alpha and Beta.deltaOut
- The out-degree bias used for Beta and Gamma.targetEdges
- Target total number of edges to reach. It has a higher priority thantargetNodes
. Zero is a valid value.
If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore,targetNodes
will be considered instead. Otherwise,targetEdges
will be considered andtargetEdges
will be ignored.targetNodes
- Target number of nodes to reach. Zero is a valid value.
This parameter has lower priority thantargetEdges
and will be used only iftargetEdges
given is a negative number.seed
- The seed to feed to the random number generator.allowingMultipleEdges
- whether the generator allows multiple parallel edges between the same two vertices (v, w).allowingSelfLoops
- whether the generator allows self loops from the a vertex to itself.
-
DirectedScaleFreeGraphGenerator
public DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, java.util.Random rng)
Construct a new generator using the provided random number generator.- Parameters:
alpha
- The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.gamma
- The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.deltaIn
- The in-degree bias used for Alpha and Beta.deltaOut
- The out-degree bias used for Beta and Gamma.targetEdges
- Target total number of edges to reach. It has a higher priority thantargetNodes
. Zero is a valid value.
If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore,targetNodes
will be considered instead. Otherwise,targetEdges
will be considered andtargetEdges
will be ignored.targetNodes
- Target number of nodes to reach. Zero is a valid value.
This parameter has lower priority thantargetEdges
and will be used only iftargetEdges
given is a negative number.rng
- TheRandom
object to use.
-
DirectedScaleFreeGraphGenerator
public DirectedScaleFreeGraphGenerator(float alpha, float gamma, float deltaIn, float deltaOut, int targetEdges, int targetNodes, java.util.Random rng, boolean allowingMultipleEdges, boolean allowingSelfLoops)
Construct a new generator using the provided random number generator and sets the two relaxation optionsallowingMultipleEdges
andallowingSelfLoops
.- Parameters:
alpha
- The probability that the new edge is from a new vertex v to an existing vertex w, where w is chosen according to d_in + delta_in.gamma
- The probability that the new edge is from an existing vertex v to a new vertex w, where v is chosen according to d_out + delta_out.deltaIn
- The in-degree bias used for Alpha and Beta.deltaOut
- The out-degree bias used for Beta and Gamma.targetEdges
- Target total number of edges to reach. It has a higher priority thantargetNodes
. Zero is a valid value.
If negative number, the user does not care about the total number of edges and is interested only in the number of nodes, therefore,targetNodes
will be considered instead. Otherwise,targetEdges
will be considered andtargetEdges
will be ignored.targetNodes
- Target number of nodes to reach. Zero is a valid value.
This parameter has lower priority thantargetEdges
and will be used only iftargetEdges
given is a negative number.rng
- TheRandom
object to use.allowingMultipleEdges
- whether the generator allows multiple parallel edges between the same two vertices (v, w).allowingSelfLoops
- whether the generator allows self loops from the a vertex to itself.
-
-
Method Detail
-
generateGraph
public void generateGraph(Graph<V,E> target, java.util.Map<java.lang.String,V> resultMap)
Generates an instance of theGraph
.- Specified by:
generateGraph
in interfaceGraphGenerator<V,E,V>
- Parameters:
target
- the target graphresultMap
- not used by this generator, can be null- Throws:
TooManyFailuresException
- When the method failsmaxFailures
times to add a new edge to the growing graph.java.lang.IllegalArgumentException
- When the graph does not support Multiple edges or self loop while the generator does.
-
pickAVertex
private V pickAVertex(Graph<V,E> target, java.util.Set<V> allNewNodes, java.util.Set<E> allNewEdgesSet, DirectedScaleFreeGraphGenerator.Direction direction, float bias)
Select a vertex from the currently available vertices, using the passed bias.- Parameters:
target
- The target graphallNewNodes
- All (new) nodes in the target graphallNewEdgesSet
- All (new) edges in the target graphdirection
-DirectedScaleFreeGraphGenerator.Direction.IN
for inDegree orDirectedScaleFreeGraphGenerator.Direction.IN
for outDegreebias
- deltaIn or deltaOut value according to #directioIn- Returns:
- the selected node.
-
getMaxFailures
public int getMaxFailures()
Returns the maximum allowed number of consecutive failed attempts to add an edge.- Returns:
- maxFailure field.
-
setMaxFailures
public void setMaxFailures(int maxFailures)
Sets the maximum allowed number of consecutive failed attempts to add an edge (must be non negative).- Parameters:
maxFailures
- Maximum allowed (non negative) number of consecutive failed attempts to add an edge.
-
isAllowingMultipleEdges
public boolean isAllowingMultipleEdges()
Returns whether the generated graph may contain multiple (parallel) edges between the same two vertices.- Returns:
- whether the generated graph may contain multiple (parallel) edges between the same two vertices
-
setAllowingMultipleEdges
public void setAllowingMultipleEdges(boolean allowingMultipleEdges)
Sets whether the generated graph may contain multiple (parallel) edges between the same two vertices- Parameters:
allowingMultipleEdges
- whether the generated graph may contain multiple (parallel) edges between the same two vertices
-
isAllowingSelfLoops
public boolean isAllowingSelfLoops()
Returns whether the generated graph may contain multiple (parallel) edges between the same two vertices- Returns:
- whether the generated graph many contain multiple (parallel) edges between the same two vertices
-
setAllowingSelfLoops
public void setAllowingSelfLoops(boolean allowingSelfLoops)
Sets whether the generated graph may contain multiple (parallel) edges between the same two vertices- Parameters:
allowingSelfLoops
- whether the generated graph many contain multiple (parallel) edges between the same two vertices
-
-