The package is not currently available on PyPI or any other Python package repository. The easiest way to install it is to clone the GitHub repository and install it from source.
- Python 3.7 or newer
- Git
- Make
Run the following commands in a shell (a UNIX-like environment is assumed):
$ git clone [email protected]:jimmyg1997/Python-Graph-Algorithmic-Problems-Visualizations/
$ cd Python-Graph-Algorithmic-Problems-Visualizations/
$ make install
The package does not have any dependencies besides Python itself. If you wish to sandbox your installation inside a virtual environment, you may choose to use virtualenvwrapper or a similar utility to do so.
When successfully installed, the following programs will be available and placed on your PATH
. See the Usage section below for details about how to use these programs.
- labyrinth
This is a project that explores algorithmic graph theory by visiting some of known graph algorithmic problems and visual solutions. The main goal is to systematically present essnetial key examples that highlight efficients algorithms in a visual representation. Most of the key techniques from these algorithms have already found applications in optimization, machine learning and statistics.
Program | Problem Solved | Algorithms Used | |
---|---|---|---|
#1 | Labyrinth | Shortest Path (undirected, unweighted) | โข Grid Generation : {binary, sidewinder} โข Shortest Path : {bfs, dfs} |
At any time, you can use the -h
or --help
flags to see a summary of options that the program accepts.
$ labyrinth -h
usage:labyrinth [-h] [-s SYMBOLS] [-f GRID_FN] [-ag {binary,sidewinder}] [-d DIMENSIONS] [-p BINARY_PCT] [-ap {dfs,bfs}]
Parse or generate labyrinth and find exit paths using different algorithms
optional arguments:
-h, --help show this help message and exit
-s SYMBOLS, --symbols SYMBOLS
Give the 4 symbols in the following order : Wall->Move->Start->End
-f GRID_FN, --grid_fn GRID_FN
[Grid][Method#1 Parsing] Give the name of the csv file for the grid
-ag {binary,sidewinder}, --algorithm_generate {binary,sidewinder}
[Grid][Method#2 Generation] The algorithm to generate the grid labyrinth
-d DIMENSIONS, --dimensions DIMENSIONS
[Grid][Method#2 Generation] Give width / height of the generated grid
-p BINARY_PCT, --binary_pct BINARY_PCT
[Grid][Method#2 Generation] Give ghe percentage of the biomial geration
-ap {dfs,bfs}, --algorithm_shortest_path {dfs,bfs}
The algorithm to find the path in a labyrinth
Typical usage is labyrinth -ag <algorithm_generation> -d <dimensions>
, where <algorithm_generation>
can be binary
, sidewinder
and <dimensions>
is a string like 10x10 describing the dimensions of the maze to generate (width x height). The program will generate a random maze of the given size and print an ASCII representation of the maze to the console
Example
labyrinth -s "# ๐๐" -ag binary -d 6x6 -p 0.9 -ap bfs
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
| โ
๐๐๐ฒ๐ฝ ๐ญ : Constructing (1) Grid (2) Graph |
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
| โ
๐๐๐ฒ๐ฝ ๐ฎ : Find shortest path (undirected, unweighted) |
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
| โ
๐๐๐ฒ๐ฝ ๐ฏ : Visualize shortest path if existing |
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
# # # # # # # # # # # # # # # # # #
# โฃ โ โ โ โ โ โ โ โ โ #
# # # # # โฃ # # # # # # โก #
# # # # # โฃ # # # # # # โก #
# # # # # โฃ # # # # # # โก ๐
# # # # # โฃ # # # # # # #
# # # # # โฃ # # # # # # #
# # # # # โฃ # # # # # # #
# # # # # # โฃ # # # # # # #
# # # # # # โฃ # # # # # # #
# # # โฃ โ โ โ # # # # # # #
# # # # โฃ # # # # # # # # #
# # # # โฃ # # # # # # # # #
# โฃ โ โ โ # # # # # # # # #
# โฃ # # # # # # # # # # #
๐ โ # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
This project owes a massive debt of gratitude to the following resources :
- Maze Grid Generation
- Series of articles on maze generation featured on Jamis Buck's blog. The step-by-step breakdown of various algorithms, along with simple diagrams and animations showing how the algorithms work, were invaluable in creating my own adaptations of these algorithms.
- Wikipedia - Maze Generation
- Pymazes Github repo
- Maze Shortest path
- The article on maze-solving algorithms on the website of Beanz magazine also came in handy for understanding the concept of the "junction graph" and using tree traversal to solve mazes.
- Wikipedia - Maze Solving Algorithm