LabelledAdjacencyMap?

[o1lo01ol1o]

I have a case where I need to model a graph (of labeled edges) via an adjacency map representation (I need, among other things, to sort the graphs topologically and compute the cycles via scc). It looks like the Diode (Set e) would take care of the labeling issue (my labels function only as edge identifiers) but I'm not sure what the best representation would be for the adjacency map itself given that I also need a King-Launchbury representation if I'm to avoid writing the sorts myself. Could anyone advise?

[snowleopard]

Hi @o1lo01ol1o!

I think the implementation will be pretty similar to Algebra.Graph.AdjacencyMap but instead of

Map a (Set a)

the labelled version will use

Map a (Map a e)

as the underlying data structure (with edge labels of type e).

If you don't want to use dioids for labelling, then here is an alternative:

Map a (Set (a, e))

Now instead of collapsing parallel edges using one of dioid's operations, you explicitly store each edge separately.

The former seems a bit more general, since one can always pick e = Set e' and obtain the latter.

Would you like to give it a try?

[o1lo01ol1o]

Hi, thanks for the reply. I ended up with something similar to the latter in the interm. However, I I'll try to re-tailor my implementation and create a PR.

[snowleopard]

Thanks!

By the way, I think I was wrong in my previous comment when I said that one of the encodings is more general than the other -- they are actually equivalent in terms of generality. But one may be easier/faster to work with than the other.

[o1lo01ol1o]

See #113

[snowleopard]

After merging #113, we still need to do the following:

• Add conversions between labelled and unlabelled adjacency maps
• Improve documentation
• Add tests

[snowleopard]

I think we can close this issue. See the module here:

https://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-Labelled-AdjacencyMap.html