Graph Algorithm Visualizer

A Python application to visualize graph algorithms including:
⁃ Depth First Search ⁃
⁃ Breadth First Search ⁃
⁃ Dijkstra's Shortest Path Algorithm ⁃
⁃ Prim's Minimum Spanning Tree Algorithm ⁃
⁃ Kruskal's Minimum Spanning Tree Algorithm ⁃
⁃ Ford Fulkerson Maximum Flow Algorithm ⁃

View Code · Report Bug · Request Feature

Table of Contents

1. About The Project
   • Built With
2. Getting Started
   • Prerequisites
   • Installation
3. Demos
4. Roadmap
5. Contributing
6. License
7. Contact
8. Acknowledgments

About The Project

Over Fall 2023 winter break, I decided to spend some time refreshing my knowledge of several graph algorithms and to learn more about python networkx and tkinter visualization.

This project includes a simple user interface that guides the user through the input process step by step. The application supports a combination of file input and individual edge input with thorough checks to ensure the inputted graph meets the requirements for the algorithm selected.

The graph's node colors and edge colors change to show step by step iterations of the selected algorithm.

(back to top)

Built With

(back to top)

Getting Started

To get a local copy up and running, follow the instructions below:

Prerequisites

This project requires the following dependencies to run:

• matplotlib

  pip install matplotlib

• networkx

  pip install networkx

• tkinter

  pip install tkinter

• graphviz

  See installation instructions at https://graphviz.gitlab.io/download/

• pygraphviz

  Note: graphviz must be installed first

  pip install pygraphviz

• tktooltip

  pip install tkinter-tooltip

Installation

1. Ensure all prerequisites are installed correctly
2. Clone the repo

   git clone https://github.com/kea-roy/GraphAlgoVisualizer.git

3. Run main.py

(back to top)

Demos

See below for several examples of the graph algorithm visualizer iterating through the different algorithms.

Depth First Search

A depth first search starting at node A.

Breadth First Search

A breadth first search starting at node A.

Dijkstra's

Dijkstra's algorithm for finding the shortest paths to all nodes from node A.

Prim's

Prim's algorithm for finding the minimum spanning tree of the connected graph

Kruskal's

Kruskal's algorithm for finding the minimum spanning tree of the connected graph

Ford-Fulkerson

Ford-Fulkerson algorithm to find the maximum flow from source node A to sink node H

(back to top)

Roadmap

• Add Feature: Import Graph via File
• Add Feature: Import Graph via Edge
• Add Features: Algorithm Support
  • DFS
  • BFS
  • Dijkstra's
  • Prim's
  • Kruskal's
  • Ford-Fulkerson
• Add Feature: Previous and Next Iteration Button
• Add Feature: ToolTip for Edge Input Format

See the open issues for a full list of proposed features (and known issues).

(back to top)

Contributing

Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

(back to top)

License

Distributed under the MIT License. See LICENSE.txt for more information.

(back to top)

Contact

Kea-Roy Ong - ko353@cornell.edu

Project Link: https://github.com/kea-roy/GraphAlgoVisualizer

(back to top)

Acknowledgments

I would like to acknowledge the following resources that were used in the process of completing this project

• NetworkX Official Documentation Site
• NeuralNine: NetworkX Crash Course - Graph Theory in Python
• Stack Overflow: NetworkX Tkinter Ford-Fulkerson Question
• othneildrew's README Template

(back to top)