pq-tree

PQ-tree 是一种数据结构，表示由一组约束条件限制的一些元素的所有可能的排列。每个约束强制树叶子集的子集按连续顺序排列。

基于PQ-tree的算法可用于解决各种问题，包括矩阵的连续1属性测试、图平面性测试、区间图识别等。

PQ-tree树由三种类型的节点组成：允许对子节点进行任意排列的P节点、仅允许反转的Q节点以及表示树叶子节的L节点。

演示

use pq_tree::PQTree;

// is this matrix C1P ?

let matrix = vec![
    vec![1, 1, 0, 1, 1],
    vec![0, 0, 0, 1, 0],
    vec![1, 1, 1, 1, 0],
    vec![1, 1, 1, 1, 1],
    vec![1, 0, 1, 1, 0],
];

let mut tree = PQTree::from_leaves(&[1, 2, 3, 4, 5]).unwrap();
tree = tree.reduction(&[1, 3, 4, 5]).unwrap();
tree = tree.reduction(&[1, 3, 4]).unwrap();
tree = tree.reduction(&[3, 4, 5]).unwrap();
tree = tree.reduction(&[1, 2, 3, 4, 5]).unwrap();
tree = tree.reduction(&[1, 4]).unwrap();

tree.frontier().into_iter().for_each(|r| println!("{:?}", matrix[r - 1]));

// [1, 1, 0, 1, 1]
// [1, 1, 1, 1, 1]
// [1, 1, 1, 1, 0]
// [1, 0, 1, 1, 0]
// [0, 0, 0, 1, 0]

// Yes, it is!