GraphForge: Graph Analysis & Visualization Framework

A modular C++ framework for graph construction, visualization, parsing, traversal, optimization, and matrix-based graph analysis.

---

Overview

GraphForge is a comprehensive graph-processing framework developed in C++ that combines graph theory, data structures, file parsing, matrix algebra, and visualization into a single modular system.

The framework enables users to:

• Create directed and undirected graphs
• Work with weighted and unweighted graphs
• Automatically generate Graphviz DOT files
• Visualize graphs through rendered images
• Execute classical graph algorithms
• Analyze graph-theoretic properties using adjacency matrix operations
• Visualize algorithm outputs such as BFS trees, DFS trees, and Minimum Spanning Trees

Unlike traditional graph algorithm implementations that only print results, GraphForge provides a complete workflow from graph creation to graphical visualization.

---

Features

Graph Construction

• Interactive graph creation through terminal input

• Support for:

  • Directed Graphs
  • Undirected Graphs
  • Weighted Graphs
  • Unweighted Graphs

• Automatic DOT file generation

• Automatic Graphviz rendering

---

Graph Parsing Engine

The framework includes a dedicated parser that:

• Reads DOT files generated by the system
• Detects graph type automatically
• Extracts graph vertices
• Constructs adjacency matrix representations
• Creates a reusable graph abstraction layer

---

Graph Algorithms

Traversal Algorithms

• Breadth First Search (BFS)
• Depth First Search (DFS)

Shortest Path Algorithms

• Dijkstra's Algorithm

Tree Algorithms

• Minimum Spanning Tree (Prim-based)

Graph Analysis

• Topological Sorting
• Degree Analysis
• Cycle Detection

Matrix-Based Analysis

• Matrix Multiplication
• Matrix Addition
• Path Counting
• Path Matrix Generation
• Connectivity Analysis
• Strongly Connected Component Detection

---

Workflow

User Input
     │
     ▼
InputGraph.cpp
     │
     ▼
DOT File Generation
     │
     ▼
Graphviz Rendering
     │
     ▼
Graph Visualization
     │
     ▼
ReadGraph.cpp
     │
     ▼
Graph Abstraction Layer
     │
     ▼
Graph Algorithms
     │
     ▼
Analysis & Visualization

---

Project Architecture

InputGraph.cpp
        │
        ▼
ReadGraph.cpp
        │
        ▼
Graph Object
        │
 ┌──────┼──────────────┬─────────────┬─────────────┐
 ▼      ▼              ▼             ▼             ▼

BFS    DFS        Dijkstra        MST      Topological
 │      │             │            │           Sort
 ▼      ▼             ▼            ▼

Visualization    Shortest      Tree
Modules          Paths         Generation

        ▼
Degree Analysis
Cycle Detection
Matrix Operations
SCC Detection

---

Demonstration

1. Graph Creation

The user creates a graph using terminal input.

Terminal Input

Generated DOT Code

Generated Graph Visualization

---

2. Breadth First Search Visualization

GraphForge performs BFS traversal and generates a highlighted BFS spanning tree.

BFS Terminal Output

BFS Spanning Tree

---

3. Depth First Search Visualization

GraphForge performs DFS traversal and generates a highlighted DFS spanning tree.

DFS Terminal Output

DFS Spanning Tree

---

4. Minimum Spanning Tree Visualization

The MST module computes a minimum-cost spanning tree and highlights selected edges.

MST Terminal Output

MST Visualization

---

5. Dijkstra's Algorithm

Computes shortest path distances from a selected source vertex.

Dijkstra Terminal Output

---

6. Topological Sorting

Performs topological ordering on directed acyclic graphs.

Topological Sort Output

---

7. Degree Analysis

Computes in-degrees and out-degrees of graph vertices.

Degree Analysis Output

---

8. Cycle Detection

Detects and counts cycles associated with graph vertices.

Cycle Detection Output

---

9. Matrix Operations and SCC Detection

Performs graph-theoretic matrix operations and connectivity analysis.

Matrix Operations Output

---

Repository Structure

GraphForge/
│
├── InputGraph.cpp
├── ReadGraph.cpp
│
├── BFS Spanning Tree.cpp
├── DFS Spanning Tree.cpp
├── Djikstra's Algorithm.cpp
├── Minimum Spanning Tree.cpp
├── Topological Sorting.cpp
├── Degree.cpp
├── No_Of_Cycles.cpp
├── MatrixOperations.cpp
│
├── Priority_Queue_Array.cpp
│
├── Dot Files/
│
├── Images/
│
└── Terminal Screenshots/

---

Languages and Data Structures Used

• C++

• Graph Theory

• Graphviz

• DOT Language

• Adjacency Matrix Representation

• Matrix Algebra

• STL Containers

  • vector
  • queue
  • priority_queue

• Custom Priority Queue Implementation

---

Key Learning Outcomes

This project demonstrates practical implementation of:

• Graph Data Structures
• Graph Traversal Algorithms
• Shortest Path Algorithms
• Minimum Spanning Trees
• Topological Sorting
• Graph Visualization
• File Parsing
• Matrix-Based Graph Theory
• Strongly Connected Components
• Software Modularization
• Custom Data Structure Design

---

Future Improvements

• Kruskal's Algorithm
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm
• A* Search
• Kosaraju's Algorithm
• Union-Find Data Structure
• Adjacency List Representation
• GUI-based Graph Builder
• Interactive Visualization Dashboard

---

Author

MAYUKH PAUL

Indian Institute of Technology, Kharagpur

---

License

This repository is intended for academic, educational, and research purposes. For reuse or collaboration, please contact the author.