logicaffeine_proof/
twosat.rs1#[derive(Clone, Copy, Debug, PartialEq, Eq)]
13pub struct Lit {
14 pub var: usize,
16 pub pos: bool,
18}
19
20impl Lit {
21 pub fn pos(var: usize) -> Self {
23 Lit { var, pos: true }
24 }
25 pub fn neg(var: usize) -> Self {
27 Lit { var, pos: false }
28 }
29}
30
31#[derive(Clone, Debug, PartialEq, Eq)]
33pub enum TwoSatOutcome {
34 Sat(Vec<bool>),
36 Unsat(usize),
39}
40
41#[inline]
43fn node(l: Lit) -> usize {
44 2 * l.var + l.pos as usize
45}
46#[inline]
47fn neg_node(n: usize) -> usize {
48 n ^ 1
49}
50
51fn dfs1(v: usize, adj: &[Vec<usize>], visited: &mut [bool], order: &mut Vec<usize>) {
52 visited[v] = true;
53 for &u in &adj[v] {
54 if !visited[u] {
55 dfs1(u, adj, visited, order);
56 }
57 }
58 order.push(v);
59}
60
61fn dfs2(v: usize, radj: &[Vec<usize>], comp: &mut [usize], c: usize) {
62 comp[v] = c;
63 for &u in &radj[v] {
64 if comp[u] == usize::MAX {
65 dfs2(u, radj, comp, c);
66 }
67 }
68}
69
70pub fn solve(clauses: &[(Lit, Lit)], num_vars: usize) -> TwoSatOutcome {
73 let nn = 2 * num_vars;
74 let mut adj = vec![Vec::new(); nn];
75 let mut radj = vec![Vec::new(); nn];
76 let mut edge = |from: usize, to: usize| {
77 adj[from].push(to);
78 radj[to].push(from);
79 };
80 for &(a, b) in clauses {
81 if a.var >= num_vars || b.var >= num_vars {
82 continue;
83 }
84 edge(neg_node(node(a)), node(b));
86 edge(neg_node(node(b)), node(a));
87 }
88 let mut visited = vec![false; nn];
90 let mut order = Vec::with_capacity(nn);
91 for v in 0..nn {
92 if !visited[v] {
93 dfs1(v, &adj, &mut visited, &mut order);
94 }
95 }
96 let mut comp = vec![usize::MAX; nn];
97 let mut c = 0;
98 for &v in order.iter().rev() {
99 if comp[v] == usize::MAX {
100 dfs2(v, &radj, &mut comp, c);
101 c += 1;
102 }
103 }
104 for v in 0..num_vars {
106 if comp[2 * v] == comp[2 * v + 1] {
107 return TwoSatOutcome::Unsat(v);
108 }
109 }
110 let assignment = (0..num_vars)
112 .map(|v| comp[node(Lit::pos(v))] > comp[node(Lit::neg(v))])
113 .collect();
114 TwoSatOutcome::Sat(assignment)
115}
116
117pub fn satisfies(clauses: &[(Lit, Lit)], assignment: &[bool]) -> bool {
119 let holds = |l: Lit| l.var < assignment.len() && assignment[l.var] == l.pos;
120 clauses.iter().all(|&(a, b)| holds(a) || holds(b))
121}
122
123pub fn is_refutation(clauses: &[(Lit, Lit)], num_vars: usize, var: usize) -> bool {
126 if var >= num_vars {
127 return false;
128 }
129 let nn = 2 * num_vars;
130 let mut adj = vec![Vec::new(); nn];
131 for &(a, b) in clauses {
132 if a.var < num_vars && b.var < num_vars {
133 adj[neg_node(node(a))].push(node(b));
134 adj[neg_node(node(b))].push(node(a));
135 }
136 }
137 let reaches = |from: usize, to: usize| {
138 let mut seen = vec![false; nn];
139 let mut stack = vec![from];
140 seen[from] = true;
141 while let Some(u) = stack.pop() {
142 if u == to {
143 return true;
144 }
145 for &w in &adj[u] {
146 if !seen[w] {
147 seen[w] = true;
148 stack.push(w);
149 }
150 }
151 }
152 from == to
153 };
154 let xt = node(Lit::pos(var));
155 let xf = node(Lit::neg(var));
156 reaches(xt, xf) && reaches(xf, xt)
157}
158
159#[cfg(test)]
160#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/twosat/tests.rs"]
161mod tests;