- [Oper] fixed transitive reduction (#145, reported by sim642) and tests for transitive reduction!
- new example
depend2dotto turnmake-like dependencies into a DOT graph, with transitive reduction - [Graphviz]: added
PosPinnedto typeNeatoAttributes.vertex - [Oper]: improved efficiency of
intersect(#136, reported by Ion Chirica) - [Path.Check]: improved efficiency with a better use of the cache (#125 by Paul Patault)
- [Cycles.Johnson]: Enumerate elementary cycles (Johnson, 1975) (contributed by Timothy Bourke)
- [Traverse.Bfs]: new function
{fold,iter}_component_distto perform a breadth-first traversal with the distance from the source
- ❗ OCamlGraph now requires OCaml >= 4.08
- ❗ [Traverse]: fixed [Dfs.fold] and [Dfs.fold_component], which were not implementing a proper DFS
- [Classic]: new functions [cycle] and [grid]
- [Eulerian]: Eulerian paths (new module)
- [Components]: strong articulation points (see functors [Connectivity] and [BiConnectivity]) (Timothy Bourke)
- [Dominator]: non-trivial dominators (Timothy Bourke)
- #31: fixed documentation of [map_vertex]: the supplied function must be injective
- #110: ensure that map_vertex applies the function only once per vertex
- port to dune and opam 2.0
- ❗ opam package now split into two packages: ocamlgraph and ocamlgraph_gtk
- [WeakTopological] fixed incorrect use of generic hash tables (#99, Tomáš Dacík)
- [Oper] fixed transitive_reduction (#91)
- fix incorrect uses of polymorphic equality (Steffen Smolka, Boris Yakobowski)
- [Coloring] fixed generation of OCamlDoc documentation (contributed by Earnestly)
- ❗ [Coloring] functions now fail if the graph is directed
- ❗ [Coloring] now uses a single, global exception [NoColoring]
- [Coloring] new function two_color to 2-color a graph (or fail)
- ❗ [Fixpoint] Take initial labeling of nodes into account (Johannes Kloos)
- ❗ [Dominator.Make_graph] now accepts a signature that is Builder-compatible
- fixed installation (Virgile Prevosto, Jacques-Pascal Deplaix)
- safe-string compatible (Jacques-Pascal Deplaix)
- ❗ fixed method get_edge_layout of class abstract_model of DGraphModel.Make. The bug could have occured when there are several edges between two vertices.
- [Traverse/Pack] added Dfs.fold and Dfs.fold_component (tail-recursive) (contributed by Guillaume Chelfi)
- ❗ fixed implementation of Golberg-Tarjan maximal flow algorithm (contributed by Guyslain Naves) No more function min_capacity in the input interface. Renaming as follows: Flow.Goldberg -> Flow.Goldberg_Tarjan and Pack.goldberg -> Pack.goldberg_tarjan
- new functors [WeakTopological] and [ChaoticIteration] to compute fixpoints with widening, following Bourdoncle's algorithms (contributed by Thibault Suzanne)
- fixed examples/demo.ml so that it also compiles with an installed OCamlGraph
- [Components] fixed stack overflow with [scc] (patch by Albin Coquereau)
- [Dominator] fixed stack overflow (patch by Albin Coquereau)
- new functor [Path.Johnson] to compute all pairs of shortest paths using Johnson's algorithm (contributed by Mário Pereira)
- fixed configuration on Windows (patch by Martin R. Neuhäußer)
- new functor [Components.Undirected] to compute connected components
- Graphviz: fixed printing of attribute BgcolorWithTransparency
- ❗ Prim, Nonnegative: function weight now has the more general type "edge -> t" (to be consistent with Path)
- new module type Sig.WEIGHT (used in Path, Prim, and Nonnegative)
- Fixpoint: do not catch Not_found raised by a user-provided function.
- Adding folds to BFS.
- ❗ Dominator: new functor [Make_graph] with may use graph building operations, while the old functor [Make] now only requires a read-only graph. Function [compute_all] and [compute_dom_graph] are now only defined in the new [Make_graph] functor.
- Graphviz: support for additional polygonal-shapes
- New module Clique (contributed by Giselle Reis)
- Avoid ocamldoc error with OCaml 4.02
- ❗ Path: function weight now has the more general type "edge -> t" (contributed by Steffen Smolka) update your code by turning "weight l" into "weight (G.E.label e)"
- installation: "make install-findlib" now uses DESTDIR when defined
- Traverse: documentation is clarified: providing iterators over the roots of the graph is enough.
- Imperative concreate (di)graph: fix bug of functions add_edge* of imperative concrete (di)graphs which appears when the added edge [e] was already in the graph [g] and one of the vertices of [e] is equal to another vertex of [g] (when using the user-defined equality [G.V.equal]), but not physically equal to it. This bug only occurs with OCaml version >= 4.0.
- functions in modules Components, Dominator, Flow, Topological and Traverse now create smaller auxiliary hash tables
- Graphviz: add the attribute `HtmlLabel to specify html strings.
- Graphviz: reverted to the old API where edges and vertices are given a single style attribute; but such attributes are collected and output in the DOT file into a list (thus allowing multiple style attributes)
- fixed issue in ./configure with ocamlfind on Win32.
- fixed compilation when laglgnomecanvas is missing (bug introduced in 1.8.4).
- fixed more issues with 'make -j'.
- fixed [Graphml] printer (contributed by Johannes Schauer)
- Components: the components of [scc_list] are provided in the same order than the ones of [scc_array].
- fix compilation with 'make -j'
- Graphviz: handle attribute penwidth on edges and vertices
- also install graph.o and graph.cmxs
- fixed installation with ocamlfind (thanks to Virgile Prevosto)
- new functions [gnp] and [gnp_labeled] in module [Rand] to generate random graphs using the G(n,p) model (contributed by Thomas Aubry)
- Prim's algorithm (in module [Prim]; not exported in [Pack]) (contributed by Thomas Aubry)
- Graphviz: support for nested subgraphs. (Backward-incompatible change: add 'sg_parent = None' to obtain subgraphs whose parents are the main graph)
- Graphviz: edges and vertices can now receive multiple styles. (Backward-incompatible change: constructors `Style now require a list as argument)
- Graphviz: new vertex style 'rounded'
- Merge: fixed bug with vertices with no incoming nor outcoming edge.
- fixed compilation issue with OCaml 3.12.1
- new module Merge implementing several different merges of vertices and edges into a graph (contributed by Emmanuel Haucourt)
- fixed DOT parser (contributed by Alex Reece)
- Topological: fixed bug in presence of disjoint cycles; new implementation
- new module [Graphml] to export graphs into the graphml format (contributed by Pietro Abate)
- Builder.S now contains functions remove_*.
- modified Fixpoint module so that it also works with unlabeled graphs, break backward compatibility yet (contributed by Markus W. Weissmann)
- support of lablgtk2 installed with findlib (contributed by B. Monate)
- new module [Dominator] to compute dominators (contributed by David Brumley and Ivan Jager)
- new module [Path.BellmanFord] implementing Bellman-Ford algorithm (contributed by Yuto Takei)
- new module Contraction implementing edge contraction (contributed by Markus W. Weissmann)
- Gmap: new function [filter_map] (contributed by Markus W. Weissmann)
- Topological: fix bug when a cycle depends on another cycle. That breaks compatibility: the input graph must implement Sig.COMPARABLE instead of Sig.HASHABLE
- new module Topological.Make_stable to iterate over a graph in a stable topological order. Stable means that the provided ordering only depends on the graph topology and on the user's vertices ordering.
- new module Leaderlist to compute the leader list algorithm (see the Dragon) (contributed by Markus W. Weissmann [email protected])
- module Gmap now has a signature for edges (E_SRC) compatible with Sig, so that it is easier to apply functor Gmap.Edge (contributed by Markus W. Weissmann [email protected])
- new module Fixpoint to compute fixpoints using the work-list algorithm, e.g. for data flow analysis (contributed by Markus W. Weissmann [email protected])
- removed ocamlyacc shift/reduce conflict in dot_parser.mly (patch contributed by Till Varoquaux)
- Dgraph: Correct height and width-related problems with text
- DGraph: many bug fixes. Patch by Benjamin Monate
- Sig.G: new function [find_all_edges] for each graph implementation
- Oper: fixed bug with function [intersect]: now use G.E.compare instead of (=)
- fixed "make install-findlib"
- Makefile: fixed bug when installing ocamlgraph with ocamlfind
- DGraph: fixed bug with colors on some windows manager
- Configure: fixed issue with automatic detection of extension under Windows/Mingw
- DGraph: new viewer mode (called `tree') which focus on a subset part of the graph centered on a given node
- Graphviz: fixed bug with attribute
Constraint (wasConstraints) (patch by Boris Yakobowski) - DGraph: fixed font size issue when zooming
- DGraph: now interpret text anchors and espaced sequences correctly
- DGraph: offer possibility to disable the default callbacks on nodes
- 'make -j' works again
- new implementation Persistent.Digraph.ConcreteBidirectionalLabeled
- new implementation Persistent.Digraph.ConcreteBidirectional
- Makefile: bug fixed when ocamlc (resp. ocamlopt) and ocamlc.opt (resp. ocamlopt.opt) are unconsistent
- Makefile: bug fixed when installing ocamlgraph with ocamlfind (patch by Virgile Prevosto)
- DGraph: new method set_zoom_padding in DgraphView.view
- Traverse.Dfs.has_cycle: can now be used on undirected graphs as well, and is now tail recursive
- DGraph: handle dotted ellipse
- new function [clear] for imperative graphs
- new implementation Imperative.Digraph.ConcreteBidirectionalLabeled (contribution of Jaap Boender)
- Dgraph displays graphs faster
- DGraph: several bugs fixed
- DGraph: several API changes (may break compatibility with existing development)
- Oper.mirror: undirected graphs are not copied anymore
- Oper.mirror: fixed bug (isolated vertices were lost)
- Graphviz: new signature GraphWithDotAttrs
- Improvements of Dgraph
- Configure: better test for detecting lablgtk
- OcamlGraph is now installed by default in
ocamlc -where/ocamlgraph - Viewgraph is now packed in a single module Viewgraph (break compatibility with previous version)
- Dgraph is now packed in a single module Dgraph (break compatibility with previous version)
- Makefile: fixed bug when the installation directory of binaries does not exist
- Makefile: fixed bug of ocamldep under Windows
- experimental: new GTK-based graph viewer called Dgraph (viewGraph is now deprecated)
- added Delaunay.iter_triangles (not of use in Ocamlgraph, actually)
- added constraint "type E.label = unit" to unlabeled graph data structure
- viewGraph: new module viewGraph_utils; fixed compilation (gtkInit was missing; patch by Mehdi Dogguy)
- configure: fixed bug under Cygwin (patch by Julien Bernet)
- configure: look for lablgnomecanvas.cmxa when compiling in native code
- Makefile: fixed make install-findlib when lablgtk and/or lablgnomecanvas not installed (patch by Peter Hawkins)
- license: LGPL updated to version 2.1
- ocamlgraph now requires ocaml 3.10 or higher
- experimental: GTK-based graph viewer based on dot (contribution of Anne Pacalet)
- Makefile:
- fixed bug when lablgnomecanvas is not installed
- fixed bug when ocamlfind is installed
- patch to the build system for a DESTDIR (patch by Igor Galic)
- "make -j" compliant
- new function Blocks.after_unserialization in order to be able to safely serialize abstract vertices (see the FAQ)
- Dot:
- fixed bug in the parsing of attributes
- fixed bug in the parsing of subgraphs (patch by Anne Pacalet)
- Oper: fixed bug in intersect
- Path: improved efficiency of Dijkstra
- Topological:
- fixed bug in Make.{iter,fold}
- folding is now tail-recursive (patch by Michael Furr)
- replicated a bug fix of Bitv (could not affect Matrix, though)
- fixed DFS traversal in Traverse.Dfs.{prefix,prefix_component,iterator}
- fixed link bug with ocaml 3.09 (see http://caml.inria.fr/mantis/view.php?id=4124)
- fixed bug in Makefile when lablgtk2 is not installed
- Sig.I.create and Sig_pack.create are now of type ?size:int -> unit -> t (instead of unit -> t) to indicate an initial guess on the graph size
- experimental: GTK-based graph editor based on hyperbolic geometry; to build it and test it, cd to editor/ and type make
- [Components.Make] functor: function [scc] as a new profile and a more precise specification. New function [scc_array].
- fixed configure to set ocaml's standard library using "ocamlc -where"
- new module Dot to parse files in Graphviz's DOT format
- slight change in the license (no more clause 6 of the LGPL; see LICENSE)
- new module Strat implementing simple game strategies
- Graphviz: little refactoring and improved documentation
- rename Sig.IA to Sig.IM
- add subgraph support in Graphviz (breaks ascendent compatibility if you use Graphviz: by default add let get_subgraph _ = None in the argument of Graphviz.Dot and Graphviz.Neato)
- fixed compilation under Windows/Cygwin (contributed by Denis Berthod)
- fixed bug with escaped string in Graphviz
- new demo program: sudoku.ml (solving the Sudoku using graph coloring)
- new module Coloring for (rather brute force) graph coloring
- new implementation Imperative.Digraph.ConcreteBidirectional that maintains the set of ingoing edges for each node, thus improving the efficiency of functions such as iter_pred, pred, in_degree, etc. (contributed by Ted Kremenek)
- compatibility with ocaml 3.09
- new module Path.Check to check for paths
- new module Gml to parse and print graphs in GML file format (see http://www.infosun.fmi.uni-passau.de/Graphlet/GML) corresponding functions parse_gml_file and print_gml_file in Pack
- added display_with_gv in Pack
- improved implementation of Unionfind (patch by Marc Lasson)
- fixed bug in Rand (integer overflow causing Invalid_argument "random"); improved code in Rand
- bug fixed in the META file
- add find_edge in Sig.G (and so in all graph implementations)
- fixed escaped labels in Graphviz output (patch by Boris Yakobowski)
- new Graphviz option OrderingOut (patch by Boris Yakobowski)
- fixed sharing bugs in Oper (patch by Boris Yakobowski)
- fixed bug in nb_edges for undirected graphs
- improvement of iterators of undirected concrete graphs
- more precise specifications of remove_edge and shortest_path.
- bug fixed in mem_edge_e of labelled graphs
- generation of random graphs improved
- add Rand.Make and Rand.Planar.Make (generic functors)
- add signatures Persistent.S and Imperative.S
- graph.cma graph.cmxa
- version.ml and META files are now writable
- add interfaces Sig.VERTEX and Sig.EDGE
- "sig.ml" and "sig_pack.ml" removed; ocamlgraph now requires ocaml 3.08.0
- improvement of Minsep
- add Components.scc_list
- Oper.Neighbourhood replaces Neighborhood
- Gmap replaces Copy
- add types Sig_pack.vertex and Sig_pack.edge
- fixed bug in Ford-Fulkerson: G.V.equal instead of = in two asserts
- compatibility with ocaml 3.08
- Oper.Choose.choose_edge: choose an edge in a graph
- add types Sig.G.edge and Sig.G.vertex resp. equal to Sig.G.V.t and Sig.G.E.t
- fixed typos in invalid_arg arguments (in Bitv)
- major contribution by Matthieu Sozeau and Pierre-Loïc Garoche.
New modules are:
- Md: Minimum Degree algorithm
- Cliquetree: the clique tree of a graph
- Mcs_m: Maximal Cardinality Search (MCS-M) algorithm
- Minsep: Minimal separators of a graph
- Neighborhood: compute the neighborhood of a vertex/some vertices
- Oper.Difference: subgraphs induced by the elimination of some vertices
- Oper.Choose: choose a vertex in a graph
- Copy: graphs copying
- Util.DataV: create a vertex type with data attached to it
- out_degree: raises Invalid_argument if v not in g (instead of Not_found)
- Pack.Graph: golberg/ford_fulkerson fail ("not a directed graph")
- Makefile.in: dependences ("make -j" works)
- union and intersection (see Oper.S.union and Oper.S.intersection)
- Golberg/Ford_fulkerson algorithms in a single module Flow
- step-by-step iterators in Traverse.{Dfs,Bfs}
- Ford_fulkerson: maxflow now returns a flow function over edges
- fixed bug in Ford-Fulkerson
- random planar graphs (see Rand.Planar)
- Delaunay triangulation (see Delaunay)
- implementations with adjacency matrices (see Imperative.Matrix)
- operations on predecessors for undirected graphs optimized
- Traverse.Dfs.{prefix,prefix_component} optimized (now tail recursive)
- first release