Package org.jgrapht.generate
Class RandomGraphGenerator.DefaultEdgeTopologyFactory<VV,EE>
java.lang.Object
org.jgrapht.generate.RandomGraphGenerator.DefaultEdgeTopologyFactory<VV,EE>
- All Implemented Interfaces:
RandomGraphGenerator.EdgeTopologyFactory<VV,
EE>
- Enclosing class:
RandomGraphGenerator<V,
E>
public class RandomGraphGenerator.DefaultEdgeTopologyFactory<VV,EE>
extends Object
implements RandomGraphGenerator.EdgeTopologyFactory<VV,EE>
Default implementation of the EdgeTopologyFactory interface. randomly
chooses an edge and tries to add it. If the add fails from any reason
(like: self edge / multiple edges in unpermitted graph type) it will just
choose another and try again. Performance:
when the number of possible edges becomes slim , this class will have
a very poor performance , cause it will not use gready methods to choose
them. for example : In simple graph , if #V = N (#x = number Of x) and we
want full mesh #edges= N*(N-1)/2 , the first added edges will do so
quickly (O(1) , the last will take O(N^2). So , do not use it in this
kind of graphs.
If the numberOfEdges is bigger than what the graph can add, there
will be an infinite loop here. It is not tested.
- Since:
- Aug 6, 2005
- Author:
- Assaf
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
createEdges
(Graph<VV, EE> targetGraph, Map<Integer, VV> orderToVertexMap, int numberOfEdges, Random randomizer) Two different calls to the createEdges() with the same parameters must result in the generation of the same.int
getMaxEdgesForVertexNum
(Graph<VV, EE> targetGraph) Return max edges for that graph.boolean
isNumberOfEdgesValid
(Graph<VV, EE> targetGraph, int numberOfEdges) checks if the numOfEdges is smaller than the Max edges according to the following table:
-
Constructor Details
-
DefaultEdgeTopologyFactory
public DefaultEdgeTopologyFactory()
-
-
Method Details
-
createEdges
public void createEdges(Graph<VV, EE> targetGraph, Map<Integer, VV> orderToVertexMap, int numberOfEdges, Random randomizer) Description copied from interface:RandomGraphGenerator.EdgeTopologyFactory
Two different calls to the createEdges() with the same parameters must result in the generation of the same. But if the randomizer is different, it should, usually, create different edge topology.- Specified by:
createEdges
in interfaceRandomGraphGenerator.EdgeTopologyFactory<VV,
EE> - Parameters:
targetGraph
- - guranteed to start with zero edges.orderToVertexMap
- - key=Integer of vertex order . between zero to numOfVertexes (exclusive). value = vertex from the graph. unique.numberOfEdges
- - to create in the graphrandomizer
-
-
isNumberOfEdgesValid
checks if the numOfEdges is smaller than the Max edges according to the following table:Graph Type Directed / UnDirected multiple edges loops Max Edges SimpleGraph UnDirected - - N(N-1)/2 Multigraph UnDirected + - Infinite Pseudograph UnDirected + + Infinite SimpleDirectedGraph Directed - - N (N-1) DefaultDirectedGraph Directed - + N*(N-1)+ N = N^2 DirectedMultigraph Directed + + Infinite - Specified by:
isNumberOfEdgesValid
in interfaceRandomGraphGenerator.EdgeTopologyFactory<VV,
EE> - Parameters:
targetGraph
- guranteed to start with zero edges.numberOfEdges
-- See Also:
-
getMaxEdgesForVertexNum
Return max edges for that graph. If it is infinite return -1 instead.
-