module Make: functor (
B
:
Builder.INT
) ->
S
with type graph = B.G.t
and type vertex = B.G.V.t
and type edge_label = B.G.E.label
Random graphs
type
graph
type
vertex
type
edge_label
val graph : ?loops:bool -> v:int -> e:int -> unit -> graph
graph v e
generates a random graph with exactly v
vertices
and e
edges. Vertices are labeled with 0
... v-1
.
The boolean loops
indicates whether loops are allowed;
default value is no loop (false
).
Raises Invalid_argument
if e
exceeds the maximal number of edges.
val labeled : (vertex -> vertex -> edge_label) ->
?loops:bool -> v:int -> e:int -> unit -> graph
labeled f
is similar to graph
except that edges are labeled
using function f
.
Raises Invalid_argument
if there are too many edges.
The two functions above actually make a choice between two
different implementations according to the ratio e/(v*v).
When this ratio is small, random_few_edges
is selected;
otherwise random_many_edges
is selected.
val random_few_edges : loops:bool -> v:int -> e:int -> graph
val random_many_edges : loops:bool -> v:int -> e:int -> graph
val gnp : ?loops:bool -> v:int -> prob:float -> unit -> graph
random graph using the G(n,p) model.
gnp v prob
generates a random graph with exactly v
vertices
and where each edge is selected with probability prob
val gnp_labeled : (vertex -> vertex -> edge_label) ->
?loops:bool -> v:int -> prob:float -> unit -> graph
gnp_labeled add_edge v e
is similar to gnp
except that edges
are labeled using function f
.