# package ocamlgraph

## Install

## Dune Dependency

## Authors

## Maintainers

## Sources

`sha256=0f962c36f9253df2393955af41b074b6a426b2f92a9def795b2005b57d302d65`

`sha512=8ee77bc1ef27bef41171b5718a73342dca8adc4b4592ff835038cd21e8c91152a0f9500b4034f664d1db7a09dab1efcc3be5d7c59260d6b33710b82a1fb2f196`

## CHANGES.md.html

## 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`

/ocamlgraphViewgraph 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