backtracking / ocamlgraph Goto Github PK
View Code? Open in Web Editor NEWOCaml graph library
Home Page: http://backtracking.github.io/ocamlgraph/
License: Other
OCaml graph library
Home Page: http://backtracking.github.io/ocamlgraph/
License: Other
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.
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?
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
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 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.
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.
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.
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.
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.
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.
Folds for BFS and DFS would be useful.
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.
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?
it doesn't show up in ocp-browser. :(
This one is for trees:
https://pdfs.semanticscholar.org/b3f2/bd7f89fdfdc118432f4105e7e6c00a6073f5.pdf
I wonder if there is an efficient one for 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.
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.
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
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.
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.
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
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.
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 ?
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)
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/
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.
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
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
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. :-)
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 ;)
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.
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?
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...
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...
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
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.
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.
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.
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.
So that the library can be used in ocamlnat
.
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.
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
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.
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.
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?
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
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
.)
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
Line 149 in 726e8d6
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
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). *)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.