package ocamlgraph

  1. Overview
  2. Docs
package ocamlgraph
Legend:
Library
Module
Module type
Parameter
Class
Class type

Undirected imperative graphs with edges and vertices labeled with integer.

Graph structure

type t

abstract type of graphs

module V : sig ... end

Vertices

type vertex = V.t
module E : sig ... end

Edges

type edge = E.t
val is_directed : bool

is this an implementation of directed graphs?

Graph constructors and destructors

val create : ?size:int -> unit -> t

Return an empty graph. Optionally, a size can be given, which should be on the order of the expected number of vertices that will be in the graph (for hash tables-based implementations). The graph grows as needed, so size is just an initial guess.

val clear : t -> unit

Remove all vertices and edges from the given graph.

  • since ocamlgraph 1.4
val copy : t -> t

copy g returns a copy of g. Vertices and edges (and eventually marks, see module Mark) are duplicated.

val add_vertex : t -> V.t -> unit

add_vertex g v adds the vertex v from the graph g. Do nothing if v is already in g.

val remove_vertex : t -> V.t -> unit

remove g v removes the vertex v from the graph g (and all the edges going from v in g). Do nothing if v is not in g.

val add_edge : t -> V.t -> V.t -> unit

add_edge g v1 v2 adds an edge from the vertex v1 to the vertex v2 in the graph g. Add also v1 (resp. v2) in g if v1 (resp. v2) is not in g. Do nothing if this edge is already in g.

val add_edge_e : t -> E.t -> unit

add_edge_e g e adds the edge e in the graph g. Add also E.src e (resp. E.dst e) in g if E.src e (resp. E.dst e) is not in g. Do nothing if e is already in g.

val remove_edge : t -> V.t -> V.t -> unit

remove_edge g v1 v2 removes the edge going from v1 to v2 from the graph g. Do nothing if this edge is not in g.

  • raises Invalid_argument

    if v1 or v2 are not in g.

val remove_edge_e : t -> E.t -> unit

remove_edge_e g e removes the edge e from the graph g. Do nothing if e is not in g.

  • raises Invalid_argument

    if E.src e or E.dst e are not in g.

module Mark : sig ... end

Vertices contains integers marks, which can be set or used by some algorithms (see for instance module Marking below)

Size functions

val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int

Degree of a vertex

val out_degree : t -> V.t -> int

out_degree g v returns the out-degree of v in g.

  • raises Invalid_argument

    if v is not in g.

val in_degree : t -> V.t -> int

in_degree g v returns the in-degree of v in g.

  • raises Invalid_argument

    if v is not in g.

Membership functions

val mem_vertex : t -> V.t -> bool
val mem_edge : t -> V.t -> V.t -> bool
val mem_edge_e : t -> E.t -> bool
val find_edge : t -> V.t -> V.t -> E.t
val find_all_edges : t -> V.t -> V.t -> E.t list

Successors and predecessors of a vertex

val succ : t -> V.t -> V.t list

succ g v returns the successors of v in g.

  • raises Invalid_argument

    if v is not in g.

val pred : t -> V.t -> V.t list

pred g v returns the predecessors of v in g.

  • raises Invalid_argument

    if v is not in g.

Labeled edges going from/to a vertex

val succ_e : t -> V.t -> E.t list

succ_e g v returns the edges going from v in g.

  • raises Invalid_argument

    if v is not in g.

val pred_e : t -> V.t -> E.t list

pred_e g v returns the edges going to v in g.

  • raises Invalid_argument

    if v is not in g.

Graph iterators

iter/fold on all vertices/edges of a graph

val iter_vertex : (V.t -> unit) -> t -> unit
val iter_edges : (V.t -> V.t -> unit) -> t -> unit
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
val fold_edges : (V.t -> V.t -> 'a -> 'a) -> t -> 'a -> 'a
val map_vertex : (V.t -> V.t) -> t -> t

map iterator on vertex

iter/fold on all labeled edges of a graph

val iter_edges_e : (E.t -> unit) -> t -> unit
val fold_edges_e : (E.t -> 'a -> 'a) -> t -> 'a -> 'a

Vertex iterators

Each iterator iterator f v g iters f to the successors/predecessors of v in the graph g and raises Invalid_argument if v is not in g.

iter/fold on all successors/predecessors of a vertex.

val iter_succ : (V.t -> unit) -> t -> V.t -> unit
val iter_pred : (V.t -> unit) -> t -> V.t -> unit
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
val fold_pred : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a

iter/fold on all edges going from/to a vertex.

val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit
val fold_succ_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
val iter_pred_e : (E.t -> unit) -> t -> V.t -> unit
val fold_pred_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a

Basic operations

val find_vertex : t -> int -> V.t

vertex g i returns a vertex of label i in g. The behaviour is unspecified if g has several vertices with label i. Note: this function is inefficient (linear in the number of vertices); you should better keep the vertices as long as you create them.

val transitive_closure : ?reflexive:bool -> t -> t

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 -> t -> t

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 -> t -> t

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 -> t -> t

replace_by_transitive_reduction ?reflexive g replaces g by its transitive reduction. Meaningless for persistent implementations (then acts as transitive_reduction).

val mirror : t -> t

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 a copy of g.

val complement : t -> t

complement g builds 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 : t -> t -> t

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 : t -> t -> t

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.

Traversal

module Dfs : sig ... end

Depth-first search

module Bfs : sig ... end

Breadth-first search

module Marking : sig ... end

Graph traversal with marking

module Coloring : sig ... end

Coloring

Graph generators

module Classic : sig ... end

Classic graphs

module Rand : sig ... end

Random graphs

module Components : sig ... end

Strongly connected components

Classical algorithms

val shortest_path : t -> V.t -> V.t -> E.t list * int

Dijkstra's shortest path algorithm. Weights are the labels.

val ford_fulkerson : t -> V.t -> V.t -> (E.t -> int) * int

Ford Fulkerson maximum flow algorithm

val goldberg_tarjan : t -> V.t -> V.t -> (E.t -> int) * int

Goldberg-Tarjan maximum flow algorithm

val bellman_ford : t -> V.t -> E.t list

bellman_ford g v finds a negative cycle from v, and returns it, or raises Not_found if there is no such cycle

module PathCheck : sig ... end

Path checking

module Topological : sig ... end

Topological order

val spanningtree : t -> E.t list

Kruskal algorithm

Input / Output

val dot_output : t -> string -> unit

DOT output in a file

val display_with_gv : t -> unit

Displays the given graph using the external tools "dot" and "gv" and returns when gv's window is closed

val parse_gml_file : string -> t
val parse_dot_file : string -> t
val print_gml : Format.formatter -> t -> unit
val print_gml_file : t -> string -> unit
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct