Graph Analytics Framework in C++

Architecture

Architecture of the graph framework showing the AbstractGraph interface, linked-list and adjacency-matrix implementations, and algorithm modules for Tarjan SCC detection and diamond pattern search.

The Challenge

The objective was to build a flexible graph framework capable of storing large directed graphs, supporting multiple internal representations, and running analysis algorithms without coupling to a specific backend. A key design requirement was ensuring that algorithms depended only on an abstract graph interface rather than a specific data structure implementation.

Graph Representations

The framework contains two independent graph implementations sharing a common abstract interface:

• Incidence List Graph — linked Node and Edge objects with incoming/outgoing edge lists; efficient traversal, supports multi-edges
• Adjacency Matrix Graph — 3D matrix structure with constant-time edge lookup; supports directed multigraphs

Algorithms Implemented

• Tarjan's Strongly Connected Components (SCC)
• Diamond pattern detection
• Depth-First Search (DFS) traversal
• Graph reachability queries

Tarjan's Strongly Connected Components

Tarjan's algorithm finds all groups of nodes where every node can reach every other node in the group:

Implemented from scratch using depth-first search, discovery indices, low-link values, and an explicit stack. The algorithm runs in O(V + E) time and operates transparently on both graph implementations through a shared abstract interface.

Diamond Pattern Detection

Diamond detection finds pairs of nodes connected by two parallel paths that diverge and then converge — a structure common in knowledge graphs and dependency analysis:

Two distinct paths connect A and D: A → B → D and A → C → D. The query engine searches for this structure across the full graph using DFS-based path enumeration, supporting custom edge-label sequences for flexible pattern matching.

Performance Analysis

Runtime comparison of Tarjan's strongly connected components algorithm using adjacency-list and adjacency-matrix graph representations. The same algorithm shows significantly different scaling behaviour depending on the underlying data structure.

Benchmarking diamond-pattern detection across graph sizes using both graph implementations. Results were visualized using log-log plots to analyze asymptotic behaviour and compare theoretical and observed complexity growth.

Memory Management

The linked graph implementation manages dynamically allocated nodes and edges using raw pointers. To ensure safe ownership semantics, the project implements the full Rule of Five: destructor, copy constructor, copy assignment operator, move constructor, and move assignment operator. Deep-copy functionality reconstructs all node-edge relationships while move operations efficiently transfer ownership.