package ocamlgraph_gtk

2.2.0 (April 11, 2025)

• [Topological]: Fix topological stable sort (#149, Maxime Buyse)
• [Path]: new module [Bfs01] to implement 0-1 BFS
• [Classic] new functions [kneser] and [petersen] to build Kneser's graphs and the Petersen graph
• [Oper] fixed transitive reduction (#145, reported by sim642) and tests for transitive reduction!
• new example depend2dot to turn make-like dependencies into a DOT graph, with transitive reduction
• [Graphviz]: added PosPinned to type NeatoAttributes.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_dist to perform a breadth-first traversal with the distance from the source

2.1.0 (August 30, 2023)

• :exclamation: OCamlGraph now requires OCaml >= 4.08
• :exclamation: [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

2.0.0 (October 2, 2020)

• port to dune and opam 2.0
• :exclamation: 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)
• :exclamation: [Coloring] functions now fail if the graph is directed
• :exclamation: [Coloring] now uses a single, global exception [NoColoring]
• [Coloring] new function two_color to 2-color a graph (or fail)
• :exclamation: [Fixpoint] Take initial labeling of nodes into account (Johannes Kloos)
• :exclamation: [Dominator.Make_graph] now accepts a signature that is Builder-compatible

1.8.8, October 17, 2017

• fixed installation (Virgile Prevosto, Jacques-Pascal Deplaix)
• safe-string compatible (Jacques-Pascal Deplaix)
• :exclamation: 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)
• :exclamation: 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)

1.8.7, April 12, 2016

• 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
• :exclamation: 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.

1.8.6, January 23, 2015

• :exclamation: 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
• :exclamation: 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.

1.8.5, March 4, 2014

• 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'.

version 1.8.4, February 4, 2014

• 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

1.8.3, April 17, 2013

• 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)

1.8.2, May 12, 2012

• 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 markus.weissmann@in.tum.de)

1.8.1, October 17, 2011

• 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 markus.weissmann@in.tum.de)
• new module Fixpoint to compute fixpoints using the work-list algorithm, e.g. for data flow analysis (contributed by Markus W. Weissmann markus.weissmann@in.tum.de)

1.8, October 4, 2011

• 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"

1.7, February 23, 2011

• 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

1.6, December 13, 2010

• 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 (was Constraints) (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

1.5, April 29, 2010

• 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

1.4, March 24, 2010

• 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)

1.3, October 2, 2009

• 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

1.2, August 31, 2009

• experimental: new GTK-based graph viewer called Dgraph (viewGraph is now deprecated)
• added Delaunay.iter_triangles (not of use in Ocamlgraph, actually)

1.1, June 23, 2009

• 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)

1.0, October 14, 2008

• 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)

0.99c, April 3rd, 2008

• replicated a bug fix of Bitv (could not affect Matrix, though)
• fixed DFS traversal in Traverse.Dfs.{prefix,prefix_component,iterator}

0.99b, December 18th, 2007

• fixed link bug with ocaml 3.09 (see http://caml.inria.fr/mantis/view.php?id=4124)

0.99a, November 21st, 2007

• 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

0.99, June 27th, 2007

• 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

0.98, Sep 27th, 2006

• 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)

0.97, July 20th, 2006

• fixed compilation under Windows/Cygwin (contributed by Denis Berthod)
• fixed bug with escaped string in Graphviz

0.96, May 2nd, 2006

• 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)

0.95, November 2nd, 2005

• compatibility with ocaml 3.09
• new module Path.Check to check for paths

0.94, July 6th, 2005

• 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)

0.93, March 31st, 2005

• 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)

0.92, January 18th, 2005

• 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

0.91, December 16th, 2004

• 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

0.90, November 30th, 2004

• 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

0.81, July 13th, 2004

• 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)

0.80, June 28th, 2004

• 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")

0.70, Feb 27th, 2004

• 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

0.60, Feb 18th, 2004

• 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)

0.50, Feb 4th, 2004

• first release