I was reading about the 2-SAT problem on Wikipedia and I was wondering what the O(n) algorithm looks like in Python.
So far I've only found implementations that either are in other programming languages or that just determine whether an expression has solutions or not, without given the solution itself.
How could the O(n) algorithm for finding the values of variables be written in Python?
Here is an OOP implementation in Python:
Here is an example of how this class can be used:
The
TwoSat
constructor takes one argument, a string, which should provide the conjugation of disjunction pairs. The syntax rules for this string are:~
to denote negation.So the above example could also have taken this string representing the same problem:
Alternatively, you can use the
getvariable
anddisjunction
methods to build the expression. Look at the__init__
method how the constructor uses those methods when parsing the string. For example:The algorithm is the one explained in the 2-satisiability article on Wikipedia, identifying strongly connected components using Kosaraju's algorithm