In real-world scenarios such as transportation networks, urban planning, and logistics, understanding the interconnections between locations (cities) is crucial for optimizing travel paths, ensuring network reliability, and detecting potential cycles. Graph theory plays a fundamental role in these domains, where algorithms for tasks like pathfinding, connectivity analysis, cycle detection, and minimum spanning trees (MST) are essential for improving system efficiency and performance. This project applies graph theory to solve these challenges, helping to model and analyze city networks effectively.
This repository showcases the implementation of key graph algorithms and techniques using various graph representations such as adjacency lists, adjacency matrices, and edge lists. The project includes functions to handle directed, weighted graphs, and addresses common graph-related problems such as:
- Strong Connectivity: Checking if a directed graph is strongly connected, and if not, generating edges to make it strongly connected.
- Cycle Detection: Detecting cycles in a directed graph and generating random edges to form a cycle if none exists.
- Shortest Path Calculation: Allowing the user to select two cities and compute the shortest path between them. If no path exists, the program generates random edges to ensure a path is found.
- Minimum Spanning Tree (MST): Allowing the user to select edges and compute the MST for the graph. If no MST exists, random edges are added until one is found.
This tool is useful for applications such as transportation planning, route optimization, and network analysis.
- Graph Representation: Supports adjacency list or matrix-based representation of graphs.
- Connectivity Check: Can verify if the graph is strongly connected.
- Cycle Detection: Identifies cycles within the graph and generates edges to form a cycle if absent.
- Shortest Path Finder: Computes the shortest path between any two cities selected by the user.
- Minimum Spanning Tree (MST): Calculates the MST from selected edges.
- Interactive Graph Management: Add or remove edges dynamically and visualize graph updates.
- Graph Visualization: Uses Matplotlib to visualize the current state of the graph and edge weights.
- Python: The main programming language used to implement the project.
- NetworkX: A Python package used for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.
- Matplotlib: A Python plotting library used for visualizing the graph structure.
- OS: Used for clearing the screen between different steps.
This project is not open for public cloning or redistribution without prior written permission from the author as stated in . If you would like to access this project, please reach out to the repository owner to request permission.
Once written permission is granted, you will receive detailed instructions on how to install and run the system, including all necessary steps and dependencies.
Similar to the installation process, usage instructions will be provided only after written permission is granted to access this repository. Upon receiving access, you will be provided with step-by-step instructions on how to use this system/application, including on how to run the program, interact with it and exploring all the key features stated.