Changing the label of a vertex in an imperative graph?

I'm trying to create a graph over sets of symbols, intended to be merged later.

I figured you would be able to modify the label value, hence I have

module G = Imperative.Graph.Abstract (struct
  type t = S.SS.t
end)

where SS is made with Set.Make(...).

I initialize all vertices with G.V.create (S.SS.add s S.SS.empty) hoping to map them or reassign whichever Set they are assigned, but I can't find any function for this, which has got me worried I might've misunderstood something..

Is it not possible to change the label after creation, as in something like

let v1 = G.V.create (S.SS.add s1 S.SS.empty)
G.V.label := S.SS.add s2 (G.V.label v1);

I always expected to be able to change it like so, hence I wrote the Display module

module Display = struct
  include G
  let vertex_name v =
    "\"{ " ^ Ll.mapcat ", " S.name (V.label v |> S.SS.elements) ^ " }\""
  (* .. *)
end

if this is not the case how else are you meant to modify the label associated with some vertex? Are we talking separate state with the label being assigned to indices or something like that?

As a matter of fact now that I think about it, how would I even include external state in a Display module? If I have a collection of strings kept separately from the vertex (i.e. not reachable in a call to vertex_name), how would I include them in the display!?

Hi @s1gtrap , Apologies for the late answer. Indeed, vertex labels are immutable. The simplest solution to your problem is to have a table on the side mapping vertices to whatever information you need. In OCamlGraph, the submodule V is always a HashedType, so this is as simple as

module H = Hashtbl.Make(G.V)

All algorithms in OCamlGraph are implemented this way. (Here is an example.) Such a module H could be included inside your Display module for instance.

Notes: For Concrete implementations, vertices are directly used as keys in (internal) hash tables, so it would not be possible to make them mutable. For Abstract implementations, however, the vertices are mutable (they carry mutable integer marks), so the labels could be mutable as well. That would be a matter of making field label mutable in this type. I don't think we'll make such a change in a near future, but thanks for pointing this out.

backtracking / ocamlgraph

Changing the label of a vertex in an imperative graph? #139