pq_tree/lib.rs
1//! A PQ-tree[^1] is a data structure that represents all possible permutations of some elements
2//! limited by a set of constraints. Each constraint enforces consecutive ordering of a subset of
3//! elements in the leaf set of the tree.
4//!
5//! PQ-tree based algorithms can be used for solving various problems, including consecutive ones property testing
6//! for matrices, graph planarity testing, interval graph recognition and so on.
7//!
8//! A PQ-tree consists of three types of nodes: P-nodes, allowing arbitrary permutations of children, Q-nodes, allowing
9//! only reversions and L-nodes that represent tree leaves.
10//!
11//! # Operations
12//!
13//! ## Reduction
14//! Applying a constraint is called "tree *reduction*".
15//! It takes a subset of tree leaves as an argument and updates the tree to enforce consecutive ordering of these leaves.
16//!
17//! Successful reduction returns modified tree with a
18//! new constraint embedded into the tree structure and marks the root of the subtree with minimal height that contains all
19//! specified leaves as the *pertinent root*. Chosen leaves and nodes containing only these leaves are labelled *full*.
20//!
21//! If a constraint is inapplicable, then reduction will fail.
22//! Failed reduction will destroy the tree.
23//!
24//! ## Replacement
25//!
26//! Full children of pertinent root, specific leaf or entire tree can be replaced with by a new set of leaves
27//! or removed from the tree.
28//!
29//! Replacement by empty set will remove subtree entirely and sets pertinent root to None.
30//!
31//! Pertinent subtree replacement is possible only if pertinent root was found by tree reduction. If pertinent subtree is
32//! replaced by a non-empty set, then the pertinent root will be set to the root of inserted subtree.
33//!
34//! ## Frontier
35//!
36//! Reading leaves of a tree from left-to-right yields its *frontier*.
37//!
38//! Tree frontier is one of the allowed leaves' permutations. Although any of such permutations is sufficient for most tasks,
39//! if leaves implement [`Ord`], then tree can be sorted and allow to choose unambiguous frontier.
40//!
41//! Two sorting functions are present: [`PQTree::sort_minimal`] and [`PQTree::sort_lexicographically`].
42//!
43//! Both of them performing node sorting from bottom to top, but the first using minimal children leaf as key for parent,
44//! and the second uses leftmost leaf (where there is no difference for P-nodes, for Q-nodes it is important).
45//!
46//! Let's see it on simple example
47//! ```none
48//! unsorted tree: ([[7 (1 4) 6] 3 2] 0 5)
49//! sort_lexicographically: (0 [2 3 [6 (1 4) 7]] 5)
50//! sort_minimal: (0 [[6 (1 4) 7] 3 2] 5)
51//! ```
52//! (P-nodes denoted by `()` and Q-nodes denoted by `[]`).
53//!
54//! Look at Q-node `[6 (1 4) 7]`: for [`PQTree::sort_minimal`] leaf `1` was picked as a node sorting key but
55//! for [`PQTree::sort_lexicographically`] leaf `6` was picked as being leftmost.
56//!
57//! Informally speaking, minimal sort ensures that minimal leaf is placed to the leftmost possible position in a frontier and
58//! lexicographical sort ensures that the leftmost leaf in a frontier is the minimal possible leaf.
59//!
60//! # Examples
61//!
62//! ## Consecutive ones example
63//! Let `matrix` be
64//! ```
65//! let matrix = vec![
66//! vec![1, 1, 0, 1, 1],
67//! vec![0, 0, 0, 1, 0],
68//! vec![1, 1, 1, 1, 0],
69//! vec![1, 1, 1, 1, 1],
70//! vec![1, 0, 1, 1, 0],
71//! ];
72//!```
73//!
74//! If it is possible to rearrange matrix rows in a way that every column has a single run of ones, we can say
75//! that the matrix has a "consecutive ones" property.
76//!
77//! We can build a PQ-tree for matrix rows and apply a constraint for each column
78//!```
79//! use pq_tree::PQTree;
80//!
81//! let mut tree = PQTree::from_leaves(&[1, 2, 3, 4, 5]).unwrap();
82//! tree = tree.reduction(&[1, 3, 4, 5]).unwrap();
83//! tree = tree.reduction(&[1, 3, 4]).unwrap();
84//! tree = tree.reduction(&[3, 4, 5]).unwrap();
85//! tree = tree.reduction(&[1, 2, 3, 4, 5]).unwrap();
86//! tree = tree.reduction(&[1, 4]).unwrap();
87//! ```
88//! Then take tree frontier and reorder matrix rows according to it
89//! ```
90//! # use pq_tree::PQTree;
91//! #
92//! # let mut tree = PQTree::from_leaves(&[1, 2, 3, 4, 5]).unwrap();
93//! # tree = tree.reduction(&[1, 3, 4, 5]).unwrap();
94//! # tree = tree.reduction(&[1, 3, 4]).unwrap();
95//! # tree = tree.reduction(&[3, 4, 5]).unwrap();
96//! # tree = tree.reduction(&[1, 2, 3, 4, 5]).unwrap();
97//! # tree = tree.reduction(&[1, 4]).unwrap();
98//! # let matrix = vec![
99//! # vec![1, 1, 0, 1, 1],
100//! # vec![0, 0, 0, 1, 0],
101//! # vec![1, 1, 1, 1, 0],
102//! # vec![1, 1, 1, 1, 1],
103//! # vec![1, 0, 1, 1, 0],
104//! # ];
105//! #
106//! tree.frontier().into_iter().for_each(|r| println!("{:?}", matrix[r - 1]));
107//! ```
108//! And obtain reordered matrix
109//! ```none
110//! [1, 1, 0, 1, 1]
111//! [1, 1, 1, 1, 1]
112//! [1, 1, 1, 1, 0]
113//! [1, 0, 1, 1, 0]
114//! [0, 0, 0, 1, 0]
115//! ```
116//!
117//! Tree is successfully reduced and we can conclude that `matrix` has a consecutive ones property.
118//!
119//! ## Irreducible tree example
120//!```
121//! use pq_tree::{PQTree, ReductionError};
122//!
123//! let mut tree = PQTree::from_leaves(&[1, 2, 3, 4]).unwrap();
124//! tree = tree.reduction(&[1, 2]).unwrap();
125//! tree = tree.reduction(&[2, 3]).unwrap();
126//! assert_eq!(tree.reduction(&[2, 4]).unwrap_err(), ReductionError::IrreducibleTree);
127//! ```
128//!
129//! ## Graph planarity testing
130//!
131//! Planarity testing requires some preliminary steps (decomposition to biconnected components and st-numbering every component)
132//! and then the PQ-tree can be used to check planarity of each component.
133//!
134//! Consider graph
135//! ```none
136//! 1
137//! |\
138//! | \
139//! | \
140//! | \
141//! | \
142//! | 2
143//! | / \
144//! | / \
145//! | / 3
146//! | / /
147//! |/ /
148//! 4 /
149//! \ /
150//! \ /
151//! 5
152//! ```
153//!
154//! It can be presented as a sequence of "bush forms": one for each vertex from top to bottom.
155//! ```none
156//! 1 1 1 1 1
157//! |\ |\ |\ |\ |\
158//! | \ | \ | \ | \ | \
159//! | \ | \ | \ | \ | \
160//! | \ | \ | \ | \ | \
161//! 4 2 | \ | \ | \ | \
162//! | 2 | 2 | 2 | 2
163//! | |\ | |\ | / \ | / \
164//! 4 3 4 | | \ | / \ | / \
165//! | 3 \ | / 3 | / 3
166//! | | \ | / | | / /
167//! 4 5 4 |/ | |/ /
168//! 4 | 4 /
169//! | | \ /
170//! 5 5 \ /
171//! 5
172//! ```
173//!
174//! Dangling labels denote incoming edges to unprocessed vertices.
175//! All incoming edges to the same vertex must be consequent and we will enforce it by reductions.
176//!
177//! We can process our graph vertex-by-vertex by reducing the tree by incoming edge set and replacing it by
178//! outgoing edges on each step.
179//!
180//! If this process succeeds for all vertices then, the graph is planar.
181//!```
182//! use pq_tree::PQTree;
183//!
184//! #[derive(Hash, PartialEq, Eq, Debug, Copy, Clone)]
185//! struct Edge(i32, i32);
186//!
187//! let mut tree = PQTree::from_leaves(&[Edge(1, 2), Edge(1, 4)]).unwrap();
188//!
189//! tree = tree.reduction(&[Edge(1, 2)]).unwrap();
190//! tree = tree.replace_pertinent_by_new_leaves(&[Edge(2, 3), Edge(2, 4)]).unwrap();
191//!
192//! tree = tree.reduction(&[Edge(2, 3)]).unwrap();
193//! tree = tree.replace_pertinent_by_new_leaves(&[Edge(3, 5)]).unwrap();
194//!
195//! tree = tree.reduction(&[Edge(1, 4), Edge(2, 4)]).unwrap();
196//! tree = tree.replace_pertinent_by_new_leaves(&[Edge(4, 5)]).unwrap();
197//!
198//! tree = tree.reduction(&[Edge(3, 5), Edge(4, 5)]).unwrap();
199//! ```
200//! Note:
201//!
202//! Single leaf reduction and replacement can be done in one operation like
203//!
204//!```
205//! # use pq_tree::PQTree;
206//! #
207//! # #[derive(Hash, PartialEq, Eq, Debug, Copy, Clone)]
208//! # struct Edge(i32, i32);
209//! #
210//! # let mut tree = PQTree::from_leaves(&[Edge(1, 2), Edge(1, 4)]).unwrap();
211//! #
212//! tree = tree.replace_leaf_by_new_leaves(&Edge(1, 2), &[Edge(2, 3), Edge(2, 4)]).unwrap();
213//! # tree = tree.replace_leaf_by_new_leaves(&Edge(2, 3), &[Edge(3, 5)]).unwrap();
214//! #
215//! # tree = tree.reduction(&[Edge(1, 4), Edge(2, 4)]).unwrap();
216//! # tree = tree.replace_pertinent_by_new_leaves(&[Edge(4, 5)]).unwrap();
217//! #
218//! # tree = tree.reduction(&[Edge(3, 5), Edge(4, 5)]).unwrap();
219//! ```
220//! because no new information can be obtained from single leaf ordering and a pertinent root is the leaf itself.
221//! But it will lack pertinent root tracking.
222//!
223//! For further information see Booth and Lueker paper referred below.
224//!
225//! # Error handling
226//!
227//! Functions that can fail on some input are consume `self` and return [`Result<Self, _>`].
228//!
229//! If necessary, a tree can be cloned before calling such functions.
230//!
231//! Panics are considered bugs (with obvious exceptions like unrelated OOM)
232//! and should be reported along with minimal reproducible example if possible.
233//!
234//! # Rerefences
235//! [^1] Booth, K.S., & Lueker, G.S. (1976).
236//! Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms.
237//! J. Comput. Syst. Sci., 13, 335-379. <https://doi.org/10.1016/s0022-0000(76)80045-1>
238
239#[doc = include_str!("../README.md")]
240#[cfg(doctest)]
241pub struct ReadmeDoctests;
242
243pub use self::errors::*;
244pub use self::tree::*;
245
246mod errors;
247mod node;
248mod reduction;
249mod rel;
250mod sublist;
251mod tree;
252
253#[cfg(test)]
254mod tests {
255 use std::fmt::{Debug, Display, Formatter};
256 use std::hash::Hash;
257
258 use crate::PQTree;
259
260 #[derive(Hash, PartialEq, Eq, Copy, Clone)]
261 struct Edge(i32, i32);
262
263 impl Display for Edge {
264 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
265 write!(f, "{}-{}", self.0, self.1)
266 }
267 }
268
269 impl Debug for Edge {
270 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
271 Display::fmt(self, f)
272 }
273 }
274
275 fn reduce<T: Eq + Hash + Clone + Debug + Display>(mut tree: PQTree<T>, s: &[T]) -> PQTree<T> {
276 tree = tree.reduction(s).unwrap();
277 println!("reduction {:<22} {tree}", format!("{:?}:", s));
278 tree
279 }
280
281 fn replace<T: Eq + Hash + Clone + Debug + Display>(mut tree: PQTree<T>, s: &[T]) -> PQTree<T> {
282 tree = tree.replace_pertinent_by_new_leaves(s).unwrap();
283 println!("replacement {:<22} {tree}", format!("{:?}:", s));
284 tree
285 }
286
287 #[test]
288 fn simple_planarity_test() {
289 let mut tree = PQTree::from_leaves(&[Edge(1, 2), Edge(1, 3), Edge(1, 5)]).unwrap();
290 println!("initial: {tree}");
291
292 tree = reduce(tree, &[Edge(1, 2)]);
293 tree = replace(tree, &[Edge(2, 3), Edge(2, 4), Edge(2, 5)]);
294
295 tree = reduce(tree, &[Edge(1, 3), Edge(2, 3)]);
296 tree = replace(tree, &[Edge(3, 4), Edge(3, 5)]);
297
298 tree = reduce(tree, &[Edge(2, 4), Edge(3, 4)]);
299 tree = replace(tree, &[Edge(4, 5)]);
300
301 tree = reduce(tree, &[Edge(1, 5), Edge(2, 5), Edge(3, 5), Edge(4, 5)]);
302 tree = replace(tree, &[]);
303
304 drop(tree);
305 }
306
307 #[test]
308 fn consecutive_ones_test() {
309 let matrix = vec![
310 vec![1, 1, 0, 1, 1],
311 vec![0, 0, 0, 1, 0],
312 vec![1, 1, 1, 1, 0],
313 vec![1, 1, 1, 1, 1],
314 vec![1, 0, 1, 1, 0],
315 ];
316
317 let mut tree = PQTree::from_leaves(&[1, 2, 3, 4, 5]).unwrap();
318 tree.frontier().into_iter().for_each(|r| println!("{:?}", matrix[r - 1]));
319 println!("initial: {tree}");
320 tree = reduce(tree, &[1, 3, 4, 5]);
321 tree = reduce(tree, &[1, 3, 4]);
322 tree = reduce(tree, &[3, 4, 5]);
323 tree = reduce(tree, &[1, 2, 3, 4, 5]);
324 tree = reduce(tree, &[1, 4]);
325 println!("frontier: {:?}", tree.frontier());
326
327 tree.frontier().into_iter().for_each(|r| println!("{:?}", matrix[r - 1]));
328 }
329}