S (kind2dev@731decdf5fb1.Graph.S)

type vertex

The vertex type

type edge

The edge type to represent line between two vertices

val mk_edge : vertex -> vertex -> edge

Make an edge from two vertices

val get_source_vertex : edge -> vertex

Get the source vertex from an edge

val is_vertex_source : edge -> vertex -> bool

Checks if the vertex is the source vertex

val get_target_vertex : edge -> vertex

Get the target vertex from an edge

val is_vertex_target : edge -> vertex -> bool

Checks if the vertex is the target vertex

type vertices

Set of vertices

type edges

Set of edges

type t

The graph type

val empty : t

The empty graph

val is_empty : t -> bool

Check if the graph is empty

val singleton : vertex -> t

returns a singleton graph

val is_singleton : t -> bool

returns true if the graph has only one vertex

val add_vertex : t -> vertex -> t

Add a vertex to a graph

val mem_vertex : t -> vertex -> bool

returns true if the vertex is in the graph

val has_edge : t -> vertex -> vertex -> bool

Returns true if there is an edge from the first vertex to the second vertex

val get_vertices : t -> vertices

get all vertices in the graph

val to_vertex_list : vertices -> vertex list

Returns a list of vertex

val from_vertex_list : vertex list -> vertices

Returns a set of vertices from a list of vertex

val get_edges : t -> edges

get all edges in the graph

val to_edge_list : edges -> (vertex * vertex) list

Returns a list of edges in the form (source, target)

val add_edge : t -> edge -> t

Add an edge to a graph

val remove_vertex : t -> vertex -> t

Remove the vertex and its associated edges from the graph

val remove_vertices : t -> vertex list -> t

Remove the vertex list and its associated edges from the graph

val remove_edge : t -> edge -> t

Remove an edge from a graph

val connect : t -> vertex -> t

Connect vertex to all the other vertices in the given graph

val is_point_graph : t -> bool

Returns true if the graph has no edges

val union : t -> t -> t

Unions two graphs

val sub_graph : t -> vertices -> t

Gets a subgraph along with appropriate edges of given graph from a given set of vertices

val extract_cycle : t -> vertex -> vertex list option

Returns Some list of vertices that form a cycle starting from the given vertex, or None if no such cycle exists

val children : t -> vertex -> vertex list

Gets the immediate children of a vertex, those reachable by one edge

val map : (vertex -> vertex) -> t -> t

Maps the vertices using the argument mapping, the structure should remain intact.

Caution: The callee function (or the programmer) is supposed to make sure this is an injective mapping to make sure that the graph structure is preserved.

val non_target_vertices : t -> vertices

Returns a list of all vertices that have no incoming edge

exception CyclicGraphException of vertex list

The exception raised when topological sort is tried on cyclic graph

Graph Traversals

val topological_sort : t -> vertex list

Computes a topological ordering of vertices * or throws an CyclicGraphException if the graph is cyclic. * Implementation of this function is based on Kahn's algorithm

val get_sccs : t -> vertices list

Computes the strongly connected components (SCCs) of the graph. * It returns the list of SCCs in topological order. * Implementation of this function is based on Tarjan's algorithm

module VMap : sig ... end

val memoized_reachable : vertices VMap.t Stdlib.ref -> t -> vertex -> vertices

Finds all the vertices that are reachable from the given vertex in a graph

Pretty Printers

val pp_print_vertex : Stdlib.Format.formatter -> vertex -> unit

Pretty print a vertex

val pp_print_vertices : Stdlib.Format.formatter -> vertices -> unit

Pretty print all the vertices

val pp_print_edge : Stdlib.Format.formatter -> edge -> unit

Pretty print one edge

val pp_print_edges : Stdlib.Format.formatter -> edges -> unit

Pretty print all the edges

val pp_print_graph : Stdlib.Format.formatter -> t -> unit

Pretty print the graph i.e. its vertices and its edges.