Labeled graphs in fgl

[Henning Thielemann]

On Thu, 14 Feb 2008, Christian Maeder wrote:

> Henning Thielemann wrote:
> > '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.
>
> I agree that Ix (or only Ord) may be desirable as node types, but still
> some applications may need more sophisticated labels
> or may want to change the labels associated to nodes.

No problem. If the node labels are in a separate array you can even do
in-place updates in ST monad.

> For these cases I don't see how you get rid of specializations to "()"
> without duplicating the library.

The library could provide a record like

   LabeledGraph i nodeLabel edgeLabel =
      LG (Gr i) (Array i nodeLabel) (Map (i,i) edgeLabel)

  with the interface that is now used for (Graph gr).
 However, I suspect that finding the label for an edge is then less
efficient then now.