FPGrowth Algorithm Implementation

Question

This is my implementation of the FPGrowth algorithm where, as an optimisation, I avoid re-creating the tree at each extension of the prefix, while I use a view representation that I think would be more memory efficient. Please let me know if there are any other ways to improve the current code. Any feedback is appreciated.

#include <iostream>

#include <map>
#include <unordered_set>
#include <vector>
#include <unordered_map>
#include <deque>
#include <queue>
#import <cassert>
#include <stack>

/**
 * Trie node required by the fpgrowth algorithm
 * @tparam T
 */
template <typename T> struct fpgrowth_node {
    size_t count, // Number of instances being observed
    tmp_count, // Temporary count while pruning the graph: instead of creating another fpgrowth tree, I'll use views to accelerate the task
    height; // height inducing the visiting order from the leaves
    const T* value; // Pointer to the actual value: this is done so to alleviate the memory from having multiple copies of the object. (the actual singleton will reside in the main fpgrowth table)
    struct fpgrowth_node* parent; // Root for the current node (if any)
    std::unordered_map<const T*, struct fpgrowth_node*> children; // Children mapped by key value
    struct fpgrowth_node* list; // single linked list connecting all the nodes associated to the same object
//    bool current_leaf;  // whether this element is currently a leaf
    fpgrowth_node(const T* k = nullptr) : value{k}, count{1}, tmp_count{0}, height{0}, parent{nullptr}, children{}, list{nullptr}  {}

    /**
     * Adding a child to the curent node or, if it already exists, incrementing the counter for the existing one
     * @param value     Value associated to the child
     * @return  Either the already-existing child or the newly allocated one
     */
    struct fpgrowth_node* add_child(const T* value) {
        auto it = children.emplace(value, nullptr);
        if (it.second) { // If I am adding a new child
            it.first->second = new fpgrowth_node(value); // Allocating the new child
            it.first->second->parent = this;  // Setting the parent to the current node
            it.first->second->height = height+1;    // Increasing the height, so to exploit topological sort for efficiently scanning the tree from the leaves
        } else {
            it.first->second->height = std::max(height+1,it.first->second->height); // Otherwise, update the nodes' depth depending on my current one
            it.first->second->count++;  // If the child was already there, increment its count
        }
        return it.first->second; // returning the child already being created in the trie
    }

    ~fpgrowth_node() {
        for (const auto& [k,v] : children) delete v; // deleting all of the allocated children so to save memory and avoid memory leaks
    }
};

template <typename T>
static inline void fpgrowth_expand(struct fpgrowth_node<T>* tree,
                                   const T* current,
                                   size_t curr_support,
                                   std::unordered_set<const T*> prefix,
                                   const std::unordered_set<struct fpgrowth_node<T>*>& view,
                                   std::unordered_map<const T*, struct fpgrowth_node<T>*>& traverse,
                                   std::vector<std::pair<size_t, std::unordered_set<const T*>>>& results,
                                   size_t minsupport = 1) {

//    std::cout << "Step: ";
//    for (const auto& ptr :prefix)
//        std::cout << *ptr << " ";
//    std::cout << *current << std::endl;

    std::unordered_set<struct fpgrowth_node<T>*> visitable,  // Whether the element was already visited in a previous iteration
                                                 in_tree     // Whether the node, for its good support, might be part of the next pruning and therefore part of the view
                                                 ;
    auto comp = []( struct fpgrowth_node<T>* a, struct fpgrowth_node<T>* b ) { return a->height < b->height; }; // As a tree is a DAG, I can exploit the topological order to know in which order extract the nodes from the queue
    std::priority_queue<struct fpgrowth_node<T>*, std::vector<struct fpgrowth_node<T>*>, decltype(comp)> dq; // Priority queue for storing all the nodes, being sorted by order of visit
    auto it = traverse.find(current);                                         // Checking whether we are allowed to traverse from this node
    std::unordered_map<const T*, struct fpgrowth_node<T>*> new_firsttraverse; // Updating the first_to_traverse table depending on the nodes being available
    std::unordered_map<const T*, size_t> toTraverseNext;                      // Updating the support table while keeping the support of the previous nodes
    std::vector<struct fpgrowth_node<T>*> visitedChild;                       // For each non-leaf node, keeping all the childs that were visited within the view
    if (it != traverse.end()) {
        {
            struct fpgrowth_node<T>* ptr = it->second;
            while (ptr) {
                if (view.contains(ptr)) { // If the current element in the linked list is actually part of the view
                    dq.emplace(ptr);
                }
                ptr = ptr->list; // Scanning all the elements in the list
            }
        }

        while (!dq.empty()) {
            struct fpgrowth_node<T>* dq_ptr = dq.top(); // Next element to be visited
            dq.pop();
            if (!visitable.emplace(dq_ptr).second) continue; // Discarding visiting the node if visited already
            {
                dq_ptr->tmp_count = 0; // Re-setting the counter to zero
//                dq_ptr->current_leaf = true;
                bool isLeaf = (dq_ptr->value == current);
                bool goodToTest = false;
                if (isLeaf) {
                    dq_ptr->tmp_count = dq_ptr->count;// As this is the leaf, it needs to hold the tmp_count for the visit its own support count.
//                    dq_ptr->current_leaf = true;// Setting the current node as leaf, from which start the visit (from the bottom!)
                    goodToTest = true; // Yes, I can proceed with the visit
                } else {
                    size_t totalChild = 0; // Counting the number of allowed children to be visited within the view as in (A)
                    visitedChild.clear(); // Clearing the set of the previous children
                    for (const auto& [k,v] : dq_ptr->children) {
                        if (view.contains(v)) {
                            totalChild++; // (A)
                            if (visitable.contains(v)) {
                                visitedChild.emplace_back(v); // Yes, this child has been visited in a previous iteration
                            }
                        }
                    }
                    if (totalChild == visitedChild.size()) { // I can do the counting only if I have already visited all of the childs that are there in the
                        for (const auto& v : visitedChild) { // After visiting all the childs that I could, *then*, I set my tmp_count to the sum of my child's tmp_count
                            goodToTest = true;
                            dq_ptr->tmp_count += v->tmp_count; // Then, setting up the count to the sum of the supports from my fully visited children
//                            dq_ptr->current_leaf = dq_ptr->current_leaf && ((v->current_leaf) && (v->tmp_count < minsupport)); // Setting myself as a leaf
                        }
                    } else
                        visitable.erase(dq_ptr); // B: If I am not allowed to visit all the children, as they have not fully visited yet, re-set myself in the visiting queue
                        // the queue guarantees that, if I have not visited another child, then, I will eventually put back in the queue by it in (C), so this does not misses a node
                }
                if (visitable.contains(dq_ptr)) { // If the visit was successful and (B) did not happen
                    if (goodToTest && (dq_ptr->tmp_count >= minsupport)) { // testing the support only if I am either a leaf or whether I have already visited all my childs, so to not
                        auto it4 = toTraverseNext.emplace(dq_ptr->value, dq_ptr->tmp_count); // Setting the current support in the table for the current item
                        if (!it4.second)
                            it4.first->second += dq_ptr->tmp_count; // If a previous value was already there, then just update it!
                        if (current != dq_ptr->value) new_firsttraverse.emplace(dq_ptr->value, dq_ptr); // If this was not met before, then setting the current node as first step in the list to be visited
                        in_tree.insert(dq_ptr); // Definitively, if the support is good, this should be part of the next iteration
                    }
                    if (view.contains(dq_ptr->parent)) // If the parent is an allowed node (still, it should be)
                        dq.push(dq_ptr->parent); // C: putting the parent as the next step to visit
                }

            }
        }
    }

    prefix.insert(current); // Adding the current node as part of the prefix
    results.emplace_back(curr_support, prefix); // setting this as another result
    for (const auto& [next,with_supp] : toTraverseNext) { // Using the updated support table to traverse the remaining nodes
        if ((next != current) && ( !prefix.contains(next))) // Visiting next only other strings that were not part of the prefix
            fpgrowth_expand(tree, next, with_supp, prefix, in_tree, new_firsttraverse, results, minsupport);
    }
}

template <typename T>
static inline std::vector<std::pair<size_t, std::unordered_set<const T*>>> fpgrowth(const std::vector<std::unordered_set<T>>& obj,
                            std::vector<std::pair<T, size_t>>& final_element_for_scan,
                            size_t minsupport = 1) {
    struct fpgrowth_node<T> tree{nullptr};
    final_element_for_scan.clear();
    std::unordered_set<struct fpgrowth_node<T>*> in_tree;
    std::unordered_map<const T*, struct fpgrowth_node<T>*> last_pointer, firstpointer;
    std::unordered_map<const T*, std::unordered_set<struct fpgrowth_node<T>*>> createdElements;
    {
        std::map<T, size_t> element; // Fast representation for the support table, for efficiently associating the item to the support value
        for (auto it = obj.begin(); it != obj.end(); it++) {
            for (const T& x : *it) {
                auto it2 = element.emplace(x, 1);
                if (!it2.second) it2.first->second++;
            }
        }
        // moving this to a vector, while keeping the items with adequate support
        for (auto it = element.begin(), en = element.end(); it != en; it++) {
            if (it->second >= minsupport)
                final_element_for_scan.emplace_back(*it);
        }
    }
    // Sorting the elements in the table by decreasing support
    std::sort(final_element_for_scan.begin(), final_element_for_scan.end(), [](const std::pair<T, size_t>& l, const std::pair<T, size_t>& r) {
        return l.second>r.second;
    });
    struct fpgrowth_node<T>* ptr ;
    for (auto itx = obj.begin(); itx != obj.end(); itx++) { // For each transaction
        auto e = itx->end();
        ptr = &tree;
        auto it_left = final_element_for_scan.begin();
        auto e_left = final_element_for_scan.end();
        while ((it_left != e_left)) {
            auto f = itx->find(it_left->first);
            if (f == e) {it_left++; continue;}
            else {
                // For each element in the transaction which is also in the support table
                auto it3 = last_pointer.emplace(&it_left->first, nullptr);
                // Expanding the trie with a new child
                ptr = ptr->add_child(&it_left->first);
                // Using a set of visited nodes to avoid loops in the list
                bool newInsertion = createdElements[&it_left->first].emplace(ptr).second;
                in_tree.insert(ptr); // This node shoudl be part of the view
                if (it3.second) {
                    // First pointer of the list for traversing the newly established leaves at each novel iteration efficiently
                    firstpointer.emplace(&it_left->first, ptr);
                        it3.first->second = ptr;
                } else {
                    if (!it3.first->second) {
                        // First pointer of the list for traversing the newly established leaves at each novel iteration efficiently
                        it3.first->second = ptr;
                    } else if (newInsertion) {
                        // Avoiding loops: adding an element in the list only if required
                        it3.first->second->list = ptr;
                        it3.first->second = ptr;
                    }
                }
                it_left++;
            }
        }
    }

    createdElements.clear();

    // results of the itemsets with their support to be returned
    std::vector<std::pair<size_t, std::unordered_set<const T*>>> results;
    // Setting up the new projection of the tree, so to avoid the re-creation of the trees multiple times:
    // setting up a view with the allowed nodes will be more efficient (as it will save the extra allocation cost for 
    // the nodes, and the only memory overhead is just the pointer to the nodes in the FPGrowth tree)
    for (auto rit = final_element_for_scan.rbegin(), ren = final_element_for_scan.rend(); rit != ren; rit++) {
        fpgrowth_expand(ptr, (const T *) &rit->first, rit->second, std::unordered_set<const T *>{}, in_tree, firstpointer, results,
                        minsupport);
    }
    return results;
}


int main() {
    std::vector<std::unordered_set<std::string>> S;
    S.emplace_back(std::unordered_set<std::string>{"m","o","n","k","e","y"});
    S.emplace_back(std::unordered_set<std::string>{"d","o","n","k","e","y"});
    S.emplace_back(std::unordered_set<std::string>{"m","a","k","e"});
    S.emplace_back(std::unordered_set<std::string>{"m","u","c","k","y"});
    S.emplace_back(std::unordered_set<std::string>{"c","o","c","k","i","e"});
    std::vector<std::pair<std::string, size_t>> single_support;
    for (const auto& ref : fpgrowth(S, single_support, 3)) {
        std::cout << "Item: ";
        for (const auto& ptr : ref.second)
            std::cout << *ptr << " ";
        std::cout << " with support " << ref.first << std::endl;
    }
    return 0;
}
```

Answer 1

Enable warnings and fix them

Enable compiler and Doxygen warnings, and fix all of them. Doyxgen is complaining about several undocumented class members, and the compiler is complaining about #import (this should be #include), missing #include <algorithm>, and incorrect order of the initializer list in the constructor of fpgrowth_node. I recommend you fix the latter by using default member intializers instead.

Unused parameter tree in fpgrowth_expand()

What the compiler didn't catch, because it looks used, is the parameter tree in fpgrowth_expand(). You pass that on to recursive calls, but you don't do anything else with this parameter. It's there for useless and should be removed.

No need to repeat struct and class after declaration

Unlike in C, after you have declared a struct or a class, you can refer to them just by their name, without having to prefix that with struct or class again.

Avoid manual memory management

Avoid calling new and delete where possible, and instead use containers or smart pointers to manage memory for you. They will ensure you don't forget to delete things, and they also do the right thing in case exceptions are thrown. In your code, it's easy: instead of storing pointers to fpgrowth_node in children, just store fpgrowth_nodes directly:

template <typename T>
struct fpgrowth_node {
    …
    std::unordered_map<const T*, fpgrowth_node> children;
    …
public:
    …
    fpgrowth_node* add_child(const T* value) {
        auto [it, is_new] = children.try_emplace(value, value);
        auto& child = it->second;

        if (is_new) {
            child.parent = this;
            child.height = height + 1;
        } else {
            child.height = std::max(height + 1, child.height);
            child.count++;
        }

        return &child;
    }
    …
};

Note that you no longer need a destructor this way either.

Make it work for any type of container

You already thought of making the algorithm more generic by templating it on the item type. However, you still require the input to be in the form of std::vectors of std::unordered_sets of those items. But what if you have a std::deque of std::sets instead? You could make your classes and functions even more generic. Consider:

template <typename Dataset>
auto fpgrowth(const Dataset& dataset, …) {
    // Derive the types of transactions and items
    using Itemset = Dataset::value_type;
    using T = Itemset::value_type;
    …
}

Most of the code will be unchanged. Of course, the second parameter of fpgrowth() is an issue, because it depended on T. However, this is actually an out parameter, and instead you can just make it part of the return value, or alternatively make the whole type of final_element_for_scan a template type as well.

Make better use of range-for loops

You use range-for loops in a few places, but often you will use old-style for loops. Prefer to use range-for where possible. For example, near the start of fpgrowth():

{
    std::unordered_map<T, size_t> elements;

    for (auto& transaction: dataset) {
        for (auto& item: transaction) {
            elements.emplace(item, 0).first->second++;
        }
    }

    for (auto& [item, count]: elements) {
        if (count >= minsupport)
            final_element_for_scan.emplace_back(item, count);
        }
    }
}

Since you are using C++20, I also used structured bindings to avoid having to write .first and .second in the second for-loop. This brings me to:

Naming things

Whenever you use std::pair, you are stuck with naming the two members .first and .second. These names carry little meaning When you have pairs of pairs, you get to write things like foo.first->second->bar, and it's really hard to understand the code at that point.

There are various ways to avoid this. First, you can use references and structured bindings to temporarily give better names to members of a pair, like I did above in add_child(). However, even better is to not use std::pair if possible, and just create a struct with two better named members. Consider:

struct element_count {
    T item;
    std::size_t count;
};

std::vector<element_count> final_elements_for_scan;

And:

struct itemset_support {
    Itemset items;
    std::size_t support;
};

std::vector<itemset_support> result;

Related to this, if you frequently use a nested type like std::unordered_set<fpgrowth_node<T>*>, create a type alias for it with a clear name, like:

using Nodeset = std::unordered_set<fpgrowth_node<T>*>;
…
Nodeset in_tree;
std::unordered_map<const T*, Nodeset> createdElements;

Also try to avoid abbreviating names too much, and avoid using too generic names. It's not great to see it, it2, itx, e, it_left, e_left and it3 all in one function. As mentioned above, prefer range-for, so instead of iterators you only have to deal with values. If you do abbreviate, at least be consistent; don't write element in one place and e in another.

Also be consistent in the way you format names. I see snake_case in some places, camelCase in others. It does not matter that much which way you choose, as long as you use the same style everywhere.

Consider using C++20's ranges

If possible, consider using C++20's range-based algorithms. These avoid you having to specify the begin and end iterators, and instead just take a reference to the whole container, so there is less to type and less chance of making mistakes.

Reconsider your datatypes

I see both std::map and std::unordered_map. I see the member variable tmp_count in fpgrowth_node, but local function variables visitable and in_tree. All these things have a certain cost, and the performance of your algorithm can be greatly affected by this. For example, lookups and insertions in std::map are \$O(\log N)\$, whereas lookups and insertions in std::unordered_map are \$O(1)\$.

Also consider memory usage of these datastructures. Both std::map and std::unordered_map can make a separate heap memory allocation for each item you insert. So if you can make in_tree a bool member variable of fpgrowth_node, that would save a lot of memory.

Also consider merging maps if possible. Why have separate last_pointer, firstpointer and createdElements maps when they are all indexed by the same key? These maps could be merged by creating a struct that holds the value parts of each of the three original maps.