Visualize Graph Algorithms
Project description
Visualisation of Graph Algorithms
Description
The package aims to create visual outputs for popular graph algorithms. Currently: BFS and DFS I plan to implement more algorithms: - Topological Sort - Prim's and Kruskal's Algorithms etc
It is not just limited to getting a visual output, but the algorithms will be optimised by using heuristics for non-polynomial time algorithms. This project aims to create a better understanding of the working of graph algorithms, improve the computation time and optimising the algorithms. It could be used by analysts as well as students and teachers, as a teaching aid.
To run the package: pip install graph-algo-vis
Sample Code to run the package
Import: from graph_algo_vis import dfs_traversal
Instantiation: g = dfs_traversal.DFS()
Visualize the input graph: g.draw_graph("input.txt")
Visualize the result of DFS: g.depth_first_search("input.txt")
Pre requisites
To run this package run you must have matplotlib and networkx libraries installed.
INPUT
Input is taken from the file
input.txt
Sample input for BFS and DFS
4
0 5 10 5
0 0 5 0
0 10 0 0
0 0 10 0
0
First line contains the number of nodes,say n.(Nodes are numbered as 0,1,2,...(n-1) ) Followed by n*n weighted matrix. Disconnected egdes are represented by negative weight. Last line contains the source node.(i.e, the node from which the BFS or DFS should begin)
Draw Graph
Graph is first drawn from the weighted matrix input from the user with weights shown. Edges are marked with black. visualization of the input graph-
BFS Traversal
Iterative BFS is performed, using a queue. Each time an edge is encountered, it is marked with red on the graph.
DFS traversal
Recursive DFS is performed, resulting DFS forests are stored in a stack.
Visualization of the result-
Time Complexity
0(m+n)
where m - number of edges
n - number of nodes
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for graph_algo_vis-0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fcbb89ad71b844fe33df7ed583f441aa1ce58b9194e2acae53c44fd774fb57bf |
|
MD5 | 252fcea5b0b43a925e00bfba9ffc6310 |
|
BLAKE2b-256 | 6cc95cc509b44d49b2b802d0dfe412e81cd24a6a4e2142867b9487b92a2cdc46 |