alga icon indicating copy to clipboard operation
alga copied to clipboard

Published 20 hours ago • verified publisher icon snowleopard

Implement connectedComponents and isConnected

Open Synthetica9 opened this issue 6 years ago • 3 comments

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

Synthetica9 avatar Jun 19 '19 21:06 Synthetica9

@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!

snowleopard avatar Jun 19 '19 23:06 snowleopard

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 :)

bolt12 avatar Jun 20 '19 01:06 bolt12

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

snowleopard avatar Sep 10 '19 19:09 snowleopard