Supermarket Analysis System - DSA Task 2

📋 Project Overview

This project is a Python-based software solution designed to analyze customer purchasing patterns from supermarket transaction records. It was developed to fulfill the requirements of Task 2: Data Structure and Algorithm, focusing on efficient data modeling, algorithmic analysis, and visualization.

The core of the system is a custom Graph Data Structure that models items as nodes and co-purchases as weighted edges. The application allows users to discover product associations, frequent bundles, and indirect relationships between items using algorithms like Breadth-First Search (BFS) and Quicksort.

Development Methodology: This project strictly followed Test-Driven Development (TDD) practices. Every feature was preceded by a failing test case, ensuring robustness and reliability.

---

📑 Table of Contents

1. Installation & Usage
2. Development Stages (TDD Approach)
   • Stage 1: Data Structure Design
   • Stage 2: Algorithm - Sorting
   • Stage 3: Algorithm - Graph Traversal & Analysis
   • Stage 4: Visualization & GUI
3. Technical Report & Analysis
4. Project Structure
5. Testing

---

📚 Detailed Documentation

For comprehensive guides and technical details, please refer to the docs/ folder:

• User Guide: How to run and use the application.
• Architecture & Diagrams: System design, UML Class Diagrams, ERD, and Algorithm details.
• Implementation Summary: Comprehensive implementation details and verification.

---

🔄 Continuous Integration

This project uses GitHub Actions for automated testing on every push and pull request.

Workflows

• Automated Tests: Comprehensive test suite across 15 configurations (3 OS × 5 Python versions)
• Quick Test: Fast feedback for rapid iteration
• Code Quality: flake8 and pylint checks
• Coverage: Test coverage reporting with artifacts
• Performance: Automated benchmarks to detect regressions

View workflows in the .github/workflows/ directory.

---

🚀 Installation & Usage

Prerequisites

• Python 3.8+
• Required libraries: networkx, matplotlib (for visualization only), tkinter (included with Python).

Setup

1. Clone the Repository:

   git clone <repository-url>
   cd DSA-Supermarket-Analysis

2. Install Dependencies:

   pip install -r requirements.txt

3. Run the Application:

   python main.py

4. Run Tests:

   python test_main.py

---

🛠 Development Stages (TDD Approach)

This project was built in distinct stages. For each stage, we defined the requirements, wrote the tests, and then implemented the code.

Stage 1: Data Structure Design

Goal: Create an efficient structure to store items and their relationships.

• Choice: Undirected Weighted Graph using Adjacency Lists.
• Justification: Market data is sparse (most items are not bought with most other items). An Adjacency Matrix would be $O(N^2)$ in space (mostly zeros). An Adjacency List is $O(V + E)$, which is memory efficient.

TDD Step 1: Write Test (tests/unit/test_models.py) We first wrote test_add_node_and_edge to assert that adding an edge also adds the nodes and sets the correct weight.

def test_add_node_and_edge(self):
    self.graph.add_edge("Bread", "Milk", 1)
    self.assertEqual(self.graph.get_weight("Bread", "Milk"), 1)

Implementation (src/models/market_graph.py) We implemented the MarketGraph class using Python's defaultdict for O(1) average lookup time.

class MarketGraph:
    def __init__(self):
        # graph[u][v] = weight
        self.graph = defaultdict(lambda: defaultdict(int))

Stage 2: Algorithm - Sorting

Goal: Rank items and bundles by frequency without using built-in sort().

• Choice: Quicksort.
• Justification: Quicksort has an average time complexity of $O(N \log N)$ and performs well in-memory.

TDD Step 2: Write Test (tests/unit/test_models.py) We defined a test case test_quicksort_basic with a known unsorted list.

Implementation (src/utils/sorting.py) We implemented a recursive Quicksort function that supports a custom key_func (for sorting tuples by score) and a reverse flag.

def quicksort(data, key_func=lambda x: x, reverse=False):
    if len(data) <= 1: return data
    pivot = data[len(data) // 2]
    # ... partition logic ...

Stage 3: Algorithm - Graph Traversal & Analysis

Goal: Analyze the graph to find indirect connections and calculate confidence.

• Algorithm 1: Breadth-First Search (BFS).
  • Why: BFS is optimal for finding the shortest path (or "degrees of separation") in an unweighted or uniformly weighted sense for connection depth.
• Algorithm 2: Depth-First Search (DFS).
  • Why: DFS explores deep connection chains and is useful for finding all reachable items through recursive traversal.
• Algorithm 3: Association Rule Mining (Confidence).
  • Formula: $Confidence(A \to B) = \frac{Support(A \cup B)}{Support(A)}$

TDD Step 3: Write Test (tests/integration/test_pipeline.py) We created a small synthetic dataset where "Apple" is bought with "Banana". We asserted that get_recommendations("Apple") returns "Banana".

Implementation (src/controllers/analyzer.py)

• find_indirect_associations: Uses a deque to implement BFS, exploring neighbors layer by layer up to max_depth.
• find_all_reachable_items_dfs: Uses recursion to implement DFS, exploring deep connection chains.
• calculate_confidence: Computes the conditional probability of purchase.

Stage 4: Visualization & GUI

Goal: Provide a user-friendly interface to interact with the data.

• Implementation: Tkinter for the dashboard and NetworkX/Matplotlib for the graph visualization.

Features:

1. Dashboard: View statistics, select items, and see tables of recommendations.
2. Visualization:
   • Full Graph: See the global network structure.
   • Focused View: See only a specific item and its immediate neighbors (Ego Graph).

---

📊 Technical Report & Analysis

1. Complexity Analysis

• Graph Construction: $O(T \times M^2)$ where $T$ is transactions and $M$ is the average basket size. Since $M$ is usually small (<20), this is linear with respect to the number of transactions.
• Lookup/Query: $O(1)$ to find if two items are connected.
• Recommendations: $O(K \log K)$ where $K$ is the number of neighbors (degree of the node), dominated by the sorting step.
• BFS Traversal: $O(V + E)$ in the worst case, but limited by max_depth to keep it practically instantaneous.
• DFS Traversal: $O(V + E)$ recursive exploration, also limited by max_depth parameter.

2. Scalability Evaluation

• Current Performance: The system handles the 15,000 transaction dataset in under 1 second on standard hardware.
• Memory: The adjacency list is highly memory-efficient for this sparse dataset.
• Limitations: If the number of items grows to millions (e.g., Amazon scale), a single in-memory dictionary would fail.
• Future Improvement: For "Big Data" scale, we would migrate the graph to a dedicated Graph Database (like Neo4j) or use a distributed framework like Apache Spark (GraphX).

3. Alternative Approaches

• Matrix Approach: Rejected due to $O(N^2)$ memory usage.
• Apriori Algorithm: Considered for itemset mining, but the Graph approach was chosen for its flexibility in traversal and real-time query capabilities.

---

📂 Project Structure

DSA-Supermarket-Analysis/
├── main.py                  # Entry point
├── test_main.py             # Test runner
├── requirements.txt         # Dependencies
├── Supermarket_dataset_PAI.csv
├── src/
│   ├── controllers/
│   │   ├── analyzer.py      # Core Analysis Logic (BFS, Mining)
│   │   └── data_loader.py   # CSV Parser
│   ├── models/
│   │   └── market_graph.py  # Graph Data Structure
│   ├── utils/
│   │   └── sorting.py       # Custom Quicksort
│   └── views/
│       └── gui.py           # Tkinter Dashboard
└── tests/                   # Comprehensive Test Suite
    ├── integration/
    ├── system/
    └── unit/

---

✅ Testing

To run the automated test suite, which includes unit tests for the data structures and integration tests for the full pipeline:

python test_main.py

Test Coverage:

• test_models.py: Verifies Graph behavior and Quicksort correctness.
• test_pipeline.py: Verifies end-to-end flow from CSV loading to Analysis results.
• test_gui_flow.py: Verifies system components availability.

---

🛠️ System Architecture

graph TD
    A[Supermarket Inventory & Layout Map] --> B[Graph Modeling - Aisles & Nodes]
    B --> C[Queue Management System - Queues & Arrays]
    C --> D[Breadth-First Search - Shortest Pathfinding]
    D --> E[Custom QuickSort - Pricing & Popularity Sorting]
    E --> F[Optimized Shopping Path & Checkout Plan]

Loading