[Java] Satisfiability of equations

Given a series of equality and inequality equations, determine whether they can be satisfied.

Equations are in the form:

a==b

a!=b

where a,b are the two variables involved.

Example:

a==b, b==c, c==a: OK

a==b, b==c, c!=a: KO

Similar to the graph coloring we saw before, we can apply the same method here but expand it to more colors.

We create an adjacency list from all equality equations, the linked variables (connected components) must all have the same color, we proceed by starting with a color and then assigning it to all variables connected to each other, we repeat this process for all variables without color, each time using a different color.

Then we parse all inequality equations and verify if any conflict arises.

This algorithm runs in O(V) space and O(E) time as we explore all edges (equations) once. We use V space for the stack when coloring as at most we can add each vertex only once (we only add if vertex has no color).

You can check my implementation of equationsPossible on my Gist along with some tests in EquationsPossibleJTests.