SCC condensation doesn't distinguish cyclic and acyclic single-node components

[michaelpj]

This can be very important. Data.Graph does it, it would be great if alga did too.

[snowleopard]

@michaelpj Indeed! I propose to modify the API with the following goals in mind:

1. Address this issue, i.e. make it easy to find out whether a component is acyclic.
2. Get rid of the invariant that the sets (i.e. vertices) in the resulting condensed graph are non-empty.
3. (Optional) Make it easy to extract the graphs corresponding to components, as discussed in Add isAcyclic, topSort, dfs and other graph analysis functions to ToGraph #105.

One option would be to use the SCC data type defined in Data.Graph, i.e. return AdjacencyMap (SCC a) from the function scc, but it's a bit awkward for two reasons: (i) SCC doesn't have an Ord instance, and (ii) it also comes with the invariant that the CyclicSCC list is non-empty.

Perhaps, we should define our own data SCC a = AcyclicSCC a | CyclicSCC (NonEmpty a) with an Ord instance?

This is still not ideal. I would prefer to have a non-empty set in the CyclicSCC constructor, but alas such sets are not provided by the containers library.

Thinking of (3), we could also switch to something like:

scc :: Ord a => AdjacencyMap a -> AdjacencyMap (NonEmptyGraph a)

Which I think ticks all the boxes, since we could then use isAcyclic on the resulting graphs.

Any other ideas?

[michaelpj]

I think modelling SCCs as non empty graphs would be great, since it even preserves the inner graph structure of the component if you want it.

More generally, if you had a graph model that includes subgraphs, you could model them as subgraphs.

[snowleopard]

Agree, this looks like the best option. I will give it a try in the next couple of days.

[snowleopard]

I've added a PR with a draft implementation: #130.

[snowleopard]

I've finally finished #130. It took a long time, because it triggered a wave of refactoring (#131, #136).

The resulting type signature is:

import           Algebra.Graph.AdjacencyMap
import qualified Algebra.Graph.NonEmpty.AdjacencyMap as NonEmpty

scc :: Ord a => AdjacencyMap a -> AdjacencyMap (NonEmpty.AdjacencyMap a)

@michaelpj Does this look good? You can now distinguish acyclic components simply by using isAcyclic on inner non-empty graphs, so I think this issue can be closed.

Feel free to reopen if I missed anything.

[michaelpj]

The interface looks great! I'll try and give it a spin later.

[snowleopard]

@michaelpj Thanks! I'd appreciate some feedback on the performance in your use case. I am a bit worried about using heavy-weight vertex types like NonEmpty.AdjacencyMap due to their expensive Ord instance. I've created #141 to track this.

[michaelpj]

I'm not using it in a performance-sensitive context, but I'll keep you posted.