Implement connectedComponents and isConnected

Synthetica9 commented 5 years ago

Based on #196.

I derived my own algorithm to get the connected components directly from the graph's structure. I'm not 100% on the complexity of it.

I'm also not 100% sure where these functions should go. They are intended for general graphs, but we can guarantee that every component isn't empty.

~~Also, there doesn't seem to be a place to put small tools that might be useful elsewhere, am I overlooking this?~~ I was! src/Algebra/Graph/Internal.hs

cc @bolt12 ~~(Did you get to this already? I couldn't find you work anywhere)~~

TODO:

[ ] Set.disjoint turns out to be fairly new. Backport?
[ ] Determine complexity

snowleopard commented 5 years ago

@Synthetica9 Many thanks for the PR! I'm currently travelling and have a few other PRs to review, but I'll try to come back to you soon!

bolt12 commented 5 years ago

I did not had the opportunity to start working on this yet but since you presented your work I think the best thing is to use your code! Once I'm free from other academic tasks I can maybe we can go through this together :)

snowleopard commented 5 years ago

@Synthetica9 It's been a while -- have you had a chance to look at the comments above?

snowleopard / alga

Implement connectedComponents and isConnected #216

TODO: