Module Merge.P

If no element of vl belongs to g then merge_vertex g (v::vl) is the graph g. Otherwise the collection of vertices of merge_vertex g (v::vl) is the collection of vertices of g from which all the elements of vl were removed and to which v was added. Any edge of merge_vertex g (v::vl) is an edge of g whose source (destination) was changed to v if it belongs to vl. The function merge_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 in merge_vertex g v::vl are exactly the ones appearing in g.

If no element of el belongs to g then merge_edges_e g (e::el) is the graph g. Otherwise the collection of vertices of merge_edges_e g (e::el) is precisely the collection of vertices of g from which the sources and the destinations of all the elements of el were removed and to which the vertices v and w were added. If dst was provided then v is src otherwise it is the source of e. If dst was provided then w is y otherwise it is the destination of e. The collection of edges of merge_edges_e g e::el is precisely the collection of edges of g from which all the elements of el were removed and to which an edge from v to w sharing the label of e was added; the edges of g being understood up to the fact their source and destination were updated. Note v=w if and only if the source of some element of el matches the destination of some element of el (possibly the same).

The graph merge_edges_with_label ?src ?tgt ?label g l is the graph merge_edges_e ?src ?dst g el with el being the list of all edges of g carrying the label l. If the optional value label is provided then the edge to which all the elements of el are identified carries the label label. Otherwise it carries the label l. In particular merge_edges_with_label ?src ?tgt ?label g l is the graph g if and only if there is at most one edge of g carrying the label l.

The graph merge_isolabelled_edges g is obtained from g 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 (if g is so) or a single vertex (if g has no edge and at least one vertex) or a single vertex and a single edge (if g has both a vertex and an edge). A label is carried by some edge of merge_isolabelled_edges g if and only if it is carried by some edge of g.

A vertex v of g is called an end if every edge of g arriving to v also starts from v. It is called a strict end if no edge of g arrives to it. The graph merge_ends g is the graph merge_vertex vl where vl is the list of (strict) ends of g. The vertex substituted to the ends can be specified.

A vertex v of g is called a start if every edge of g starting from v also arrives to v. It is called a strict start if no edge of g starts from it. The graph merge_starts g is the graph merge_vertex vl where vl is the list of (strict) starts of g. The vertex substituted to the starts can be specified.

The vertex of every strongly connected component are identified. If the option loop_killer is set to true then all the edges between identified vertices are removed. The option specified_vertex allows to choose the vertex that replaces the elements of a strongly connected component.