Hopcroft's Algorithm

hopcroft.rs

use std::collections::VecDeque;

// compute the inverse relation given a function
fn inverse_fn(n: usize, f: &Vec<usize>) -> Vec<Vec<usize>> {
    let mut inverse_f = vec![vec![]; n];
    for i in 0..n {
        inverse_f[f[i]].push(i);
    }
    inverse_f
}

fn hopcroft(n: usize, mut partition: Vec<usize>, f: &Vec<usize>) -> Vec<usize> {
    let inverse_f = inverse_fn(n, f);
    let mut blocks_count = partition.iter().max().unwrap() + 1;

    // invariant: on_worklist[i] iff i is in worklist
    let mut worklist = VecDeque::from((0..blocks_count).collect::<Vec<usize>>());
    let mut on_worklist = (0..n).map(|i| i < blocks_count).collect::<Vec<bool>>();

    while !worklist.is_empty(){
        // pop an element from the worklist
        let i : usize = worklist.pop_front().unwrap();
        on_worklist[i] = false;

        // compute the inverse image of the ith partition
        let inverse = (0..n).filter(|&x| partition[x] == i)
                            .map(|x| inverse_f[x].clone())
                            .flatten()
                            .collect::<Vec<usize>>();

        let size_of_partition = (0..n).fold(vec![0; blocks_count], |mut acc, x| {
            acc[partition[x]] += 1;
            acc
        });
        // size_of_inverse_in_block = cardinality of f^{-1}(B[i]) \cap B[j]
        let size_of_inverse_in_block = inverse.iter().fold(vec![0; blocks_count], |mut acc, &x| {
            acc[partition[x]] += 1;
            acc
        });

        for j in 0..blocks_count {
            if i == j || size_of_inverse_in_block[j] == 0 
            || size_of_inverse_in_block[j] == size_of_partition[j] { 
                continue; 
            }

            // move elements of B[j] \cap inverse to B[q + 1]
            blocks_count += 1;
            for &x in inverse.iter() {
                if partition[x] == j {
                    partition[x] = blocks_count - 1;
                }
            }

            if on_worklist[j] {
                worklist.push_back(blocks_count - 1);
                on_worklist[blocks_count - 1] = true;
            }
            else {
                // put the smaller of the two blocks on the worklist
                if size_of_inverse_in_block[j] < size_of_partition[j] - size_of_inverse_in_block[j] {
                    worklist.push_back(blocks_count - 1);
                    on_worklist[blocks_count - 1] = true;
                }
                else {
                    worklist.push_back(j);
                    on_worklist[j] = true;
                }
            }
            
        }

    }

    partition
}

// block1 is stable with respect to block2 if
// either block1 \cap f^{-1}(block2) = \emptyset
// or, block1 \subseteq f^{-1}(block2)
fn stable_wrt(n : usize, f : &Vec<usize>, block1 : &Vec<usize>, block2 : &Vec<usize>) -> bool {
    let inverse_f = inverse_fn(n, f);
    let block2inv = block2.clone().into_iter()
                          .map(|x| inverse_f[x].clone())
                          .flatten()
                          .collect::<Vec<usize>>();
    let block1_and_block2inv = block1.clone().into_iter()
                                     .filter(|&x| block2inv.contains(&x));
    let block1_in_block2inv = block1.clone().into_iter()
                                    .all(|x| block2inv.contains(&x));
    block1_and_block2inv.count() == 0 || block1_in_block2inv
}

// a partition is stable if every block is stable with respect to every other block
fn stable_partition(n : usize, f: &Vec<usize>, partition : &Vec<usize>) -> bool {
    let blocks = (0..n).fold(vec![vec![]; n], |mut acc, x| {
        acc[partition[x]].push(x);
        acc
    });
    let blocks = blocks.into_iter().filter(|x| x.len() > 0).collect::<Vec<Vec<usize>>>();
    blocks.iter().enumerate().all(|(i, block1)| {
        blocks.iter().enumerate().all(|(j, block2)| {
            if i == j { true } else { stable_wrt(n, f, block1, block2) }
        })
    })
}

// a partition P refines a partition Q if every block of P is a subset of some block of Q
fn refines(n : usize, partition1 : &Vec<usize>, partition2 : &Vec<usize>) -> bool {
    let blocks1 = (0..n).fold(vec![vec![]; n], |mut acc, x| {
        acc[partition1[x]].push(x);
        acc
    });
    let blocks1 = blocks1.into_iter().filter(|x| x.len() > 0).collect::<Vec<Vec<usize>>>();
    let blocks2 = (0..n).fold(vec![vec![]; n], |mut acc, x| {
        acc[partition2[x]].push(x);
        acc
    });
    let blocks2 = blocks2.into_iter().filter(|x| x.len() > 0).collect::<Vec<Vec<usize>>>();
    blocks1.iter().all(|block1| {
        blocks2.iter().any(|block2| {
            block1.iter().all(|x| block2.contains(x))
        })
    })
}

fn test_correctness(n : usize, f : &Vec<usize>, partition : Vec<usize>) {
    let new_partition = hopcroft(n, partition.clone(), f);
    assert!(stable_partition(n, f, &new_partition));
    assert!(refines(n, &new_partition, &partition));
}

fn main() {
    /*
    0 -> (1)
    2 -> (3)
    4 -> 5
    6 -> 7
    */
    let n = 8;
    let partition = vec![0, 1, 0, 1, 0, 0, 0, 0];
    let f = vec![1, 1, 3, 3, 5, 5, 7, 7]; 
    test_correctness(n, &f, partition.clone());
    println!("{:?}", hopcroft(n, partition, &f));
}