breadth-first search algorithm for solving set of logic equations

I am trying to conceive a solution for problems like in the following example:

A != B
B != C
D != B
C != B
E != D
E != A

开发者_如何学PythonHow many variables are true and how many are false? As far as I found out I should try to use breadth-first search, but my problem is where to start and the fact that the graph will be an oriented one (I am connecting xi to !xj where the equality relation exists). Can someone point me in the right direction?

It's a graph 2-coloring problem. Vertices: A, B, C, … Edge (u, v) in this undirected graph is present if and only if u != v.

2-coloring is one of the applications of the breadth-first search. See: http://en.wikipedia.org/wiki/Breadth-first_search#Testing_bipartiteness

I don't think you need search at all here. Consider your constraints as a graph connecting vertices xi and xj iff there is a constraint xi = !xj. Take a connected component of the graph (i.e., one where a path exists connecting every pair of vertices). Assuming your constraints are consistent (i.e., don't simultaneously specify xi = xj and xi = !xj) then you can pick any vertex xi in the component and immediately work out whether any connected vertex xj is equal to xi or !xi. It's then straightforward to work out the assignments you need to maximise or minimise the number of true variables.