Labeled graphs in fgl

[Christian Maeder]

Henning Thielemann wrote:
> 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.

Interesting, the nodeLabel bit looks good (although I would use a "Map i
nodeLabel"). Considering that "Gr i" is also implemented as something
like "Map i <Context>" the structure is already duplicated, although
keeping the separate node labels in sync is fairly easy and maybe the
price for the added value (namely node labels).

In particular during decomposing the graph the node-label-map does not
need to be changed (although lookups may be faster in smaller maps).

W.r.t edge labels more needs to be done:
 1. there may be several edges between a node pair
 2. Getting a whole context (all in- and outgoing labelled edges) of a
node is less efficient (as you said above)
 3. Some identity of edges (i.e. a unique number, apart from the label)
is desirable, to locate or (re-)insert/delete certain edges.

W.r.t to the fgl-Design I would more complain about the many type
synonyms for tuples instead of using new (algebraic data) types.

Also wrapper types are an idea to keep the general implementation but
present a simplified interface to users of unlabeled graphs.

Cheers Christian