TO DO (FGL/Haskell, Version: April 2000)
----------------------------------------

The current Haskell FGL version is still incomplete.  To make it a
usable library it has to be extended/revised along the following dimensions:

  (A) Design/Expressiveness/Completeness
  (B) Efficiency
  (C) Documentation
  (D) Tools

Below is a list of things that should be addressed.



(A) Design/Expressiveness/Completeness
--------------------------------------

(1) More algorithms

General-purpose Algorithms to be added:
* graph generators (in preparation)
* graph parsers (in preparation)
* maximum flow
* bi-connected components, articulation points
* dominators
* transitive closure & reduction
* traveling salesman (backtracking, branch and bound, MST approximation)
* ...

Applications:
* Functional Graph Reduction (in preparation)
* WWW-Site managing tools (in preparation)
* ...


(2) Other folds

Implement mfold, backtrack and possibly other graph fold operations (see
ICFP'97 paper).


(3) Integration of Active Patterns?

If we had active patterns available, algorithms could be specified highly
concisely and clearly.  Eg, if & is the infix version of embed, and &?  is
the corresponding active pattern, dfs would become:

dfs []    g                = []
dfs (v:l) ((p,v,a,s) &? g) = v:dfs (s++l) g
dfs (v:l) g                = dfs l g

However, integration of active patterns needs either an extension of
Haskell (not desirable?) or a kind of preprocessing transformation of
FGL-files containing active patterns.


(4) Thread vs. Monad

It seems that the Thread module can be replaced by suitable monads.
So this should be done.



(B) Efficiency
--------------

(1) Match/monadic gfold

The match operation is currently not really efficient since it has to build
a representation of the remaining graph.  This affects all algorithms that
are built using match.  Actually, these are almost all interesting,
non-trivial algorithms since match essentially embodies the idea of
inductive graphs and inductive graph algorithms.  In particular, dfs does
not have linear runtime (as in the ML version).  The problems is that we
cannot use the trick of using a cache array because this requires the use
of impure array update.  This cannot be remedied by using monads without
having to write all algorithms in monadic style, which I strongly deny
since it destroys the current flavor of the algorithms.

Efficiency can be recovered if algorithms are expressed with gfold and if
we provide a monadic implementation of gfold using an imperatively updated
array as in the ML version.
    

(2) Representation for dense graphs

Is it reasonable to include a two-dimensional array representation and to
define embed, match, etc for this?  I am not sure whether this really gains
anything in terms of efficiency.



(C) Documentation
-----------------

(1) Write a library report

Description of all modules, all data structures and functions together
with their efficiency, possible alternatives, and guidelines for choosing 
graph types and functions.



(D) Tools
---------

(1) GUI to construct graphs visually

(2) GUI to show results of graph operations (graphs, trees, node sets in 
context, etc)

(3) Active Patterns Preprocessor

(4) Gfold builder (a preprocessor that transforms graph algorithms written 
using match into an instance of gfold)

