How cool is that? – Tarjun’s SCC algorithm

by hobbitalastair

I worked through an implementation of a Tarjun’s SCC algorithm to solve a version of the 2SAT problem fairly recently, for an online course. It was a fairly complex assignment, with no real direct analogue for me, so it took a while to work through!

One thing I definitely did not expect was for it to have a direct practical application within a few months of completing my version. Given that we covered a wide range of algorithms, I would have thought one of the other ones that I had at least heard of before would have come up first!

Still, I’m glad I know about it. Strictly speaking, I could achieve the same purpose with a similar, simpler algorithm, but I gain a few nice ‘features’ with Tarjun’s SCC algorithm, and it can be implemented in linear time – which is surely a good thing. Plus, I’ll get to explore a practical application of it, which is always fun 🙂

“What practical application?” you may be asking. If you read this far, that is. It turns out that I’m solving a problem that can be expressed as a 2SAT problem in my SSS2 project. Specifically, I would like to have a set of files, each describing a ‘state’ (say, having mpv installed), which are either included, or not included. There can also be relationships between files – like “only install this configuration file if this program is installed”. Finally, there can be relationships between variables and files – “only install xf86-video-nouveau if ‘this machine runs X’ and ‘this machine has X installed'”. All of those relationships would, preferably, be able to be described by a logical statement, where all the variables are represented by files.

This is a 2SAT problem – each file is either ‘on’ or ‘off’ (true or false), and the relationships between the files use the standard logical operators. If I create an implication graph from the files, and then run Tarjun’s SCC, I can solve the problem, load all of the files that are ‘on’ into a single, combined ‘state’, and pass that to the rest of the program.

The above is a bit of a simplification, but that’s pretty much what will happen.

There are a few “limitations” with this approach:

  • Tarjun’s SCC is a bit of an overkill. I believe could actually implement a solution using DFS; however, Tarjun’s SSC does give me a bit more information, allowing me to set all unrestricted ‘states’ to ‘on’ as needed, for example.
  • I cannot generate requirements automatically. This is something that would be hard to remedy!
  • Variables are represented by ‘meta-files’. This is… imperfect. But it’s probably the easiest way.

Generally, though, I think it’ll be pretty flexible, and hopefully easy enough to write.

One design decision that I’m not completely sure about is how I’ll create the implication graph. My current idea is that each file will have at least two variables; IsAny and IsAnd. Both will be a list of other files, with Any translating to an “or” relationship, and And translating to an “and” relationship. I’m not sure whether I’ll have another couple of variables that are the Not equivalents, or whether I’ll just use an ‘!’ infront of the filenames. I’ll also need meta-files, which could get a bit messy… but I’m already doing that for groups, and the alternative is parsing a custom logic string, which sounds even more messy to me!