Labelled graphs in fgl

[Henning Thielemann]

On Thu, 14 Feb 2008, Christian Maeder wrote:

> Henning Thielemann wrote:
> > Is there a reason why graphs in fgl are labeled by default, and unlabelled
> > graphs must be constructed by labeling with () ? In my opinion the more
> > natural design would be to number the nodes and edges with an Enum type
> > instead of Int and to retrieve the labels from an array. This would
> > support the "from simple to complex" design.
>
> The design of the fgl could be improved. Labels for nodes (only) are
> (also) supported by Data.Graph.Inductive.NodeMap.

I was not aware of NodeMap so far. It seems to add a mapping from labels
to nodes, whereas node labels (that is mappings from Node to a Label of
arbitrary type) are already provided by the
Data.Graph.Inductive.Graph.Graph type constructor class and the type
concrete Data.Graph.Inductive.Tree.Gr type constructor. A graph type is
'gr a b', but 'a' is not an index type. The nodes are indexed by Node
which is a synonym for Int. For the tasks I had so far there was no need
for the label type 'a', I just needed a more specific index type than Node
(=Int), say an enumeration.
 The library designer seems to appreciate that applications may not need
the labels, and provided functions like mkUGraph and type synonyms like
Data.Graph.Inductive.Tree.UGr = Gr () (), which seems for me the wrong way
around. It would be simple to add labels to an arbitrary indexed but
unlabeled graph, say Ix i => gr i.

> (Keeping just a list of edges makes it difficult - leaves it to the user
> - to find certain edges after insertions or deletions)