backtracking / ocamlgraph

OCaml graph library

OCamlgraph

OCamlgraph is a graph library for OCaml. Its contribution is three-fold:

1. It provides an easy-to-use graph implementation together with several operations and algorithms over graphs, in Graph.Pack.Digraph. It is a reasonably efficient imperative data structure for directed graphs with vertices and edges labeled with integers.

   Have a look at this module first in order to get an overview of what this library provides. See also demo.ml.

2. Then OCamlgraph provides several other graph implementations for those not satisfied with the one above. Some are persistent (immutable) and other imperative (mutable). Some are directed and other are not. Some have labels for vertices, or labels for edges, or both. Some have abstract types for vertices. etc.

   See interface Sig for the graph signatures and modules Persistent and Imperative for the implementations.

   These implementations are written as functors: you give the types of vertices labels, edge labels, etc. and you get the data structure as a result.

3. Finally, OCamlgraph provides several classic operations and algorithms over graphs. They are also written as functors i.e. independently of the data structure for graphs. One consequence is that you can define your own data structure for graphs and yet re-use all the algorithms from this library -- you only need to provide a few operations such as iterating over all vertices, over the successors of a vertex, etc.

Documentation

https://backtracking.github.io/ocamlgraph/

Examples

You'll find examples of OCamlgraph use in subdirectory examples/ (demo.ml, demo_planar.ml, color.ml, etc.).

Bug reports

https://github.com/backtracking/ocamlgraph/issues

ocamlgraph's Issues

the opam package doesn't install the ocamldoc

it doesn't show up in ocp-browser. :(

Configuration script error when building for Windows

Configuring the build of ocamlgraph for Windows using the Cygwin environment
fails in detecting ocamlfind's presence:

$ ./configure
checking for ocamlc... ocamlc
ocaml version is 4.02.2
ocaml library path is C:/ocamlmgw/lib
checking for ocamlopt... ocamlopt
checking ocamlopt version... ok
checking for ocamlc.opt... ocamlc.opt
checking ocamlc.opt version... ok
checking for ocamlopt.opt... ocamlopt.opt
checking ocamlc.opt version... ok
checking for ocamldep... ocamldep
checking for ocamllex... ocamllex
checking for ocamllex.opt... ocamllex.opt
checking for ocamlyacc... ocamlyacc
checking for ocamldoc... ocamldoc
checking for ocamldoc.opt... ocamldoc.opt
checking for ocamlweb... true
checking for ocamlfind... ocamlfind
OCamlfind detected but disabled. Standard libraries differ:
  ocamlc: 'C:/ocamlmgw/lib'
  ocamlfind: 'C:\ocamlmgw\lib'
checking for C:/ocamlmgw/lib/lablgtk2/lablgtk.cmxa... no
checking Win32 platform... yes
configure: WARNING: lablgnomecanvas not found: the graph editor and view_graph will not be compiled
configure: creating ./config.status
config.status: creating Makefile

This behavior is due to the difference in Windows path separators that are reported by
ocamlfind and ocamlc. The build succeeds, once the test in line 2253 in ocamlgraph's
configure script is deleted.

Fixpoint computes incorrect node labelling

Hi,

The fixpoint module calculates surprising and (from my understanding) incorrect node labels.

Consider the attached example. We take the divisor graph (up to 15, but that's arbitrary) and label each node with a set of integers, which initially contains the node label. The fixpoint algorithm is then instantiated to label each node with the union of the label sets of the transitively reachable nodes (i.e., we want to compute all multiples of the node in the graph), by taking set union as the join, set equality as equaity and identity as the transfer function.

What I would expect:
The node 10 should be labelled with {10}.
The node 2 should be labelled with {2,4,6,8,10,12,14}.

What I get:
The node 10 is labelled with {10}.
The node 2 is labelled with {8, 10, 12, 14}.

Note that a significant part of 2's expected label, including the original label 2, is missing!

A similar errors manifests itself when using forward propagation.

Thanks,
Johannes

Does not compile with -static

When compiling ocamlgraph with switch 4.07.1+musl+static+flambda, I get

#=== ERROR while compiling ocamlgraph.1.8.8 ===================================#
# context     2.0.0 | linux/x86_64 | ocaml-variants.4.07.1+musl+static+flambda | https://opam.ocaml.org/#892303df
# path        ~/.opam/4.07.1+musl+static+flambda/.opam-switch/build/ocamlgraph.1.8.8
# command     /usr/bin/make
# exit-code   2
# env-file    ~/.opam/log/ocamlgraph-27696-8b47d2.env
# output-file ~/.opam/log/ocamlgraph-27696-8b47d2.out
### output ###
# [...]
# ocamlopt.opt -c -I src -I lib -for-pack Graph src/merge.ml
# ocamlopt.opt -c -I src -I lib -for-pack Graph src/mincut.ml
# ocamlopt.opt -c -I src -I lib -for-pack Graph src/clique.ml
# ocamlopt.opt -c -I src -I lib -for-pack Graph src/weakTopological.ml
# ocamlopt.opt -c -I src -I lib -for-pack Graph src/chaoticIteration.ml
# ocamlopt.opt -I src -I lib -pack -o graph.cmx src/sig.cmi src/sig_pack.cmi src/dot_ast.cmi lib/unionfind.cmx lib/heap.cmx lib/bitv.cmx lib/persistentQueue.cmx src/version.cmx src/util.cmx src/blocks.cmx src/persistent.cmx src/imperative.cmx src/delaunay.cmx src/builder.cmx src/classic.cmx src/rand.cmx src/oper.cmx src/components.cmx src/path.cmx src/nonnegative.cmx src/traverse.cmx src/colori[...]
# ocamlopt.opt -I src -I lib -a -o graph.cmxa graph.cmx
# ocamlopt.opt -I src -I lib -shared -o graph.cmxs graph.cmx
# sh: 1: shared-libs-not-available: not found
# File "caml_startup", line 1:
# Error: Error during linking
# make: *** [Makefile:104: graph.cmxs] Error 2

Switching to Dune will fix the problem automatically. :-)

`map_vertex` violates invariants if two vertices map to the same new one.

See this SCC contraction code for an example of how I ran into this.

Either the documentation surrounding map_vertex should be changed to document that it is unsafe to map vertices to the same value, or values for new vertices need to be somehow loaded in the implementation. Most likely, this would necessitate switching from a map to a fold, and essentially rebuilding the whole thing, but I suspect that the map is essentially already doing this.

build fails on 4.1 due to errors-as-warnings

WIth 4.1:

### stderr ###
File "gdir.ml", line 51, characters 30-32:
Warning 3: deprecated feature: operator (or); you should use (||) instead
File "gdir.ml", line 1:
Error: Some fatal warnings were triggered (1 occurrences)

This failed in an OPAM regression test run (OCamlPro/opam-repository#1029 for the gory details). In general, disabling errors-as-warnings in released tarballs would be helpful to keep it working with development versions of the compiler that usually introduce new warnings every release.

Breaking API change in a minor release

Hi,

this commit ff600ed is very valuable. However, it changes the API of the Fixpoint module (functor more precisely).

That would be fine, expect it has been released with ocamlgraph 1.8.3, without a word of warning in CHANGES about the incompatible change. Ocamlgraph 1.8.3 has made its way into opam or Debian yet, but once it will, expect angry users. Using semantic versioning would be much nicer:
http://semver.org/

Problem building ocamlgraph with MSVC toolchain in Windows

Dear all,

while testing the builds of ocamlgraph in Windows, another problem occurs when
compiling the shared library with the MSVC toolchain.
The error that is reported looks as follows:

[...]
ocamlopt.opt -c -I src -I lib -for-pack Graph src/dot_lexer.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/dot.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/pack.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/gmap.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/minsep.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/cliquetree.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/mcs_m.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/md.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/strat.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/fixpoint.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/leaderlist.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/contraction.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/graphml.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/merge.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/mincut.ml
ocamlopt.opt -c -I src -I lib -for-pack Graph src/clique.ml
ocamlopt.opt -I src -I lib -pack -o graph.cmx src/sig.cmi src/sig_pack.cmi src/d
ot_ast.cmi lib/unionfind.cmx lib/heap.cmx lib/bitv.cmx src/version.cmx src/util.
cmx src/blocks.cmx src/persistent.cmx src/imperative.cmx src/delaunay.cmx src/bu
ilder.cmx src/classic.cmx src/rand.cmx src/oper.cmx src/components.cmx src/path.
cmx src/nonnegative.cmx src/traverse.cmx src/coloring.cmx src/topological.cmx sr
c/kruskal.cmx src/flow.cmx src/prim.cmx src/dominator.cmx src/graphviz.cmx src/g
ml.cmx src/dot_parser.cmx src/dot_lexer.cmx src/dot.cmx src/pack.cmx src/gmap.cm
x src/minsep.cmx src/cliquetree.cmx src/mcs_m.cmx src/md.cmx src/strat.cmx src/f
ixpoint.cmx src/leaderlist.cmx src/contraction.cmx src/graphml.cmx src/merge.cmx
 src/mincut.cmx src/clique.cmx
LINK : warning LNK4044: unrecognized option '/Lsrc'; ignored
LINK : warning LNK4044: unrecognized option '/Llib'; ignored
LINK : warning LNK4044: unrecognized option '/LC:/ocamlms/lib'; ignored
ocamlopt.opt -I src -I lib -a -o graph.cmxa graph.cmx
ocamlopt.opt -I src -I lib -shared -o graph.cmxs graph.cmx
** Fatal error: Cannot find file "uuid.lib"
File "caml_startup", line 1:
Error: Error during linking
Makefile:104: die Regel für Ziel "graph.cmxs" scheiterte
make: *** [graph.cmxs] Fehler 2

If the error message is ignored and continued with "make install" and "make install-findlib", we obtain a running version of ocamlgraph. So it seems that only some parts fail to build, that are not required for a native build with static linking.

If I can help in debugging, please let me know!

Best regards
Martin

Proposition for important entry in FAQ

Hey,

I think it is interesting to explicitly write information (for example in FAQ) if it is possible to update imperative graph during traversal done by fold_vertex or iter_vertex.

The API of Dominator.Make_graph is inconsistent with OCamlgraph's style

The Make_graph functor takes as an argument a module whose signature is imperative, while it seems to me that it should be the persistent one, so as to allow the users to use it both with imperative and persistent implementations (potentially using Builder when necessary).

Is there a reason for this choice? There are not many changes needed to implement my suggestion.

Graph.Pack: parse_dot_file numbers from 1, not from 0

Contrary to Rand which starts from 0. This implies that doing in sequence dot_output then parse_dot_file produces a graph with nodes numbered differently. The culprit is

ocamlgraph/src/pack.ml

Line 149 in 726e8d6

incr new_node;

.

Components.scc_list returns SCCs in reverse order

  let scc_list g =
    let _,scc = scc g in
    let tbl = Hashtbl.create 97 in
    G.iter_vertex
      (fun v ->
         let n = scc v in
         try
           let l = Hashtbl.find tbl n in
           l := v :: !l
         with Not_found ->
           Hashtbl.add tbl n (ref [ v ]))
      g;
    Hashtbl.fold (fun _ v l -> !v :: l) tbl []

Order in which elements are passed to Hashtbl.fold in undefined. At this moment order of SCCs is the reverse of what the user expects.

"The type `edge' is required but not provided" when running demo

Hi I cloned the repo and was trying to get the demos running. However, I get the following error:

mkdir -p bin ocamlopt.opt -o bin/compare_prim_kruskal.opt graphics.cmxa unix.cmxa graph.cmxa examples/compare_prim_kruskal.ml 

File "examples/compare_prim_kruskal.ml", line 103, 
characters 25-26: Error: Signature mismatch: 
       ...        
The type `edge' is required but not provided make: *** [bin/compare_prim_kruskal.opt] 
Error 2

I tried this on both OCaml v4.02.3 and v4.04.2, neither seems to work for some reason. This is rather confusing to me as I thought the with clause at https://github.com/backtracking/ocamlgraph/blob/master/src/prim.mli#L37 would resolve the interface problem. I am quite new to ocaml so maybe I am missing something here...

ERROR while installing ocamlgraph.1.8.7 (missing separator)

I'm running the following versions:

> ocaml --version
The OCaml toplevel, version 4.03.0
> opam --version
1.2.2

And while running:

> opam install mirage

(mirage 3.0.4)

=-=- Processing actions -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=  🐫
[ERROR] The compilation of ocamlgraph failed at "make".
Processing  1/3: [ocamlgraph: ocamlfind remove]
#=== ERROR while installing ocamlgraph.1.8.7 ==================================#
# opam-version 1.2.2
# os           darwin
# command      make
# path         /Users/chris/.opam/mirage-version/build/ocamlgraph.1.8.7
# compiler     4.03.0
# exit-code    2
# env-file     /Users/chris/.opam/mirage-version/build/ocamlgraph.1.8.7/ocamlgraph-84631-d8a4ae.env
# stdout-file  /Users/chris/.opam/mirage-version/build/ocamlgraph.1.8.7/ocamlgraph-84631-d8a4ae.out
# stderr-file  /Users/chris/.opam/mirage-version/build/ocamlgraph.1.8.7/ocamlgraph-84631-d8a4ae.err
### stderr ###
# Makefile:38: *** missing separator.  Stop.

Any insight into obvious gotchas?

Is there a graph edit distance in ocamlgraph?

This one is for trees:
https://pdfs.semanticscholar.org/b3f2/bd7f89fdfdc118432f4105e7e6c00a6073f5.pdf
I wonder if there is an efficient one for graphs.

HTML label problem

When one tries to create html label, a vertex definition in the dot generated file looks like this: "vertex [label="<vertex_name>" ];". The two " characters cause the html parsing to fail.
I think that the " addition trick is used to create clean label names but on the other hand it causes html labels to not work.

Please add an algorithm to calculate the condensation of a directed cyclic graph

It would be nice if ocamlgraph could provide an implementation that calculates the condensation of a cyclic graph. This would allow representing all strongly connected components of a graph as a single vertex and would make the graph acyclic. A callback function could make this generic.

I would prepare a pull request but I'm unsure which algorithm best fits the datastructures used by ocamlgraph.

I tried the following two approaches which do not seem to differ significantly in their speed. They are non-generic and I only want to use them to show the approaches I have tried. My graph has two vertex kinds, PkgV.Pkg and PkgV.SCC where the former only contains a single item and the latter a set of them.

Number 1:

List.iter (function | [] | [_] -> () | scc ->
    let pset = List.fold_left (fun acc v -> match v with
        | PkgV.SCC _ -> fatal "cannot condense graph with SSC vertices"
        | PkgV.Pkg p -> Set.add p acc) Set.empty scc
    in
    let sccv = PkgV.SCC pset in
    let vmemofscc = function
      | PkgV.SCC _ -> false
      | PkgV.Pkg p -> Set.mem p pset
    in
    List.iter (fun v ->
        G.iter_pred (fun pred ->
          G.remove_edge g pred v;
          if not (vmemofscc pred) then G.add_edge g pred sccv) g v;
        G.iter_succ (fun succ ->
          G.remove_edge g v succ;
          if not (vmemofscc succ) then G.add_edge g sccv succ) g v;
        G.remove_vertex g v;
      ) scc;
) (C.scc_list g);
g

Number 2:

let to_scc_vert = function
  | [] -> fatal "scc cannot be empty"
  | [v] -> v
  | scc ->
    let pset = List.fold_left (fun acc v -> match v with
        | PkgV.SCC _ -> fatal "cannot condense graph with SSC vertices"
        | PkgV.Pkg p -> Set.add p acc) Set.empty scc
    in PkgV.SCC pset
in
let sccs = Array.of_list (List.map to_scc_vert (C.scc_list g)) in
let cg = G.create () in
let mapping = Hashtbl.create (G.nb_vertex g) in
Array.iteri (fun i v ->
    match v with
    | PkgV.Pkg _ -> Hashtbl.add mapping v i
    | PkgV.SCC s -> Set.iter (fun p -> Hashtbl.add mapping (PkgV.Pkg p) i) s
  ) sccs;
G.iter_edges (fun v1 v2 ->
  let scc1 = Hashtbl.find mapping v1 in
  let scc2 = Hashtbl.find mapping v2 in
  if scc1 <> scc2 then
    G.add_edge cg sccs.(scc1) sccs.(scc2)
) g;
cg

Using my input graphs (Debian dependency graphs with 51674 vertices and 286301 edges) the first algorithm takes about 43 seconds to execute and the second takes about 38 seconds.

This seems a bit much because I'm building this graph in only 17 seconds and I'm traversing all its vertices in only 6 seconds. Computing C.scc_list only takes 2 seconds so the rest is spent in either moving edges around (in the first version) or building a new graph from a mapping (in the second version).

I wonder if there is an algorithm that would perform better?

Feature request: support for parametric types for V ?

I would like to use this library but my vertex type is a parametric type, something like ('input, 'output) t where I want to use the type system to ensure that I can add an edge from two vertices only if the types are matching. I believe I cannot use this library for this but it would still be nice ;)

Build error on initial invocation of `make`

This error (Linux - haven't observed on Windows) results on the first invocation of make:

  File "editor/gen.ml", line 18, characters 0-1:
  Error: Syntax error

It's down to some top-level directives at this location in this file. Subsequent invocation of make (surprisingly) succeeds.

Using 'module type of'

Performing 'git grep Map.S' or 'git grep Hashtbl.S' returns a few hits, mostly in the results of some algorithms. See e.g. ChaoticIteration for Map.S and Coloring/Path for Hashtbl.S. Those signatures are okay-ish, in the sense that

1. it works
2. it is not optimal, because you do not have the equality between this particular instance of Map.S or Hashtbl.S and others created on the same keys.

My proposal would be to replace the occurrences of e.g. Map.S with type key = G.V.t by module type of Map.Make(G.V), which is strictly more informative. If all instances of Map.Make has been called on the same module-paths everywhere, we would get equality of the results thanks to applicative functors.

Trouble is, the notation module type of is only available starting from 3.12.1 and onwards, which would force us to drop support for 3.10.2 and 3.11. @backtracking @signoles Do you have opinions on such a change?

(BTW, we really encountered this problem in practice, while trying to use ChaoticIteration.)

Default size for temporaries hash tables

When an Ocamlgraph function requires an auxiliary hash table, there is currently no consensus on which size should be used. Depending on the module, you can find values such as 57, 97, 997, 9999 or 65537 (!!). I believe that all but the first two values are too high, as they put an undue pressure on OCaml's GC. (Any array whose size is more than Max_young_wosize triggers a minor collection.) I have an application for which the analysis takes 1min10s when Traverse.Dfs.has_cycle (which is called a considerable amount of time) allocates buckets of size 65537, and 3.5s when it allocates small buckets.

Since hash tables are designed to grow by themselves with a good amortized constant, can we start with reasonable values such as 97 ? This probably won't change much for applications with big graphs, and will make a big difference for those with small graphs.

Dominator module failure

I am using the Dominator module with an Imperative.Digraph.ConcreteLabeled graph. The vertices are constructed from records which include functions. They also include a unique integer identifier which is provided for comparison/hashing purposes.

The dominator module raises an exception on equality of a functional value.

Presumably the dominator module is testing equality of vertices directly rather than using the provided comparison functions.

I have worked around the issue by constructing a separate graph with integer vertices that can be related back to the original graph so it's no big deal. (I wonder if using AbstractLabeled might also work?)

Cheers,
Andy

performance of Oper. transitive_closure

Hi,

I am wondering the performance of Oper.transitive_closure.
I ran the function with a concrete-unlabeled graph (#vertex:2175, #edge: 13065) but it does not terminate even after 12 hours.
I have never treated such a large graph so I am curious that there is a better way to reduce the cost.

Thanks,
Kihong

1.8.6 changes to Dominator.Make causes breakage

I'm not sure whether this is intentional or not, but the Make functor from src/dominator.ml no longer creates a module that exposes the 'compute_all' function.

If it's intentional, it should probably have an asterisk in the CHANGES file. If not, could it be fixed? This causes dose3 to fail to build (due to this)

Please generate a `graph.cmxs` object

So that the library can be used in ocamlnat.

make check fails with ocaml-4.04.0

Forward of downstream report: https://bugs.gentoo.org/show_bug.cgi?id=608554

I'm not sure what changed in ocaml-4.04.0... but I reproduced it with git master:

$ make check
ocaml graph.cma tests/test_clique.ml tests/check.ml
File "./tests/test_clique.ml", line 3, characters 5-10:
Error: Unbound module Graph
make: *** [Makefile:363: check] Error 2

Please let me know if you need any additional information.

Compilation fails in OCaml 4.04.0+flambda with lablgtk

This is an issue related to lablgtk + flambda, but it manifests itself during compilation of ocamlgraph, so I'm not sure where to report it. I'd like someone to confirm they can reproduce it before filing the bug elsewhere.

In OPAM switch 4.04.0+flambda, with package lablgtk 2.18.5 installed, if I try to install ocamlgraph 1.8.7 from OPAM, or if I try to compile from master (tested with 726e8d6), I get an error:

ocamlopt.opt -c -I src -I lib -I /home/user/.opam/4.04.0+flambda/lib/lablgtk2 -I dgraph -I . -for-pack Dgraph dgraph/dGraphView.ml
>> Fatal error: Assignment of a float to a specialised non-float array: (array.unsafe_set[addr]<>
                                                          self/1736
                                                          zoom_f/1701
                                                          Parraysetu_arg/1802)
Fatal error: exception Misc.Fatal_error
Makefile:570: recipe for target 'dgraph/dGraphView.cmx' failed
make: *** [dgraph/dGraphView.cmx] Error 2

Could someone please confirm if the issue is reproducible?

Recommendations about where to file the bug (lablgtk or flambda) are also welcome.

By the way, I just tested on 4.05.0+beta2+flambda and there is no issue, so perhaps it was already fixed...

Reachability by `Fixpoint` is not working as expected.

I wrote a reachability test using the same code explained in fixpoint.mli, but the result is puzzling.

Here is a simple reproducible example. I create here a small graph 1 -> 2 -> 3 and see which vertices are reachable from 1, then from 2. I expect 2 and 3 are reported as reachable from 2, but the code linked with ocamlgraph.1.8.8 does not:

(* ocamlfind ocamlc -o g.exe -package ocamlgraph g.ml -linkpkg *)

module G = Graph.Persistent.Digraph.Concrete(struct
    type t = int
    let compare = compare
    let hash x = x
    let equal = (=)
  end)
    
module Reachability = Graph.Fixpoint.Make(G)
    (struct
      include G
      type g = G.t
      type data = bool
      let direction = Graph.Fixpoint.Forward
      let equal = (=)
      let join = (||)
      let analyze _ = (fun x -> x)
    end)

let test g root =
  let is_root_vertex x = x = root in
  let reachable = Reachability.analyze is_root_vertex g in
  G.iter_vertex (fun n ->
      if reachable n then Format.eprintf "%d is reachable from %d@." n root)
    g

let () =
  (* 1 -> 2 -> 3 *)
  let g =
    let g = G.empty in
    let g = G.add_edge g 1 2 in
    let g = G.add_edge g 2 3 in
    g
  in
  test g 1; (* 1, 2, 3 are reachable from 1 *)

  test g 2  (* 2, 3 are reachable from 2, but it does not report them at all *)

Expected result is:

1 is reachable from 1
2 is reachable from 1
3 is reachable from 1
2 is reachable from 2
3 is reachable from 2

but the actual output is:

1 is reachable from 1
2 is reachable from 1
3 is reachable from 1

Is it a bug of Fixpoint or I misunderstand something?

Building and installing a cmxs version of the library

Hi,

could you consider building and installing a cmxs version of the library, so that it could be loaded dynamically? I realize it's probably a bit tedious because one needs to check that ocamlopt supports -shared on the plateform (probably in ./configure), and generate the META file accordingly.

cannot compile demos?

hi, i just installed via opam and i'm unable to build the demos. i cwd into the build/ocamlgraph.1.8.6 directory in my opam tree, and then try make demo. this fails with

File "examples/demo.ml", line 261, characters 38-39:  
Error: Signature mismatch:
       ...
       The type `edge' is required but not provided

make demo.opt as indicated in the README finds no build target.

Please add releases

In order to be able to access (old) releases of OCamlGraph from github, it suffices to add tags to the repo.

That way, we should be able to do something like wget https://github.com/${user}/${repo}/archive/${version}.tar.gz from scripts.

I know that old versions are available from here http://ocamlgraph.lri.fr/download/ but it's not possible to list the content of this directory now.

Please create a release

Hello.

Could you please create a release on GitHub? At the moment, package managers cannot download a specific version of ocamlgraph.

For version 1.8.6:

$ git tag -a v1.8.6 c10607c
$ git push origin --tags

Thanks for your time.

Is there an equivalent of Graph.Pack.Digraph for persistent graphs?

I like a lot Graph.Pack.Digraph because it gives me direct access to all I need.
However, now that I started to do serious things with my graphs, I don't feel
very comfortable that they are mutable, I'd like them to be persistent.

Safe string support (4.06.0+beta1 compatibility)

Compilation of ocamlgraph fails on 4.06.0+beta1 due to safe string becoming the default.

It seems support for safe-string was added in #60 would it please be possible to make a release ? ocamlgraph is in the dep cone of opam libs which are in turn used by other tools in the eco-system.

=-=- Gathering sources =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
[ocamlgraph.1.8.7] found in cache
[opam-core.2.0.0~beta3.1] found in cache
[opam-format.2.0.0~beta3.1] found in cache
[topkg-care.0.9.0] found in cache

=-=- Processing actions -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
[ERROR] The compilation of ocamlgraph failed at "make".

#=== ERROR while compiling ocamlgraph.1.8.7 ===================================#
# command      make
# path         /Users/dbuenzli/.opam/4.06.0+beta1/.opam-switch/build/ocamlgraph.1.8.7
# exit-code    2
# env-file     /Users/dbuenzli/.opam/log/ocamlgraph-37273-0a5907.env
# output-file  /Users/dbuenzli/.opam/log/ocamlgraph-37273-0a5907.out
### output ###
# [...]
# ocamlc.opt -c -I src -I lib -g -dtypes -w +a -w -4 -w -44 -w -50 -w -48 -w -29 lib/unionfind.ml
# ocamlc.opt -c -I src -I lib -g -dtypes -w +a -w -4 -w -44 -w -50 -w -48 -w -29 lib/heap.mli
# ocamlc.opt -c -I src -I lib -g -dtypes -w +a -w -4 -w -44 -w -50 -w -48 -w -29 lib/heap.ml
# ocamlc.opt -c -I src -I lib -g -dtypes -w +a -w -4 -w -44 -w -50 -w -48 -w -29 lib/bitv.mli
# ocamlc.opt -c -I src -I lib -g -dtypes -w +a -w -4 -w -44 -w -50 -w -48 -w -29 lib/bitv.ml
# File "lib/bitv.ml", line 454, characters 27-39:
# Warning 3: deprecated: String.set
# Use Bytes.set instead.
# File "lib/bitv.ml", line 454, characters 27-28:
# Error: This expression has type string but an expression was expected of type
#          bytes
# make: *** [lib/bitv.cmo] Error 2

Can you please release 1.8.7 on OPAM?

Hi,

Since 1.8.7 has been out for a while, it would be great if we could have it available on OPAM.

Thanks in advance,
Johannes

Decomposition d'un graphe en ses composantes connexes

Bonjour,

J'en ai deja eu besoin et ca n'etait pas dans ocamlgraph a l'epoque.
Est-ce que ca serait possible de l'avoir?

Merci,
Francois.

[NoColoring] is not a valid exception constructor

• ocaml 4.06.0

When attempting to build the documentation via make doc I'm getting the following errors:

File "src/coloring.mli", line 3332, character 0:
[NoColoring] is not a valid exception constructor in "@raise [NoColoring] if [g] cannot be [k]-colored.

      Worst-case time complexity is exponential. Space complexity is O(V)."
File "src/coloring.mli", line 3344, character 0:
[NoColoring] is not a valid exception constructor in "@raise [NoColoring] if [g] cannot be [k]-colored.

      Worst-case time complexity is exponential. Space complexity is O(V)."
File "src/coloring.mli", line 3403, character 0:
[NoColoring] is not a valid exception constructor in "@raise [NoColoring] if [g] cannot be [k]-colored.

      Worst-case time complexity is exponential. Space complexity is O(V)."
File "src/coloring.mli", line 3410, character 0:
[NoColoring] is not a valid exception constructor in "@raise [NoColoring] if [g] cannot be [k]-colored.

      Worst-case time complexity is exponential. Space complexity is O(V)."

It seems that removing the brackets solves this problem insofar as the build completes without issue.

Here is the small diff I'm using to get around this:

diff --git a/src/coloring.mli b/src/coloring.mli
index 4b9cac8..09d0def 100644
--- a/src/coloring.mli
+++ b/src/coloring.mli
@@ -57,7 +57,7 @@ module Mark(G : GM) : sig
       - any value between 1 and [k]: a color already assigned
       - any value greater than [k]: a node to be ignored
 
-      @raise [NoColoring] if [g] cannot be [k]-colored.
+      @raise NoColoring if [g] cannot be [k]-colored.
 
       Worst-case time complexity is exponential. Space complexity is O(V). *)
 
@@ -95,7 +95,7 @@ module Make(G: G) : sig
       coloring as a hash table mapping nodes to their colors.
       Colors are integers from 1 to [k].
 
-      @raise [NoColoring] if [g] cannot be [k]-colored.
+      @raise NoColoring if [g] cannot be [k]-colored.
 
       Worst-case time complexity is exponential. Space complexity is O(V). *)

Examples do not compile.

Specifically,

$ make examples
ocamlopt.opt -c -I src -I lib examples/demo.ml
File "examples/demo.ml", line 261, characters 38-39:
Error: Signature mismatch:
       ...
       The field `edge' is required but not provided
make: *** [examples/demo.cmx] Error 2

Not certain about when this happened but it seems like the difference between the Path Weight and Prim Weight signatures are no longer the same.

Can we do vertex cleaving/splitting with ocamlgraph?

Cannot add edge in simple Persistent module

Hello there,

I'm running into a big of a problem when trying to use the ocamlgraph Persistent module. I create a simple integer based module:

module G = Persistent.Graph.Concrete(
  struct
    type t = int
    let equal a b = phys_equal a b
    let compare a b = if a <= b then a else b
    let hash a = a
  end
)

and try to create a simple graph using the code

>>> let gr = G.add_vertex gr 1;;
val gr : G.t = <abstr>
>>> let gr = G.add_vertex gr 2;;
val gr : G.t = <abstr>
>>> G.is_empty gr;;
- : bool = false

But then when trying to add an edge I run into an error:

>>> G.add_edge gr 1 2;;
Exception: Not_found.
Raised at file "map.ml", line 131, characters 16-25
Called from file "src/blocks.ml", line 140, characters 52-66
Called from file "src/persistent.ml", line 220, characters 14-32
Called from file "toplevel/toploop.ml", line 180, characters 17-56

Any help in debugging this would be highly appreciated.

Calcul de la composante connexe commune maximale entre deux graphes

Bonjour,

Ca aussi ce n'etait pas dans ocamlgraph a l'epoque je crois.
C'est pourtant bien utilie, notemment pour certains problemes de chimie
ou les graphes sont relativement petits et ou l'algorithme exacte, meme s'il
est lent marche quand-meme.

Est-ce que ca serait possible d'avoir ca dans ocamlgraph?

Merci,
Francois.

Separate graph creation in the Dominator module

I'm using a graph who is read-only (https://github.com/Drup/llvmgraph), and I would like to compute dominators on it (to be more precise, provide pre-applied functors). The dominator functor allows to build the subgraph of all dominators, which is not possible with my interface.

The current implementation define create and add_edge as assert false, but it would be better to put this function in another functor altogether and to allow dom_graph to be of a different type.

iter_vertex not starting at root node

I'm not sure if this is an expectation of using iter_vertex, but for most cases I've found that running iter_vertex starts iterating at the root node of the graph. However, if I create a bunch of graphs, this eventually breaks.

Some example code (main.ml):

type instruction =
  | Start
  | Stop

let to_string = function
  | Start -> "Start"
  | Stop -> "Stop"

module E = struct
  type t = Int32.t
  let compare = Int32.compare
  let default = Int32.zero
end
module V = struct type t = instruction end
module G = Graph.Imperative.Digraph.AbstractLabeled(V)(E)

let _ =

  let create () =
    let g = G.create () in
    let src = G.V.create Start in
    let dst = G.V.create Stop in
    let e = G.E.create src Int32.zero dst in
    G.add_vertex g src;
    G.add_vertex g dst;
    G.add_edge_e g e;
    g
  in
  let process () =
    let g = create () in
    let s = Stack.create () in
    let visit v =
      Printf.printf "Vertex = %s\n" (to_string (G.V.label v));
      match G.V.label v with
      | Start -> Stack.push "test" s
      | Stop -> let _ = Stack.pop s in ()
    in
    G.iter_vertex visit g
  in
  for i = 0 to 100 do
    Printf.printf "iteration %d\n" i;
    process ()
  done;

The _tags file:

true: package(ocamlgraph)

To build: ocamlbuild -I . -use-ocamlfind main.native

For me, on iteration 63 I find that the first vertex iterated on is the Stop vertex. I.e., this is the output I get

...
iteration 61
Vertex = Start
Vertex = Stop
iteration 62
Vertex = Start
Vertex = Stop
iteration 63
Vertex = Stop
Fatal error: exception Stack.Empty

DFS and BFS use a strange order

During some tests with the Traverse module, @ThomasRuby and I were surprised by the orders chosen by DFS and BFS. Initially, I wrongly believed that both were somehow looking for nodes with no predecessors, but instead, they use the arbitrary order returned by fold_vertex or iter_vertex. More precisely, they perform a DFS or a BFS for each node returned by one of these functions if it has not been seen yet (and each traversal also ignores nodes seen by each previous traversal).

For instance, let us consider the following diamond graph:
g : u1 -> u2, u1 -> u3, u2 -> u4, u3 -> u4
If iter_vertex traverses nodes in the order [1; 2; 3; 4] (or any other order that begins with 1), the DFS or the BFS starts a traversal at node 1, visits all the nodes, and then do nothing for the subsequent calls on nodes 2, 3 and 4. From the point of view of the user, this amounts to a single traversal from node 1, and this is what is expected.

On the contrary, if iter_vertex traverses nodes in the order [4; 2; 3; 1], then the DFS or the BFS starts a traversal at node 4 that stops immediately since 4 has no children, then perform a traversal at node 2 that stops immediately since the only child, 4, has already been processed, and similarly for 3 and 1. This means that, whether we perform a DFS prefix, a DFS postfix or a BFS, nodes are systematically processed in the same order, i.e. [4; 2; 3; 1]. For me, in this case, it actually does not look like a DFS or BFS traversal.

I consider there are four solutions:

• consider this is the normal behaviour (though, in my opinion, it makes some sense only in the case of a postfix DFS since, at least, the property that each node is visited after its children is observed), and better document it;

• change the comment

  It is enough to iter over all the roots (vertices without predecessor) of the graph, even if iterating over the other vertices is correct.

  in the documentation into

  Be careful to iter only over all the roots (vertices without predecessor) of the graph

  (but certainly in this case, the functions should not be named fold_vertex and iter_vertex anymore);

• add to the functions some additional argument specifying the initial node(s);

• as suggested in the first paragraph, look for nodes with no predecessors before performing any traversal.

Seperate Graph- and Viewer functionality

I think it woule be better to seperate the ocamlgraph-module and the graph-viewer.
I think seperating the pure Graph-Processing and the GUI-stuff / viewer would be good style.

Is there a diameter function?

I have an undirected graph.
All edge weights are one and there are cycles.
Is there an algorithm implemented to find the diameter of the graph?
I.e. the longest of all shortest-path between any two pair of points from the graph.

Issue with WEIGHT signature

In last version 1.8.6, Path.WEIGHT was changed so that weight is of type edge -> t (which breaks compat in a patch version, seriously ...).

Prim.WEIGHT, which used to be the same, was not updated.

Maybe the WEIGHT signature should be pulled in Sig and standardized ?

Port ocamlgraph to lablgtk3

GTK 2 is being deprecated, and there is largely compatible version of OCaml bindings to GTK 3 is available - lablgtk3.

See lablgtk3 branch here: https://github.com/garrigue/lablgtk/tree/lablgtk3

Folds

Folds for BFS and DFS would be useful.

Path.WEIGHT.weight signature

Is there a good reason why the signature Path.WEIGHT declares the weight function to have type
label -> t instead of edge -> t? The latter is more general as it allows to specify meaningful weights even when using a graph without explicit edge labels, and I don't see any obvious disadvantages. Am I missing something or is this purely accidental?