bundles/menhirLib/menhir-20120123/src/breadth.mli

   1 (**************************************************************************)
   2 (*                                                                        *)
   3 (*  Menhir                                                                *)
   4 (*                                                                        *)
   5 (*  François Pottier, INRIA Rocquencourt                                  *)
   6 (*  Yann Régis-Gianas, PPS, Université Paris Diderot                      *)
   7 (*                                                                        *)
   8 (*  Copyright 2005-2008 Institut National de Recherche en Informatique    *)
   9 (*  et en Automatique. All rights reserved. This file is distributed      *)
  10 (*  under the terms of the Q Public License version 1.0, with the change  *)
  11 (*  described in file LICENSE.                                            *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* This module implements generic breadth-first search
  16    over a graph with labeled edges. *)
  17
  18 module Make (G : sig
  19
  20   (* This is the type of graph vertices. *)
  21
  22   type vertex
  23
  24   (* This is the type of graph labels. *)
  25
  26   type label
  27
  28   (* These allow marking a vertex and checking whether
  29      it is marked. *)
  30
  31   val set_mark: vertex -> Mark.t -> unit
  32   val get_mark: vertex -> Mark.t
  33
  34   (* This is an iterator over the graph's entry vertices. *)
  35
  36   val entry: (vertex -> unit) -> unit
  37
  38   (* This provides access to a vertex' successors. *)
  39
  40   val successors: (label -> vertex -> unit) -> vertex -> unit
  41
  42 end) : sig
  43
  44   (* [search f] invokes [f discovery v label v'] once for every edge
  45      from vertex [v] to vertex [v'] carrying label [label]. Vertices
  46      [v'] are presented breadth-first. The flag [discovery] tells
  47      whether the edge is a discovery edge, that is, whether it belongs
  48      to the spanning forest of shortest paths that is being built. *)
  49
  50   val search: (bool -> G.vertex -> G.label -> G.vertex -> unit) -> unit
  51
  52 end
  53