Graph Explorer

A visual graph theory application developed as part of the Graph Algorithms course at university. This project implements various graph manipulation tools and minimum spanning tree algorithms using Delphi/Pascal.

Academic Context

This project was created for the Graph Algorithms course at my university. It demonstrates the implementation of fundamental graph algorithms and data structures, with a focus on minimum spanning tree construction using different variations of Kruskal's algorithm.

Features

Graph Manipulation

• Interactive Graph Creation: Click to add vertices, drag between vertices to create edges
• Visual Editor: Real-time visual representation of graphs
• Graph Editing: Modify vertex positions, colors, edge weights, and colors
• File I/O: Save and load graphs for later use
• Random Graph Generation: Generate random vertices and edges with configurable parameters

Graph Generation Tools

• Add Random Vertices: Generate a specified number of randomly positioned vertices
• Complete Graph: Create a complete graph from existing vertices
• Edge Generation by Density: Add edges based on a density percentage (0-100%)
• Edge Generation by Weight: Add edges up to a maximum weight threshold

Data Structures

• Adjacency Matrix: Real-time visualization of graph connectivity
• Vertex List: Track vertex properties (position, degree, color)
• Edge List: Manage edge properties (endpoints, weight, color)

Algorithms

Minimum Spanning Tree (MST) Algorithms

The application implements three variations of Kruskal's algorithm:

1. Kruskal-R (Relabeling)

   • Basic implementation using relabeling technique
   • Updates all vertices with the same root when merging components
   • Displays MST weight and iteration count

2. Kruskal-DS (Disjoint Sets)

   • Uses disjoint set data structure with path traversal
   • More efficient than basic relabeling
   • Finds roots by following parent pointers

3. Kruskal-DS+PC (Disjoint Sets with Path Compression)

   • Optimized version with path compression
   • Flattens tree structure during root finding
   • Most efficient implementation
   • Best performance for large graphs

Graph Analysis

• Graph Statistics:
  • Vertex count and edge count
  • Maximum possible edges
  • Graph density calculation
  • Minimum, maximum, and average vertex degree

Technical Stack

• Language: Object Pascal (Delphi)
• Framework: VCL (Visual Component Library)
• IDE: Embarcadero Delphi
• Graphics: GDI-based canvas rendering

Project Structure

AG_CP_2_016_MI/
├── MainUnit.pas              # Main application logic and algorithms
├── MainUnit.dfm              # Main form design
├── EditVertexUnit.pas        # Vertex editor dialog
├── EditVertexUnit.dfm        # Vertex editor form design
├── EditEdgeUnit.pas          # Edge editor dialog
├── EditEdgeUnit.dfm          # Edge editor form design
├── AddRandomVerticesUnit.pas # Random vertex generation dialog
├── AddRandomVerticesUnit.dfm # Random vertex dialog design
├── GraphExplorer_BASIC_SOL.dpr    # Project file
├── GraphExplorer_BASIC_SOL.dproj  # Project configuration
└── README.md                 # This file

How to Use

Creating a Graph

1. Add Vertices: Click anywhere on the canvas to create a vertex
2. Add Edges: Click and drag from one vertex to another to create an edge
3. Edit Properties:
   • Select a vertex/edge from the list
   • Use the Edit menu to modify properties (position, color, weight)

Generating Graphs

1. Random Vertices: Graph → Add Random Vertices → Enter count
2. Complete Graph: Add vertices first, then Graph → Add Edges to Complete Graph
3. By Density: Graph → Add Edges by Density → Enter percentage (0-100)
4. By Weight: Graph → Add Edges by Weight → Enter maximum weight threshold

Finding MST

1. Click Init to initialize the algorithm and reset colors
2. Click Sort Edges to sort edges by weight (required for Kruskal's algorithm)
3. Choose an algorithm:
   • Kruscal-R: Basic relabeling approach
   • Kruscal-DS: Disjoint sets implementation
   • Kruscal-DS+PC: Optimized with path compression
4. View results in the output panel (MST weight and iteration count)
5. MST edges are highlighted in blue, MST vertices in aqua

Graph Management

• New Graph: File → New
• Save Graph: File → Save / Save As
• Load Graph: File → Open
• Remove Vertex: Select last vertex with degree 0, then Graph → Remove Vertex
• Remove Edge: Graph → Remove Edge (removes last edge)

Algorithm Complexity

Algorithm	Time Complexity	Space Complexity
Kruskal-R	O(E² + EV)	O(V)
Kruskal-DS	O(E·α(V))	O(V)
Kruskal-DS+PC	O(E·α(V))	O(V)

Note: α(V) is the inverse Ackermann function, which grows extremely slowly

Learning Objectives

This project demonstrates understanding of:

• Graph data structures (adjacency matrix, edge list)
• Graph algorithms (MST construction)
• Union-Find data structure and optimizations
• Algorithm complexity analysis
• Visual algorithm representation
• Interactive GUI development

Building the Project

1. Open GraphExplorer_BASIC_SOL.dproj in Embarcadero Delphi
2. Build → Compile
3. Run → Run (or F9)