Labeled graphs in fgl
lemming at henning-thielemann.de
Thu Feb 14 05:32:16 EST 2008
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.
More information about the Libraries