module Make:

Basic operations over graphs

type

g

val transitive_closure : `?reflexive:bool -> g -> g`

`transitive_closure ?reflexive g`

returns the transitive closure
of `g`

(as a new graph). Loops (i.e. edges from a vertex to itself)
are added only if `reflexive`

is `true`

(default is `false`

).

val add_transitive_closure : `?reflexive:bool -> g -> g`

`add_transitive_closure ?reflexive g`

replaces `g`

by its
transitive closure. Meaningless for persistent implementations
(then acts as `transitive_closure`

).

val transitive_reduction : `?reflexive:bool -> g -> g`

`transitive_reduction ?reflexive g`

returns the transitive reduction
of `g`

(as a new graph). Loops (i.e. edges from a vertex to itself)
are removed only if `reflexive`

is `true`

(default is `false`

).

val replace_by_transitive_reduction : `?reflexive:bool -> g -> g`

`replace_by_transitive_reduction ?reflexive g`

replaces `g`

by its
transitive reduction. Meaningless for persistent implementations
(then acts as `transitive_reduction`

).

val mirror : `g -> g`

`mirror g`

returns a new graph which is the mirror image of `g`

:
each edge from `u`

to `v`

has been replaced by an edge from `v`

to `u`

.
For undirected graphs, it simply returns `g`

.
Note: Vertices are shared between `g`

and `mirror g`

; you may need to
make a copy of `g`

before using `mirror`

val complement : `g -> g`

`complement g`

returns a new graph which is the complement of `g`

:
each edge present in `g`

is not present in the resulting graph and
vice-versa. Edges of the returned graph are unlabeled.

val intersect : `g -> g -> g`

`intersect g1 g2`

returns a new graph which is the intersection of `g1`

and `g2`

: each vertex and edge present in `g1`

*and* `g2`

is present
in the resulting graph.

val union : `g -> g -> g`

`union g1 g2`

returns a new graph which is the union of `g1`

and `g2`

:
each vertex and edge present in `g1`

*or* `g2`

is present in the
resulting graph.