package ocamlgraph

  1. Overview
  2. Docs
A generic graph library for OCaml

Install

Dune Dependency

Authors

Maintainers

Sources

ocamlgraph-2.1.0.tbz
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/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