package ocamlgraph

  1. Overview
  2. Docs
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Pack.GraphSource

Undirected imperative graphs with edges and vertices labeled with integer.

Graph structure

Sourcetype t

abstract type of graphs

module V : sig ... end

Vertices

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

Edges

Sourcetype edge = E.t
Sourceval is_directed : bool

is this an implementation of directed graphs?

Graph constructors and destructors

Sourceval 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.

Sourceval clear : t -> unit

Remove all vertices and edges from the given graph.

  • since ocamlgraph 1.4
Sourceval copy : t -> t

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

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourcemodule Mark : sig ... end

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

Size functions

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

Degree of a vertex

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

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

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

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

Membership functions

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

Successors and predecessors of a vertex

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

succ g v returns the successors of v in g.

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

pred g v returns the predecessors of v in g.

Labeled edges going from/to a vertex

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

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

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

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

Graph iterators

iter/fold on all vertices/edges of a graph

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

map iterator on vertex

iter/fold on all labeled edges of a graph

Sourceval iter_edges_e : (E.t -> unit) -> t -> unit
Sourceval 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.

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

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

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

Basic operations

Sourceval 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.

Sourceval 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).

Sourceval 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).

Sourceval 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).

Sourceval 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).

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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

Sourcemodule Dfs : sig ... end

Depth-first search

Sourcemodule Bfs : sig ... end

Breadth-first search

Sourcemodule Marking : sig ... end

Graph traversal with marking

Sourcemodule Coloring : sig ... end

Coloring

Graph generators

Sourcemodule Classic : sig ... end

Classic graphs

Sourcemodule Rand : sig ... end

Random graphs

Sourcemodule Components : sig ... end

Strongly connected components

Classical algorithms

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

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

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

Ford Fulkerson maximum flow algorithm

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

Goldberg-Tarjan maximum flow algorithm

Sourceval 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

Sourcemodule PathCheck : sig ... end

Path checking

Sourcemodule Topological : sig ... end

Topological order

Sourceval spanningtree : t -> E.t list

Kruskal algorithm

Input / Output

Sourceval dot_output : t -> string -> unit

DOT output in a file

Sourceval display_with_gv : t -> unit

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

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

Innovation. Community. Security.