fp_growth/
lib.rs

1//! A lib that implements the FP-Growth algorithm.
2//!
3//! # Usage
4//!
5//! To get you started quickly, the easiest and highest-level way to get
6//! a FP-Growth algorithm result is to use [`algorithm::FPGrowth::find_frequent_patterns()`]
7//!
8//! ```
9//! use fp_growth::algorithm::*;
10//!
11//! let transactions = vec![
12//!     vec!["e", "c", "a", "b", "f", "h"],
13//!     vec!["a", "c", "g"],
14//!     vec!["e"],
15//!     vec!["e", "c", "a", "g", "d"],
16//!     vec!["a", "c", "e", "g"],
17//!     vec!["e"],
18//!     vec!["a", "c", "e", "b", "f"],
19//!     vec!["a", "c", "d"],
20//!     vec!["g", "c", "e", "a"],
21//!     vec!["a", "c", "e", "g"],
22//!     vec!["i"],
23//! ];
24//! let minimum_support = 2;
25//! let fp_growth_str = FPGrowth::<&str>::new(transactions, minimum_support);
26//! let result = fp_growth_str.find_frequent_patterns();
27//! println!("The number of results: {}", result.frequent_patterns_num());
28//! for (frequent_pattern, support) in result.frequent_patterns().iter() {
29//!     println!("{:?} {}", frequent_pattern, support);
30//! }
31//! ```
32
33use std::{fmt::Debug, hash::Hash};
34
35pub mod algorithm;
36pub mod tree;
37
38pub trait ItemType: Eq + Ord + Hash + Copy + Debug {}
39
40impl<T> ItemType for T where T: Eq + Ord + Hash + Copy + Debug {}
41
42#[cfg(test)]
43mod tests {
44    use crate::algorithm::FPGrowth;
45    use crate::tree::{Node, Tree};
46    use std::rc::Rc;
47
48    #[test]
49    fn test_node() {
50        let root_node = Node::<i32>::new_rc(None, 0);
51        let child_node_1 = Rc::new(Node::<i32>::new(Some(1), 1));
52        let child_node_2 = Rc::new(Node::<i32>::new(Some(2), 2));
53
54        root_node.add_child(Rc::clone(&child_node_1));
55        child_node_1.add_child(Rc::clone(&child_node_2));
56
57        assert!(root_node.is_root());
58        assert_eq!(root_node.search(1), Some(Rc::clone(&child_node_1)));
59        assert_eq!(root_node.search(2), None);
60        assert_eq!(root_node.item(), None);
61
62        assert!(!child_node_1.is_root());
63        assert_eq!(child_node_1.search(1), None);
64        assert_eq!(child_node_1.search(2), Some(Rc::clone(&child_node_2)));
65        assert_eq!(child_node_1.item(), Some(1));
66
67        assert!(!child_node_2.is_root());
68        assert_eq!(child_node_2.search(1), None);
69        assert_eq!(child_node_2.search(2), None);
70        assert_eq!(child_node_2.item(), Some(2));
71    }
72
73    #[test]
74    fn test_tree() {
75        let mut tree = Tree::<&str>::new();
76        let transactions = vec![
77            vec!["a", "c", "e", "b", "f"],
78            vec!["a", "c", "g"],
79            vec!["e"],
80            vec!["a", "c", "e", "g", "d"],
81            vec!["a", "c", "e", "g"],
82            vec!["e"],
83            vec!["a", "c", "e", "b", "f"],
84            vec!["a", "c", "d"],
85            vec!["a", "c", "e", "g"],
86            vec!["a", "c", "e", "g"],
87        ];
88        for transaction in transactions.into_iter() {
89            tree.add_transaction(transaction);
90        }
91    }
92
93    #[test]
94    fn test_algorithm() {
95        let transactions = vec![
96            vec!["a", "c", "e", "b", "f", "h", "a", "e", "f"],
97            vec!["a", "c", "g"],
98            vec!["e"],
99            vec!["e", "c", "a", "g", "d"],
100            vec!["a", "c", "e", "g"],
101            vec!["e", "e"],
102            vec!["a", "c", "e", "b", "f"],
103            vec!["a", "c", "d"],
104            vec!["g", "c", "e", "a"],
105            vec!["a", "c", "e", "g"],
106            vec!["i"],
107        ];
108        // FIXME: use specific result cases to verify correctness.
109        let test_cases: Vec<(usize, usize, usize)> = vec![
110            // (minimum_support, frequent_patterns_num, elimination_set_num)
111            (1, 88, 88),
112            (2, 43, 47),
113            (3, 15, 20),
114            (4, 15, 20),
115            (5, 11, 17),
116            (6, 7, 15),
117            (7, 4, 14),
118            (8, 4, 14),
119            (9, 0, 10),
120        ];
121        for (minimum_support, frequent_patterns_num, elimination_set_num) in test_cases.iter() {
122            let fp_growth_str = FPGrowth::<&str>::new(transactions.clone(), *minimum_support);
123            let result = fp_growth_str.find_frequent_patterns();
124            assert_eq!(*frequent_patterns_num, result.frequent_patterns_num());
125            assert_eq!(*elimination_set_num, result.elimination_sets_num());
126        }
127    }
128}
fp_growth/lib.rs

fp_growth/
lib.rs
