Changelog of @hackage/fgl 5.5.4.0

5.5.4.0

  • Improved type safety of shortest-path functions (in Data.Graph.Inductive.Query.SP) thanks to Nathan Collins.

    • getDistance, spLength and sp now return Maybe values.

  • Fixed building on GHC < 7.4; previously uncaught due to cabal-install doing the wrong thing on Travis-CI.

5.5.3.1

  • Hopefully clearer documentation for &, Context and the ufold-based functions.

  • Thanks to David Feuer, the existing benchmark suite is now runnable with cabal bench.

  • Some performance improvements for PatriciaTree, thanks to David Feuer.

5.5.3.0

  • Additional closure functions by Matthew Danish.

  • Bifunctor instances for base >= 4.8.0.0.

  • An ST-based GraphM instance.

  • Addition of order and size functions for finding the number of nodes and edges respectively in a graph (the former is an alias for the existing noNodes function).

  • The rules for faster implementations of insNode and insEdge for PatriciaTree should fire more often now.

5.5.2.3

  • Earlier fix for NFData wasn't quite complete/correct.

5.5.2.2

  • Ensure firing of specialised rules for PatriciaTree.

  • Better way of only creating NFData instances when possible.

5.5.2.1

  • Only create NFData instances for GHC >= 7.4.1.

5.5.2.0

  • Documentation, clean-up and refactoring of various parts of the library.

    • As part of this, various types now have instances for classes like Show, Eq, Ord, NFData, etc. where applicable.

    • In particular, the various options for use with depth-first search and shortest path queries was documented by David Luposchainsky.

  • Addition of a proper test-suite. So far it covers the Data.Graph.Inductive.Graph module and all Data.Graph.Inductive.Query.* modules except for Monad.

    • The tests are also automatically run for every (set of) commits thanks to Travis-CI.

  • Arbitrary instances for the two graph types are now available in the new fgl-arbitrary sub-package.

  • Now depends solely on the transformers library rather than mtl.

  • Potentially breaking changes:

    These changes are those where the behaviour was un-specified or didn't match the documentation.

    • nodeRange and nodeRangeM for the various graph data structures erroneously returned (0,0) for empty graphs (making them indistinguishable from graphs containing the single node 0). They now match the default implementation of throwing an error.

    • The behaviour of delLEdge when dealing with multiple edges was unspecified; it now deletes only a single edge and the new function delAllLEdge deletes all edges matching the one provided.

  • Additional functions thanks to Sergiu Ivanov:

    • Creating sub-graphs by Node- and Context-filtering as well as induced by a set of Nodes.

    • Graph condensation (i.e. graph of strongly-connected-components).

    • Various edge- and neighbor-based helper functions.

  • The graph types now have Generic instances thanks to Piotr Mlodawski.

  • The OrdGr wrapper by Trevor Cook allows performing Ord-based comparisons on graphs.

5.5.1.0

  • Support added for GHC 7.10 by Herbert Valerio Riedel.

  • Additional DFS query functions added by Conrad Parker.

  • Repository location changed to GitHub.

  • Code cleanup:

    • Replaced usage of internal FiniteMap copy with Data.Map and Data.Set from the containers library.

    • Remove usage of data type contexts.

    • Use newtypes where applicable.

5.5.0.1

  • Fix up Eq instances for Tree and PatriciaTree so that they work with multiple edges.

5.5.0.0

  • Add proper Show, Read and Eq instances to Data.Graph.Inductive.Tree and Data.Graph.Inductive.PatriciaTree.

  • Add pretty-printing functions to Data.Graph.Inductive.Graph. These are based upon the old Show implementation for Data.Graph.Inductive.Tree.

  • Now use PatriciaTree by default rather than Tree (and recommend as such). IntMap has been receiving a lot of optimisation work on it, whereas the internal FiniteMap implementation hasn't received any attention.

  • The version :: IO () action now uses the actual Cabal version.

  • Remove Data.Graph.Inductive.Graphviz; use the graphviz package instead.

5.4.2.4

  • Update to work with GHC-7.2 and Cabal-1.6.

5.4.2.3

  • Maintainership taken over by Ivan Miljenovic.

  • Allow Data.Graph.Inductive.PatriciaTree to deal with multiple edges between nodes.

5.4.2.2 (November 2008)

  • Bugfix in Graphviz.sq

5.4.2.1 (June 2008)

  • bug fix in bcc by Reid Barton

  • added new dynamic graph implementation: Data.Graph.Inductive.PatriciaTree (thanks to Pho)

  • added test/benchmark.hs: a benchmark to compare Tree and PatriciaTree implementations (thanks to Pho)

5.4.2 (May 2008)

  • added Setup.hs to tar file

  • reimplementation of Data.Graph.Inductive.Query.Dominators by Bertram Felgenhauer:

    It was buggy and very slow for large graphs. See http://www.haskell.org/pipermail/haskell-cafe/2008-April/041739.html

    This patch also adds a new function, iDom, that returns the immediate dominators of the graph nodes.

  • Exported xdf*With functions from DFS.hs

  • many little cleanups thanks to many people (use 'darcs changes' to see the details)

5.4 (April 2007)

  • changed the implementation for inspection functions (suc, pred, ...) to correct the behavior in the presence of loops (thanks to Ralf Juengling for pointing out the inconsistency)

5.3 (June 2006)

  • fixed a bug in findP (thanks to lnagy@fit.edu)

  • added function delLEdge in Graph.hs (thanks to Jose Labra)

  • changed implementation of updFM and mkGraph (thanks to Don Stewart)

February 2005

  • fixed an import error in Basic.hs

  • removed Eq instance of gr because it caused overlapping instance problems. Instead the function equal defined in Graph.hs can be used

  • added some more functions to the export list of DFS.hs

  • changed the definition of LPath into a newtype to avoid overlapping instances with lists

  • fixed the Makefile (for GHC and GHCi)

January 2004

  • bug fix for nearestNode (src/Data/Graph/Inductive/Query/GVD.hs) Update contributed by Aetion Technologies LLC (www.aetion.com)

  • Refactor into hierarchical namespace

  • Build changes:

    • build a standard haskell library (libHSfgl.a, HSfgl.o)
    • install as ghc package (fgl), uses Auto so no -package is needed

  • Automatic Node generation for labels: Data.Graph.Inductive.NodeMap

  • Graphviz output: Data.Graph.Inductive.Graphviz

September 2002

  • Introduction of graph classes

  • Monadic graphs and graph computation monad

  • Graph implementation based on balanced (AVL) trees

  • Fast graph implementation based on IO arrays

  • New algorithms:

    • Maximum flow
    • Articulation points
    • biconnected components
    • dominators
    • transitive closure

  • minor changes in utility functions

    • changed signatures (swapped order of arguments) of functions context and lab to be consistent with other graph functions
    • changed function first in RootPath: not existing path is now reported as an empty list and will not produce an error
    • esp version that returns a list of labeled edges (to find minimum label in maxflow algorithm)
    • BFS uses amortized O(1) queue
    • Heap stores key and value separately
    • ...

March 2001

  • Changes to User Guide

  • a couple of new functions

  • some internal changes

April 2000

  • User Guide

  • Systematic structure for all depth-first search functions

  • Graph Voronoi diagram

  • Several small changes and additions in utility functions

February 2000

  • Representation for inward-directed trees

  • Breadth-first search

  • Dijkstra's algorithm

  • Minimum-spanning-tree algorithm

August 1999

  • First Haskell version