Module Graph

module Graph: sig .. end

Graph operations. This module is similar to the graph library module common in Prolog systems.

The P-representation of a graph is a list of (from, to) vertex pairs, where the pairs can be in any old order.

The S-representation of a graph is a list of (vertex, neighbours) pairs, where the pairs are ordered according to their vertex and the neighbours of each vertex are also orderered.

Structural equality (i.e. =) and Pervasives.compare are used for identity and comparison of vertices.

type 'a p_graph = ('a * 'a) list

Graphs in P-representation.

type 'a s_graph = ('a * 'a list) list

Graphs in S-representation.

val p_to_s_graph : 'a p_graph -> 'a s_graph

Return the S-graph representation of the given P-graph.

val s_to_p_graph : 'a s_graph -> 'a p_graph

Return a P-graph representation of the given S-graph.

val p_transpose : 'a p_graph -> 'a p_graph

Return the transposed P-graph.

val warshall : 'a s_graph -> 'a s_graph

Returns the transitive closure of the given S-graph as S-graph.

val top_sort : 'a s_graph -> 'a list

Returns a list of vertices of the given S-graph in topological ordering. Raises Not_found if the graph is cyclic.