NonEmpty AdjacencyIntMaps

[jitwit]

Adding modules for NAIMs

I was having problems in the test suite with reachable about couldn't match type ToVertex AIM with type Int so I commented it out for now.

I changed the complexity comments for vertexCount/edgeCount in AIM, which claimed O(1).

Hopefully not too many names in the documentation are out of sync!

[snowleopard]

@jitwit Thanks for doing this! I'm a bit terrified about the combinatorial explosion in modules but no idea what to do about it :)

[jitwit]

Yeah, the explosion is a bit horrifying. Is that part of why no AdjacencyHashMap type modules are supported?

[snowleopard]

@jitwit Yep. At some point, I also had a representation based on arrays but then deleted it too.

[jitwit]

Hi and sorry for the MASSIVE delay, I finally returned to this! Hope all is well. I resolved some merge conflicts and added the last comments you made about the plan for generic tests to test/Algebra/Graph/Test/API.hs

[snowleopard]

@jitwit Hey, welcome back! All is good and I hope you're good too. Nice new avatar 👍

The plan looks fine to me, looking forward to future commits :)

[jitwit]

Things are still good here, too. Thanks!

[zyklotomic]

Hi, I was wondering what the current status of this PR is.

I realized that AdjacencyIntMaps don't have an scc algorithm, which led me to realizing NonEmpty AdjacencyIntMaps were missing too.

Should I try to submit a PR for IntMap scc? It would basically be similar in nature to this PR, copying the code from the regular AdjacencyMap.

Thanks!

[snowleopard]

@zyklotomic Hi there! I think @jitwit run out of steam a bit, so it would be great if you could help.

Let's give @jitwit a week to comment. If we don't hear back from him, I think it would be fine to create a new PR, keeping all the commits from this PR and their authorship, and then fixing the remaining issues. I'm happy to review.

[zyklotomic]

@snowleopard

I was trying to continue the work mentioned in the thread above https://github.com/snowleopard/alga/pull/250#discussion_r371318553 .

If I understand correctly about extending the test API, we would want to add the field

overlays1 :: forall a. c a => NonEmpty (g a) -> g a

which should be analogous to the existing

overlays :: forall a. c a => [g a] -> g a

Furthermore, I interpreted your plan as that we should be adding API's for other types of graphs. I started with nonEmptyAdjacencyMapAPI :: API NAM.AdjacencyMap Ord where NAM is the NonEmpty Adjacency Map module, and found an issue with implementing the API field for overlays. I can't think of a way that makes sense, since the type [g a] doesn't guarantee that the list will be non-empty.

I think we do in fact need ToGraph instances, because some API entries would be more conveniently implemented using ToGraph, for example isTopSortOf = ToGraph.isTopSortOf.

I am not sure if I understood your plan correctly, let me know if I have misunderstood it. Thanks!

[snowleopard]

@zyklotomic I think you understood the plan correctly. However, implementing a non-generic version of the testsuite for the new module should be OK too: as long as every property we promise in comments is tested, I will be happy :) So, feel free to test some (or all?) of the properties directly, without trying to be too generic. (I admit I might have overengineered the testsuite quite a bit...)

However, since this is all still going to be quite a lot of work, I'd like us to take a step back and think: is adding AdjacencyIntMap.NonEmpty really worth it in the end? This library is already hard to navigate because of so many similar APIs: empty/non-empty, Int/generic, algebraic/Map-based etc.

If I recall correctly, your specific motivation for doing this was the scc function, so here are two questions:

• Could you perhaps use AdjacencyMap instead of AdjacencyIntMap? Is the performance boost you get from IntMaps really that important for your application?
• If the answer to the above is "yes, I really need the performance of IntMaps": perhaps, it would be better to invest our efforts into making AdjacencyMaps map faster, for example, by implementing them with IntMaps with some auxiliary Int/a mapping.

I am a bit unhappy with how the library looks at the moment (it's way too complex) and I think adding more APIs may be a step in the wrong direction. So, it'd be really interesting to learn more about your motivation/use-case.

[zyklotomic]

I have already been using an auxiliary mapping due to space complexity reasons. Performance boost isn't super important.

If you are interested, I used scc here. I was trying to write a heap analysis of the GHC runtime. I used scc to compress cycles in the heap reference graph into one representative node.

The only reason why I thought to add it was because it was missing. I do agree that the library is a bit complex. In my experience, it is because of the inconsistencies (such as scc not being available for IntMaps). Having to select a specific graph "backend" such as AdjacencyMap was confusing. It is still a really enjoyable library to use nonetheless.

[snowleopard]

If you are interested, I used scc here. I was trying to write a heap analysis of the GHC runtime. I used scc to compress cycles in the heap reference graph into one representative node.

Wow, that's very cool! Best wishes with finishing this project.

I do agree that the library is a bit complex. In my experience, it is because of the inconsistencies (such as scc not being available for IntMaps). Having to select a specific graph "backend" such as AdjacencyMap was confusing.

Yes, I agree with you. I'd love to have consistency, but it seems almost unreachable in practice because of so many different combinations of graph flavours. It's very hard to implement, document, test and maintain all of these combinations. I'll try to find a way around that, hopefully soon.