FGL/Haskell - A Functional Graph Library for Haskell Version 5.4.2.2, November 2008

Kown bug:

• The Patricia tree implementation does not support multiple edges between two nodes.

New since the last version (June 2008):

• Bug fix in Graphvis.sq

The functional graph library for Haskell provides several modules that define inductive graphs and graph algorithms. An older version for ML can be found here.

To use the library:

• Download fgl-5.4.2.2.tar.gz
  Note that an up-to-date version can be found on Hackage and at: http://darcs.haskell.org/packages/fgl/
• Gunzip and untar the archive. This will create a directory fgl-5.4.2.2. Change to that directory.
• For GHC/GHCi (version 6.6):
  1. To build and install the FGL package, run:

     runhaskell Setup.hs configure
     runhaskell Setup.hs build
     runhaskell Setup.hs install
     runhaskell Setup.hs register

  2. Download a little test program test.hs, and compile and run it or load it into ghci:

     ghci test.hs

     Print some test values, e.g.:

     *Main> t2
     Loading package fgl ... linking ... done.
     
     1:"shorts"->[((),4),((),5)]
     2:"socks"->[((),5)]
     3:"watch"->[((),4)]
     4:"pants"->[((),7),((),5)]
     5:"shoes"->[]
     6:"shirt"->[((),3),((),8),((),7)]
     7:"belt"->[((),9)]
     8:"tie"->[((),9)]
     9:"jacket"->[]

     Apply graph algorithms:

     *Main> topsort t2
     [6,8,3,2,1,4,5,7,9]
     *Main> topsort' t2
     ["shirt","tie","watch","socks","shorts","pants","shoes","belt","jacket"]

  3. Note: Don't start ghci from the installation directory unless you have removed all .hs and .o files from the local Data/Graph/Inductive subdirectories, because otherwise ghci (version 6.2) might get confused.
• For Hugs (November 2003 or later):
  1. Copy the sources to the Hugs Data subdirectory of the hierarchical library directory (change /usr/local to the appropriate directory prefix of your installation):

     cp -R Data/Graph /usr/local/lib/hugs/libraries/Data

  2. Start Hugs disabling 98 compatibility mode to facilitate multi-parameter type classes:

     hugs -98

  3. Load the FGL examples:

     Prelude> :l Data.Graph.Inductive.Example

  4. Print an example graph showing clothing dependencies (this example is taken from Cormen, Leiserson, Rivest "Introduction to Algorithms", MIT Press 1990, p. 486):

     Data.Graph.Inductive.Example> clr486
     
     1:"shorts"->[((),4),((),5)]
     2:"socks"->[((),5)]
     3:"watch"->[]
     4:"pants"->[((),5),((),7)]
     5:"shoes"->[]
     6:"shirt"->[((),7),((),8)]
     7:"belt"->[((),9)]
     8:"tie"->[((),9)]
     9:"jacket"->[] :: Gr String ()

  5. Determine a correct order of how to dress:

     Data.Graph.Inductive.Example> topsort clr486
     [6,8,3,2,1,4,7,9,5]

     or even better:

     Data.Graph.Inductive.Example> topsort' clr486
     ["shirt","tie","watch","socks","shorts","pants","belt","jacket","shoes"]

You can find more information in the (very old) User Guide [ps.gz] [pdf]. Note: The User Guide refers to the March 2001 version of the FGL; it has not been updated to reflect the extensions and changes of the current version.

The previous versions of the FGL can be accessed here: June 2008 version, May 2008 version, April 2007 version, June 2006 version, February 2005 version, January 2004 version, September 2002 version.

The library contains not just a couple of graph algorithms, but rather builds upon a functional view of graphs and graph algorithms. This view is motivated and explained in the paper Inductive Graphs and Functional Graph Algorithms.

Please send questions, comments, and bug reports to Martin Erwig.