use super::{NONE, VertexId};
use crate::linear::occurrences::{Forest, OccId, OccSet};
use crate::linear::sequents::Kind;
#[derive(Clone, Debug)]
pub(super) struct Graph {
start: Box<[u32]>,
to: Box<[u32]>,
switched_tree_edges: usize,
vertices: usize,
}
#[derive(Clone, Debug)]
pub struct Scratch {
deleted: OccSet,
stuck: OccSet,
removed: Box<[bool]>,
disc: Box<[u32]>,
low: Box<[u32]>,
dfs_parent: Box<[u32]>,
bridge: Box<[bool]>,
component: Box<[u32]>,
stack: Vec<(u32, u32)>,
}
impl Scratch {
fn new(graph: &Graph) -> Self {
let n = graph.start.len() - 1;
Self {
deleted: OccSet::empty(n),
stuck: OccSet::empty(n),
removed: vec![false; graph.to.len()].into_boxed_slice(),
disc: vec![NONE; n].into_boxed_slice(),
low: vec![NONE; n].into_boxed_slice(),
dfs_parent: vec![NONE; n].into_boxed_slice(),
bridge: vec![false; n].into_boxed_slice(),
component: vec![NONE; n].into_boxed_slice(),
stack: Vec::with_capacity(n),
}
}
pub(super) fn fits(&self, graph: &Graph) -> bool {
self.removed.len() == graph.to.len() && self.disc.len() == graph.len()
}
fn is_deleted(&self, v: u32) -> bool {
self.deleted.contains(OccId::new(v))
}
pub(super) fn restore(&mut self) {
self.deleted.clear();
}
pub(super) fn delete(&mut self, v: OccId) {
self.deleted.insert(v);
}
pub(super) fn reached(&self, v: OccId) -> bool {
self.disc[v.index()] != NONE
}
pub(super) fn component(&self, v: OccId) -> OccId {
OccId::new(self.component[v.index()])
}
pub(super) fn is_bridge(&self, v: u32, w: u32) -> bool {
debug_assert!(
self.reached(OccId::new(v)) && self.reached(OccId::new(w)),
"the last search did not reach both ends"
);
(self.dfs_parent[w as usize] == v && self.bridge[w as usize])
|| (self.dfs_parent[v as usize] == w && self.bridge[v as usize])
}
}
impl Graph {
pub(super) fn new(
forest: &Forest,
live: Option<&OccSet>,
cuts: &[(VertexId, VertexId)],
) -> Self {
let n = forest.len();
let mut start = Vec::with_capacity(n + 1);
let mut to = Vec::with_capacity(3 * n);
let mut switched_tree_edges = cuts.len();
let mut across = Vec::new();
if !cuts.is_empty() {
across = vec![NONE; n];
for &(x, y) in cuts {
across[x.index()] = y.get();
across[y.index()] = x.get();
}
}
let mut vertices = 0;
for o in forest.ids() {
start.push(to.len() as u32);
if live.is_some_and(|live| !live.contains(o)) {
continue;
}
vertices += 1;
match across.get(o.index()) {
Some(&end) if end != NONE => to.push(end),
_ => {
if let Some(p) = forest.parent(o) {
to.push(p.get());
}
}
}
to.extend(forest.children(o).map(OccId::get));
match forest.kind(o) {
Kind::Tensor => switched_tree_edges += 2,
Kind::Par => switched_tree_edges += 1,
Kind::Atom
| Kind::DualAtom
| Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::With
| Kind::Plus
| Kind::Bang
| Kind::Quest
| Kind::Forall
| Kind::Exists => to.push(NONE),
}
}
start.push(to.len() as u32);
Self {
start: start.into_boxed_slice(),
to: to.into_boxed_slice(),
switched_tree_edges,
vertices,
}
}
pub(super) fn vertices(&self) -> usize {
self.vertices
}
pub(super) fn scratch(&self) -> Scratch {
Scratch::new(self)
}
fn len(&self) -> usize {
self.start.len() - 1
}
fn slots(&self, v: u32) -> std::ops::Range<usize> {
self.start[v as usize] as usize..self.start[v as usize + 1] as usize
}
fn axiom_slot(&self, l: u32) -> usize {
self.start[l as usize + 1] as usize - 1
}
fn twin(&self, v: u32, w: u32) -> usize {
self.slots(w)
.find(|&s| self.to[s] == v)
.expect("the edge exists at both ends")
}
pub(super) fn link(&mut self, x: u32, y: u32) {
self.to[self.axiom_slot(x)] = y;
self.to[self.axiom_slot(y)] = x;
}
pub(super) fn unlink(&mut self, x: u32, y: u32) {
self.to[self.axiom_slot(x)] = NONE;
self.to[self.axiom_slot(y)] = NONE;
}
pub(super) fn remove_cut(&self, scratch: &mut Scratch, x: u32) {
let slot = self.slots(x).start;
let y = self.to[slot];
let twin = self.twin(x, y);
scratch.removed[slot] = true;
scratch.removed[twin] = true;
}
pub(super) fn switched_edges(&self, links: usize) -> usize {
self.switched_tree_edges + links
}
pub(super) fn search(
&self,
scratch: &mut Scratch,
roots: impl IntoIterator<Item = u32>,
) -> u32 {
debug_assert_eq!(
scratch.removed.len(),
self.to.len(),
"a scratch of another graph"
);
scratch.disc.fill(NONE);
let mut time = 0;
let mut trees = 0;
for r in roots {
if scratch.is_deleted(r) || scratch.disc[r as usize] != NONE {
continue;
}
trees += 1;
self.discover(scratch, r, NONE, r, &mut time);
while let Some(&(v, next)) = scratch.stack.last() {
if next < self.start[v as usize + 1] {
scratch.stack.last_mut().unwrap().1 = next + 1;
let w = self.to[next as usize];
if w == NONE
|| scratch.removed[next as usize]
|| scratch.is_deleted(w)
|| w == scratch.dfs_parent[v as usize]
{
continue;
}
if scratch.disc[w as usize] == NONE {
self.discover(scratch, w, v, r, &mut time);
} else {
let (lv, dw) = (scratch.low[v as usize], scratch.disc[w as usize]);
scratch.low[v as usize] = lv.min(dw);
}
} else {
scratch.stack.pop();
let p = scratch.dfs_parent[v as usize];
if p != NONE {
let (lp, lv) = (scratch.low[p as usize], scratch.low[v as usize]);
scratch.low[p as usize] = lp.min(lv);
scratch.bridge[v as usize] = lv > scratch.disc[p as usize];
}
}
}
}
trees
}
fn discover(&self, scratch: &mut Scratch, v: u32, parent: u32, root: u32, time: &mut u32) {
scratch.disc[v as usize] = *time;
scratch.low[v as usize] = *time;
*time += 1;
scratch.dfs_parent[v as usize] = parent;
scratch.component[v as usize] = root;
scratch.bridge[v as usize] = false;
scratch.stack.push((v, self.start[v as usize]));
}
fn deletable(&self, forest: &Forest, scratch: &Scratch, v: u32) -> bool {
let present = |s: usize| {
let w = self.to[s];
w != NONE && !scratch.removed[s] && !scratch.is_deleted(w)
};
if forest.kind(OccId::new(v)) == Kind::Par {
let slots = self.slots(v);
slots.len() < 3 || !present(slots.start) || scratch.is_bridge(v, self.to[slots.start])
} else {
self.slots(v)
.all(|s| !present(s) || scratch.is_bridge(v, self.to[s]))
}
}
pub(super) fn acyclic(
&self,
forest: &Forest,
scratch: &mut Scratch,
stop: &mut dyn FnMut(u64) -> bool,
) -> Option<bool> {
let n = self.len();
let mut remaining = n - scratch.deleted.len();
while remaining > 0 {
if stop(1) {
return None;
}
self.search(scratch, 0..n as u32);
let before = remaining;
for v in 0..n as u32 {
if !scratch.is_deleted(v) && self.deletable(forest, scratch, v) {
scratch.delete(OccId::new(v));
remaining -= 1;
}
}
if remaining == before {
return Some(false);
}
}
Some(true)
}
pub(super) fn cycle(
&self,
forest: &Forest,
scratch: &mut Scratch,
stop: &mut dyn FnMut(u64) -> bool,
) -> Option<Vec<VertexId>> {
let n = self.len();
scratch.stuck.clone_from(&scratch.deleted);
for v in 0..n as u32 {
for s in self.slots(v) {
let w = self.to[s];
if w == NONE
|| w < v
|| scratch.removed[s]
|| scratch.stuck.contains(OccId::new(v))
|| scratch.stuck.contains(OccId::new(w))
{
continue;
}
let t = self.twin(v, w);
scratch.removed[s] = true;
scratch.removed[t] = true;
scratch.deleted.clone_from(&scratch.stuck);
let Some(acyclic) = self.acyclic(forest, scratch, stop) else {
scratch.removed.fill(false);
return None;
};
if acyclic {
scratch.removed[s] = false;
scratch.removed[t] = false;
} else {
scratch.stuck.clone_from(&scratch.deleted);
}
}
}
let first = (0..n as u32)
.find(|&v| !scratch.stuck.contains(OccId::new(v)))
.expect("a switching cycle is left");
let mut cycle = Vec::new();
let (mut previous, mut current) = (NONE, first);
loop {
cycle.push(VertexId(current));
let next = self
.slots(current)
.map(|s| (s, self.to[s]))
.find(|&(s, w)| {
w != NONE
&& w != previous
&& !scratch.removed[s]
&& !scratch.stuck.contains(OccId::new(w))
})
.map(|(_, w)| w)
.expect("every vertex of the cycle has two edges on it");
if next == first {
break;
}
(previous, current) = (current, next);
}
scratch.removed.fill(false);
Some(cycle)
}
pub(super) fn parts(&self, forest: &Forest, scratch: &mut Scratch) -> Vec<Vec<VertexId>> {
let n = self.len();
scratch.restore();
let vertex = |o: OccId| !self.slots(o.get()).is_empty();
for p in forest
.ids()
.filter(|&p| forest.kind(p) == Kind::Par && vertex(p))
{
let r = forest.right(p).unwrap();
scratch.removed[self.twin(r.get(), p.get())] = true;
scratch.removed[self.slots(r.get()).start] = true;
}
self.search(scratch, 0..n as u32);
scratch.removed.fill(false);
let mut parts: Vec<(u32, Vec<VertexId>)> = Vec::new();
for v in forest.ids().filter(|&v| vertex(v)) {
let cut = match forest.parent(v) {
None => forest.dual(v).is_none_or(|d| v < d),
Some(p) if !vertex(p) => forest.dual(v).is_some_and(|d| v < d),
Some(p) => forest.kind(p) == Kind::Par && forest.right(p) == Some(v),
};
if !cut {
continue;
}
let label = scratch.component[v.index()];
match parts.iter_mut().find(|(l, _)| *l == label) {
Some((_, part)) => part.push(VertexId::of(v)),
None => parts.push((label, vec![VertexId::of(v)])),
}
}
parts.sort_by_key(|(label, _)| *label);
parts.into_iter().map(|(_, part)| part).collect()
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::super::{Criterion, NetError, ProofStructure, VertexId};
use crate::linear::occurrences::{Forest, OccId};
use crate::linear::search::generate::{self, Rng, Rules};
use crate::linear::sequents::{Kind, Sequent};
const fn v(id: u32) -> VertexId {
VertexId::new(id)
}
fn net(input: &str, mix: bool, links: &[(u32, u32)]) -> ProofStructure {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
let links: Vec<(VertexId, VertexId)> = links.iter().map(|&(x, y)| (v(x), v(y))).collect();
ProofStructure::from_links(
Forest::new(&s).unwrap(),
Criterion {
mix,
..Criterion::MLL
},
&links,
)
.unwrap()
}
#[expect(
clippy::wildcard_enum_match_arm,
reason = "a structure of MLL has no other parent"
)]
fn enumerate(net: &ProofStructure) -> (bool, bool) {
let f = net.forest();
let pars: Vec<OccId> = f.ids().filter(|&p| f.kind(p) == Kind::Par).collect();
assert!(pars.len() <= 16, "too many switchings to enumerate");
let (mut acyclic, mut connected) = (true, true);
for switching in 0..1u32 << pars.len() {
let keeps_left = |p: OccId| {
let i = pars.iter().position(|&q| q == p).unwrap();
switching & (1 << i) == 0
};
let mut parent: Vec<usize> = (0..f.len()).collect();
fn find(parent: &mut [usize], mut x: usize) -> usize {
while parent[x] != x {
x = parent[x];
}
x
}
let mut components = f.len();
let mut cyclic = false;
let mut join = |x: OccId, y: OccId| {
let (a, b) = (find(&mut parent, x.index()), find(&mut parent, y.index()));
if a == b {
cyclic = true;
} else {
parent[a] = b;
components -= 1;
}
};
for v in f.ids() {
if let Some(p) = f.parent(v) {
let kept = match f.kind(p) {
Kind::Tensor => true,
Kind::Par => keeps_left(p) == (f.left(p) == Some(v)),
_ => unreachable!(),
};
if kept {
join(p, v);
}
}
}
for &(x, y) in net.links() {
join(x.occ(), y.occ());
}
acyclic &= !cyclic;
connected &= components == 1;
}
(acyclic, connected)
}
fn check_cycle(net: &ProofStructure, cycle: &[VertexId]) {
let f = net.forest();
let cycle: Vec<OccId> = cycle.iter().map(|v| v.occ()).collect();
assert!(cycle.len() >= 3, "{cycle:?}");
let mut sorted = cycle.clone();
sorted.sort();
sorted.dedup();
assert_eq!(sorted.len(), cycle.len(), "simple: {cycle:?}");
for i in 0..cycle.len() {
let (a, b, c) = (
cycle[(i + cycle.len() - 1) % cycle.len()],
cycle[i],
cycle[(i + 1) % cycle.len()],
);
let adjacent = f.parent(b) == Some(c)
|| f.parent(c) == Some(b)
|| net.partner(VertexId::of(b)) == Some(VertexId::of(c));
assert!(adjacent, "{b:?} and {c:?} are not adjacent in {cycle:?}");
if f.kind(b) == Kind::Par {
assert!(
f.parent(a) != Some(b) || f.parent(c) != Some(b),
"{cycle:?} passes {b:?} through both premises"
);
}
}
}
#[test]
fn classic_structures() {
assert_eq!(
net("A, A -o B |- B", false, &[(0, 2), (3, 4)]).is_correct(|_| false),
Ok(())
);
let partial = net("A, A -o B |- B", false, &[(0, 2)]);
assert_eq!(
partial.is_correct(|_| false),
Err(NetError::Unlinked { vertex: v(4) })
);
assert!(partial.is_acyclic(&mut partial.scratch()));
let cyclic = net("|- A * ~A", true, &[(1, 2)]);
let Err(NetError::SwitchingCycle { cycle }) = cyclic.is_correct(|_| false) else {
panic!("a link below a ⊗ is a switching cycle");
};
check_cycle(&cyclic, &cycle);
assert_eq!(cycle, [v(0), v(1), v(2)]);
assert!(!cyclic.is_acyclic(&mut cyclic.scratch()));
assert_eq!(
net("|- A par ~A", false, &[(1, 2)]).is_correct(|_| false),
Ok(())
);
assert_eq!(
net("|- A par B, ~A, ~B", false, &[(1, 3), (2, 4)]).is_correct(|_| false),
Err(NetError::Disconnected {
parts: vec![vec![v(0), v(3)], vec![v(2), v(4)]]
})
);
assert_eq!(
net("|- A par B, ~A, ~B", true, &[(1, 3), (2, 4)]).is_correct(|_| false),
Ok(())
);
assert_eq!(
net("|- (A par ~A) par (B par ~B)", false, &[(2, 3), (5, 6)]).is_correct(|_| false),
Err(NetError::Disconnected {
parts: vec![vec![v(0), v(3)], vec![v(4), v(6)]]
})
);
let cyclic = net("|- A * B, ~A * ~B", true, &[(1, 4), (2, 5)]);
let Err(NetError::SwitchingCycle { cycle }) = cyclic.is_correct(|_| false) else {
panic!("two tensors joined twice are a switching cycle");
};
check_cycle(&cyclic, &cycle);
assert_eq!(cycle.len(), 6);
assert_eq!(
net("|-", true, &[]).is_correct(|_| false),
Err(NetError::Empty)
);
}
#[test]
fn agrees_with_enumeration() {
let mut cases = (0, 0, 0);
for (seed, mix) in [(1, false), (2, true)] {
let mut rng = Rng::new(seed);
for i in 0..200 {
let rules = Rules {
units: false,
additives: false,
mix: i % 3 == 2,
exponentials: false,
};
let budget = 2 + rng.below(9);
let mut formulas = generate::provable(&mut rng, rules, 3, budget).formulas;
if i % 2 == 1 {
generate::mutate(&mut rng, &mut formulas, 3);
}
let text = generate::sequent(&formulas);
let s: Sequent = text.parse().unwrap();
let forest = Forest::new(&s).unwrap();
let mut pairs = Vec::new();
for a in 0..s.atom_names().len() {
let atom = crate::linear::sequents::Atom::new(a as u32);
let vars = forest.literals(atom, crate::linear::occurrences::Sign::Atom);
let mut duals = forest
.literals(atom, crate::linear::occurrences::Sign::Dual)
.to_vec();
for k in (1..duals.len()).rev() {
duals.swap(k, rng.below(k + 1));
}
pairs.extend(vars.iter().copied().zip(duals));
}
for k in (1..pairs.len()).rev() {
pairs.swap(k, rng.below(k + 1));
}
let mut net = ProofStructure::new(
forest,
Criterion {
mix,
..Criterion::MLL
},
)
.unwrap();
let mut scratch = net.scratch();
for &(x, y) in &pairs {
net.link(VertexId::of(x), VertexId::of(y)).unwrap();
let (acyclic, _) = enumerate(&net);
assert_eq!(
net.is_acyclic(&mut scratch),
acyclic,
"{text:?} with {:?}",
net.links()
);
}
let (acyclic, connected) = enumerate(&net);
let verdict = net.is_correct(|_| false);
let expected =
!net.forest().is_empty() && net.is_complete() && acyclic && (mix || connected);
assert_eq!(
verdict.is_ok(),
expected,
"{text:?} with {:?}: {verdict:?}",
net.links()
);
match &verdict {
Ok(()) => cases.0 += 1,
Err(NetError::SwitchingCycle { cycle }) => {
check_cycle(&net, cycle);
cases.1 += 1;
}
Err(NetError::Disconnected { parts }) => {
let f = net.forest();
let switched = f.ids().filter(|&v| f.kind(v) == Kind::Tensor).count() * 2
+ f.ids().filter(|&v| f.kind(v) == Kind::Par).count()
+ net.links().len();
assert_eq!(parts.len(), f.len() - switched, "{text:?}");
for &r in f.roots() {
assert_eq!(
parts
.iter()
.filter(|p| p.contains(&VertexId::of(r)))
.count(),
1,
"{text:?}"
);
}
cases.2 += 1;
}
Err(NetError::Unlinked { .. }) => {}
Err(e) => panic!("{text:?}: {e}"),
}
}
}
assert!(cases.0 > 20 && cases.1 > 20 && cases.2 > 5, "{cases:?}");
}
}