PrivacyScanData/visualize/Visualization-of-popular-algorithms-in-Python

Visualization-of-popular-algorithms-in-Python

Description

The project aims to create visual outputs for popular graph algorithms like DFS,BFS and NP-HARD problems like Travelling Salesman Problem and Graph colouring problems using NetworkX graph library of Python. It is not just limited to getting a visual output, but the algorithms will be optimised to its best by using heuristics for non-polynomial time algorithms. The project aims to create a better understanding of the working of the algorithms, in-depth understanding of the application of heuristics to improve the computation time and usage of the later to our advantage in optimising the algorithm. It could be used by analysts as well as students and teachers, as a teaching aid. It could definitely serve all the applications of Np-hard problems like- School scheduling, Tourist Itineraries, etc.

Motivation

DFS,BFS and NP-Hard algorithms have been there for years now and it has been coded out in every programming language as well. This project aims in visulization of them, to create a better understanding. Solving most of the above mentioned algorithm using brute force-technique might give the optimal solution, however, as the problem size increases, the search for an optimal solution will no longer be worth the effort. Hence, by involving heuristics, we aim to improve the time complexity while arriving at a good solution( need not be optimal always). (Heuristics is used, to predict how close the end of path is to a solution, so that the paths which are judged to be closer to a solution are extended first.)

It includes:

1. DFS:

DFS

2. BFS:

BFS

3. Dijsktra's:

Dijsktra's

4. Prim's:

Prim's

5. Kruskal's:

Kruskal's

6. Assignment Problem:

Assignment Problem

7. Travelling Salesman Problem:

Travelling Salesman Problem

8. Greedy Best First Search:

Greedy BFS

9. A* Search:

A* Search

10. Topological Sort:

Topological Sort

11. Graph Coloring Problem:

Graph-Coloring Problem

12. K Centers Problem:

K Centers Problem

13. Egocentric Network:

Egocentric Network

14. Bellman-Ford algorithm:

Bellman Ford