1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

//! A lib that implements the FP-Growth algorithm.
//!
//! # Usage
//!
//! To get you started quickly, the easiest and highest-level way to get
//! a FP-Growth algorithm result is to use [`algorithm::FPGrowth::find_frequent_patterns()`]
//!
//! ```
//! use fp_growth::algorithm::*;
//!
//! let transactions = vec![
//!     vec!["e", "c", "a", "b", "f", "h"],
//!     vec!["a", "c", "g"],
//!     vec!["e"],
//!     vec!["e", "c", "a", "g", "d"],
//!     vec!["a", "c", "e", "g"],
//!     vec!["e"],
//!     vec!["a", "c", "e", "b", "f"],
//!     vec!["a", "c", "d"],
//!     vec!["g", "c", "e", "a"],
//!     vec!["a", "c", "e", "g"],
//!     vec!["i"],
//! ];
//! let minimum_support = 2;
//! let fp_growth_str = FPGrowth::<&str>::new(transactions, minimum_support);
//! let result = fp_growth_str.find_frequent_patterns();
//! println!("The number of results: {}", result.frequent_patterns_num());
//! for (frequent_pattern, support) in result.frequent_patterns().iter() {
//!     println!("{:?} {}", frequent_pattern, support);
//! }
//! ```

use std::{fmt::Debug, hash::Hash};

pub mod algorithm;
pub mod tree;

pub trait ItemType: Eq + Ord + Hash + Copy + Debug {}

impl<T> ItemType for T where T: Eq + Ord + Hash + Copy + Debug {}

#[cfg(test)]
mod tests {
    use crate::algorithm::FPGrowth;
    use crate::tree::{Node, Tree};
    use std::rc::Rc;

    #[test]
    fn test_node() {
        let root_node = Node::<i32>::new_rc(None, 0);
        let child_node_1 = Rc::new(Node::<i32>::new(Some(1), 1));
        let child_node_2 = Rc::new(Node::<i32>::new(Some(2), 2));

        root_node.add_child(Rc::clone(&child_node_1));
        child_node_1.add_child(Rc::clone(&child_node_2));

        assert!(root_node.is_root());
        assert_eq!(root_node.search(1), Some(Rc::clone(&child_node_1)));
        assert_eq!(root_node.search(2), None);
        assert_eq!(root_node.item(), None);

        assert!(!child_node_1.is_root());
        assert_eq!(child_node_1.search(1), None);
        assert_eq!(child_node_1.search(2), Some(Rc::clone(&child_node_2)));
        assert_eq!(child_node_1.item(), Some(1));

        assert!(!child_node_2.is_root());
        assert_eq!(child_node_2.search(1), None);
        assert_eq!(child_node_2.search(2), None);
        assert_eq!(child_node_2.item(), Some(2));
    }

    #[test]
    fn test_tree() {
        let mut tree = Tree::<&str>::new();
        let transactions = vec![
            vec!["a", "c", "e", "b", "f"],
            vec!["a", "c", "g"],
            vec!["e"],
            vec!["a", "c", "e", "g", "d"],
            vec!["a", "c", "e", "g"],
            vec!["e"],
            vec!["a", "c", "e", "b", "f"],
            vec!["a", "c", "d"],
            vec!["a", "c", "e", "g"],
            vec!["a", "c", "e", "g"],
        ];
        for transaction in transactions.into_iter() {
            tree.add_transaction(transaction);
        }
    }

    #[test]
    fn test_algorithm() {
        let transactions = vec![
            vec!["a", "c", "e", "b", "f", "h", "a", "e", "f"],
            vec!["a", "c", "g"],
            vec!["e"],
            vec!["e", "c", "a", "g", "d"],
            vec!["a", "c", "e", "g"],
            vec!["e", "e"],
            vec!["a", "c", "e", "b", "f"],
            vec!["a", "c", "d"],
            vec!["g", "c", "e", "a"],
            vec!["a", "c", "e", "g"],
            vec!["i"],
        ];
        // FIXME: use specific result cases to verify correctness.
        let test_cases: Vec<(usize, usize, usize)> = vec![
            // (minimum_support, frequent_patterns_num, elimination_set_num)
            (1, 88, 88),
            (2, 43, 47),
            (3, 15, 20),
            (4, 15, 20),
            (5, 11, 17),
            (6, 7, 15),
            (7, 4, 14),
            (8, 4, 14),
            (9, 0, 10),
        ];
        for (minimum_support, frequent_patterns_num, elimination_set_num) in test_cases.iter() {
            let fp_growth_str = FPGrowth::<&str>::new(transactions.clone(), *minimum_support);
            let result = fp_growth_str.find_frequent_patterns();
            assert_eq!(*frequent_patterns_num, result.frequent_patterns_num());
            assert_eq!(*elimination_set_num, result.elimination_sets_num());
        }
    }
}