Up
# module Rand

: sig
## Random graphs

## Random planar graphs

Random graph generation.

#

module type S = sig

#

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 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`

.

end

#

module Planar : sig

#

module type S = sig

#

type graph

#

val graph : ?loops:bool -> xrange:int * int -> yrange:int * int -> prob:float -> int -> graph

`graph xrange yrange prob v`

generates a random planar graph with exactly `v`

vertices.
Vertices are labeled with integer coordinates, randomly distributed
according to `xrange`

and `yrange`

.
Edges are built as follows: the full Delaunay triangulation is
constructed and then each edge is discarded with probabiblity `prob`

(which should lie in `0..1`

). In particular `prob = 0.0`

gives the
full triangulation.
Edges are labeled with the (rounded) Euclidean distance between
the two vertices.
The boolean `loops`

indicates whether loops are allowed;
default value is no loop (`false`

).

end

end

end