Module Graph__Merge.P
Extension for the module G
.
Parameters
G : Graph.Sig.P
Signature
val merge_vertex : graph -> vertex list -> graph
If no element of
vl
belongs tog
thenmerge_vertex g (v::vl)
is the graphg
. Otherwise the collection of vertices ofmerge_vertex g (v::vl)
is the collection of vertices ofg
from which all the elements ofvl
were removed and to whichv
was added. Any edge ofmerge_vertex g (v::vl)
is an edge ofg
whose source (destination) was changed tov
if it belongs tovl
. The functionmerge_vertex
always returns a graph with a smaller collection of vertices and a smaller collection of edges (in the weak sense). However the labels appearing inmerge_vertex g v::vl
are exactly the ones appearing ing
.
val merge_edges_e : ?src:vertex -> ?dst:vertex -> graph -> edge list -> graph
If no element of
el
belongs tog
thenmerge_edges_e g (e::el)
is the graphg
. Otherwise the collection of vertices ofmerge_edges_e g (e::el)
is precisely the collection of vertices ofg
from which the sources and the destinations of all the elements ofel
were removed and to which the verticesv
andw
were added. Ifdst
was provided thenv
issrc
otherwise it is the source ofe
. Ifdst
was provided thenw
isy
otherwise it is the destination ofe
. The collection of edges ofmerge_edges_e g e::el
is precisely the collection of edges ofg
from which all the elements ofel
were removed and to which an edge fromv
tow
sharing the label ofe
was added; the edges ofg
being understood up to the fact their source and destination were updated. Notev=w
if and only if the source of some element ofel
matches the destination of some element ofel
(possibly the same).
val merge_edges_with_label : ?src:vertex -> ?dst:vertex -> ?label:edge_label -> graph -> edge_label -> graph
The graph
merge_edges_with_label ?src ?tgt ?label g l
is the graphmerge_edges_e ?src ?dst g el
withel
being the list of all edges ofg
carrying the labell
. If the optional valuelabel
is provided then the edge to which all the elements ofel
are identified carries the labellabel
. Otherwise it carries the labell
. In particularmerge_edges_with_label ?src ?tgt ?label g l
is the graphg
if and only if there is at most one edge ofg
carrying the labell
.
val merge_isolabelled_edges : graph -> graph
The graph
merge_isolabelled_edges g
is obtained fromg
by identifying two vertices when they are the sources (destinations) of two edges sharing the same label. Therefore two distinct edges of the returned graph cannot carry the same label. In particular if all the edges share the same label then the returned graph is either empty (ifg
is so) or a single vertex (ifg
has no edge and at least one vertex) or a single vertex and a single edge (ifg
has both a vertex and an edge). A label is carried by some edge ofmerge_isolabelled_edges g
if and only if it is carried by some edge ofg
.
val merge_ends : ?strict:bool -> ?specified_vertex:vertex -> graph -> graph
A vertex
v
ofg
is called an end if every edge ofg
arriving tov
also starts fromv
. It is called a strict end if no edge ofg
arrives to it. The graphmerge_ends g
is the graphmerge_vertex vl
wherevl
is the list of (strict) ends ofg
. The vertex substituted to the ends can be specified.
val merge_starts : ?strict:bool -> ?specified_vertex:vertex -> graph -> graph
A vertex
v
ofg
is called a start if every edge ofg
starting fromv
also arrives tov
. It is called a strict start if no edge ofg
starts from it. The graphmerge_starts g
is the graphmerge_vertex vl
wherevl
is the list of (strict) starts ofg
. The vertex substituted to the starts can be specified.
val merge_scc : ?loop_killer:bool -> ?specified_vertex:(vertex list -> vertex) -> graph -> graph
The vertex of every strongly connected component are identified. If the option
loop_killer
is set totrue
then all the edges between identified vertices are removed. The optionspecified_vertex
allows to choose the vertex that replaces the elements of a strongly connected component.