Posts

Trivial Class vs Aggregate Structure Trivial Class A trivial class is a class that: Has a trivial default constructor. Has a trivial copy constructor. Has a trivial move constructor (since C++11). Has a trivial copy assignment operator. Has a trivial move assignment operator (since C++11). Has a trivial destructor. Has no virtual functions or virtual base classes. The trivial constructors/operations/destructor means they are not user-provided (i.e., is implicitly-defined or defaulted on its first declaration)....

The table summarizes how brackets {} and () are related to list-initialization in various contexts. The column Allows Narrowing Conversion indicates whether implicit type conversions that lose information are allowed. The column Allows Explicit Constructors indicates whether the syntax can call constructors marked as explicit. The columns Use for Aggregates and Use for User-Defined Types show the applicability of each initialization type for aggregates like arrays (e.g., int x[3][4]) and structs, and user-defined types like classes, respectively....

Note The SCAN (Structural Clustering Algorithm for Networks) algorithm is used for detecting clusters in graphs. It also looks at the structural similarity between nodes: $$ s(A, B) = \frac{|N(A) \cap N(B)|}{\sqrt{|N(A)| \times |N(B)|}} $$ Compute Structural Similarity: For each edge (A,B)(A,B), compute its structural similarity score. Identify Strong Relations: Mark edges as ‘strong’ if their structural similarity is above **eps. Identify Core Nodes: For each node, count its strong relationships....

The core reason for my re-implementing the standard containers is the Priority Queue (or namely Max Heap). It combines algorithms and fundamental data structures to create a sophisticated yet highly efficient data structure. My current focus on reinventing these containers has temporarily paused here. Similar containers, like flat_set, are slated for release in C++23. When they become available, I plan to continue this series by attempting to re-implement them. Description A priority queue is a container adapter offering constant time access to the largest (by default) element, albeit at the cost of logarithmic time insertion and extraction....

Description Strongly Connected Components operates the directed graph in which there is a directed path from each vertex to every other vertex. Weakly Connected Component (the one we discussed before) ignores the direction of the edges. WCC is commonly considered the “default” CC algorithm, if there isn’t a specification for Strongly or Weakly. Kosaraju’s Algorithm: Run 1st DFS to get finishing times of each vertex (i.e., postordering of DFS). [Backtracking] Run 2nd DFS on the transposed graph, starting with the visited vertices in Reverse Post-Order Each DFS tree in step 2 is an SCC....

Description Both std::queue and std::stack are container adaptors that rely on an underlying container to provide specific functionality. For example: std::queue implements a First-In-First-Out (FIFO) flow, making it efficient to remove the front element. It can use std::deque (by default) or std::list as the underlying container. std::stack follows a Last-In-First-Out (LIFO) flow, where the back element needs efficient modification. By default, it uses std::deque but can also be based on std::list or std::vector....

Description A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a tree that spans all the vertices in the graph and has the minimum possible total edge weight among all the trees that can be created from the graph. In simpler terms, it’s a subgraph that includes all the vertices, is a tree (meaning it has no cycles), and the sum of its edge weights is as small as possible....

Description The implementation of unordered containers rely on hashing techniques and utilize buckets for storing elements. Each bucket is essentially a vector containing a (singly) linked list. The following steps outline how elements are located, whether for finding, inserting, or erasing: Compute the hash value of the key. Determine the bucket index by taking the remainder of the hash value divided by the bucket size, e.g., index = {hash value} % {bucket size}....

Description Both std::set and std::map are underpinned by red-black trees (RBT). RBTs are self-balancing binary trees, albeit not perfectly balanced. In this structure, it’s ensured that the values (for std::set) or keys (for std::map) adhere to the following condition: node→left < node < node→right. Consequently, the RBT are considered ordered, so std::set and std::map are called ordered containers. RBT are characterized as follows: Property A node is either red or black....

count how many triangles can be formed inside the graph undirected graph, and each triangle would be counted for three times, once per node. $O(n^3)$ #include <iostream> #include <vector> // Reference: https://github.com/georgegito/vertexwise-triangle-counting/blob/master/src/v3/v3_seq.cpp // allow for parallelism auto bfs_tc(const std::vector<int>& rowPtr, const std::vector<int>& colIdx) { int numTriangles = 0; const auto numVertices = rowPtr.size() - 1; // check if two nodes have an edge between them with binary search (require sorted colIdx) auto intersect = [&](int first, int second) -> bool { // std::find is O(N), assuming the iterator is a forward iterator // auto first_begin = colIdx....