Version & licenses
Creative Commons License

Graph.S

Guyslain Naves

  2. module type S =
  3. sig


  6. (**all functions may raise Not_found if called with incorrect arguments *)

  8. type edge
  9. type vertex
  10. type graph

  12. (** Ordering on vertices and edges, also used for test for equality. *)
  13. val compare_vertex : vertex -> vertex -> int
  14. val compare_edge : edge -> edge -> int

  16. (** The graph without vertex *)
  17. val empty : graph

  19. (** [add_vertex graph v]: a graph obtained by adding an isolated vertex [v] to [graph] *)
  20. (** raise Invalid_arg if [v] is already in [graph] *)
  21. val add_vertex : graph -> vertex -> graph

  23. (** [add_edge graph u v e]: a graph obtained by adding an edge [e] between [u] and [v] in [graph] *)
  24. (** raise Invalid_arg if [e] is already in [graph] *)
  25. (** raise Not_found if [u] and [v] are not vertices of [graph] *)
  26. val add_edge : graph -> vertex -> vertex -> edge -> graph

  28. (** [remove_vertex graph v]: a graph obtained by removing [v] from [graph],
  29. and all the incident arcs to [v] in [graph]
  30. *)
  31. val remove_vertex : graph -> vertex -> graph

  33. (** [remove_edge graph edge]: a graph obtained by deleting [edge] in [graph]. *)
  34. val remove_edge : graph -> edge -> graph


  37. (** modules for set of vertices and edges*)
  38. module V : Set.S with type elt = vertex
  39. module E : Set.S with type elt = edge

  41. (** modules for partial function on vertices and edges *)
  42. module VMap : Map.S with type key = vertex
  43. module EMap : Map.S with type key = edge

  45. (** [v graph] is the vertex set of [graph] *)
  46. val v : graph -> V.t

  48. (** [e graph] is the edge set of [graph] *)
  49. val e : graph -> E.t


  52. (** [tail graph edge] is the first vertex of the arc [edge] in [graph] *)
  53. val tail : graph -> edge -> vertex

  55. (** [head graph edge] is the second vertex of the arc [edge] in [graph] *)
  56. val head : graph -> edge -> vertex

  58. (** [extremities graph edge] is the couple of vertices of [edge] in [graph] *)
  59. val extremities : graph -> edge -> vertex * vertex

  61. (** [opposite graph e v], where [v] is an extremity of [e], is the other extremity of [e]
  62. ([v] if [e] is a loop) *)
  63. val opposite : graph -> edge -> vertex -> vertex


  66. (** [delta_in graph v] is the set of arcs entering [v] in [graph] *)
  67. val delta_in : graph -> vertex -> E.t

  69. (** [delta_out graph v] is the set of arcs leaving [v] in [graph] *)
  70. val delta_out : graph -> vertex -> E.t

  72. (** [delta graph v] is the set of arcs incident to [v] in [graph] *)
  73. val delta : graph -> vertex -> E.t

  75. (** [in_neighbour graph v] is the set of vertices with an arc to [v] in [graph] *)
  76. val in_neighbour : graph -> vertex -> V.t

  78. (** [out_neighbour graph v] is the set of vertices with an arc from [v] in [graph] *)
  79. val out_neighbour : graph -> vertex -> V.t

  81. (** [neighbour graph v] is the set of vertices adjacent to [v] in [graph] *)
  82. val neighbour : graph -> vertex -> V.t


  85. (** [adjacent graph u v] checks whether [u] and [v] are adjacent in [graph] *)
  86. val adjacent : graph -> vertex -> vertex -> bool

  88. (** [edge graph u v] is an arbitrary edge with endpoints [u] and [v] in [graph] *)
  89. (** raise Not_found if none exists *)
  90. val edge : graph -> vertex -> vertex -> edge


  93. (** [arcs graph u v] is the set of arcs from [u] to [v] in [graph] *)
  94. val arcs : graph -> vertex -> vertex -> E.t

  96. (** [edges graph u v] is the set of edges with endpoints [u] and [v] in [graph] *)
  97. val edges : graph -> vertex -> vertex -> E.t

  99. (** [induced graph vertex_set] is the graph induced by [vertex_set] in [graph] *)
  100. val induced : graph -> V.t -> graph

  102. (** [subgraph graph edge_set] is the subgraph of [graph] with edge set [edge_set] *)
  103. val subgraph : graph -> E.t -> graph

  105. (** [contract graph ?v e] is the graph obtained by contracting edge [e] in [graph].
  106. The optional argument [v] is the vertex obtained by this contraction.
  107. By default, it is one of the endpoints of [e] in [graph]
  108. *)
  109. val contract : graph -> ?w:vertex -> edge -> graph

  111. (** [identify graph ?v vertex_set] is the graph obtained from [graph]
  112. by identifying all the vertices in [vertex_set].
  113. It may have multiple edges or loops.
  114. The optional argument is the vertex corresponding to the identification in the result graph.
  115. By default, it is a vertex of [vertex_set].
  116. *)
  117. val identify : graph -> ?w:vertex -> V.t -> graph

  119. (** [simplify graph vertex] is the graph obtained by removing all the loops at [vertex],
  120. and keeping only one edge of every set of parallel edges incident to [vertex] in [graph].
  121. *)
  122. val simplify : graph -> vertex -> graph

  124. (** same as simplify, but keeps a copy of an arc in both direction if possible *)
  125. val directed_simplify : graph -> vertex -> graph


  128. (** additional modules for vertices and edges manipulation *)
  129. module VFun : Cmap.CMAP with type elt = vertex
  130. module VCount : Counter.COUNTER with type elt = vertex
  131. module EFun : Cmap.CMAP with type elt = edge
  132. module ECount : Counter.COUNTER with type elt = edge


  135. end