Skip to content

An application written in Python3 and Tkinter that allows users to draw an undirected weighted graph in a canvas using their mouse, and apply Dijkstra's algorithm to it. Built without libraries like networkx and matplotlib.

License

Notifications You must be signed in to change notification settings

kyletimmermans/dijkstras-canvas

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Version 3.2 Python 3.9 Last Updated kyletimmermans Twitter

Dijkstra's Canvas

Dijkstra's Canvas is an application written in Python3 and Tkinter that allows users to draw a visual undirected weighted graph in the program's window. Using only the mouse, users can click where they want to place different vertex points. They can then draw edges from one vertex to another by first clicking on the source vertex, and then on the destination vertex, creating the connections. At this point, the user can now enter weights for the edges they drew, in order to simulate distance between the vertex points. Finally, they can specify two vertex points and then have the program use Dijkstra's algorithm to find the shortest path between the specified points. The visual aspect of this program is solely created with Tkinter and does not use visual-graphing libraries such as networkx or matplotlib.

Dijkstra's Canvas


Updated v3 Look with Dark Mode

v3.0 Dark Mode Look


Table of Contents

Installation

Download DijkstrasCanvas.zip which contains the .app file here

or

Run Dijkstra's Canvas through command line:

  1. If you don't already have Python 3 on your system, download the installer here.
  2. Run pip3 install tkmacosx
  3. Run wget https://raw.githubusercontent.com/kyletimmermans/dijkstras-canvas/master/DijkstrasCanvas.py
  4. Run python3 DijkstrasCanvas.py

Note: Use --force-run flag in command line to have the program run in any OS

Changelog

v1.0: Initial-Relase
v1.1:
  -Fixed lots of user-input related bugs
  -Fixed edge weight number printing, no longer prints edge weight numbers inside of or on top of lines
  -Added 'Reset Canvas' Button
v1.2:
  -Added Canvas-Buttons separation line
  -Can only have so many shortest path results (8 results) before it reaches the separation line
  -Added more Error Handling
  -Minor bug fixes
v1.3:
  -Added automatic geometry fix for creating edges, no more edges overlapping vertexes
  -Bug fixes
v1.4:
  -Optimization fixes
  -Minor bug fixes
v2.0:
  -Added Windows compatibility
  -Fixed edge weight placement being too far away in some cases
  -Fixed UnboundLocalError: local variable 'vertexDestination' referenced before assignment
  -Fixed ZeroDivisonError in class circleEdgePoint
  -Fixed key error with non-existant edges
  -Fixed addEdgeWeight() input sanitation
  -Fixed dijkstra() input sanitation
  -Fixed NSAlert runModal error on MacOSX when trying to re-size window on x-axis
v2.1:
  -Code cleanup, wrapped lots of math into classes. Deprecated Windows version b/c no anti-aliasing
  -Fixed resize window issue
  -Windows Binary still available
v2.2:
  -Fixed 'sys' module not being recognized
  -Removed binaries from relases, better to compile per machine basis
v3.0
  -Update tkinter code to follow Python3.9
  -Using tkmacosx library to have widgets look more native
  -MacOSX 'Dark Mode' compliant
  -Added app version to window header
  -Added root window geometry for proper window placement
v3.1
  -Added if __name__ == "__main__":
  -Refactor / Moved code into main
  -Added Python Shebang
  -Added --version and -v command line flag
v3.2
  -Check for proper command line usage
  -Added '--force-run' flag for command line which forces program to run on any OS

Usage

  1. Right-click to enter Vertex points at any point in the window, and hit the 'Done' Button next to the input field
  2. Now you can click from any vertex point to any other vertex point to create edges, then hit the second 'Done' Button
  3. Input weights separated by commas and hit 'Input', e.g. A=7, B=8, C=9
  4. Input two vertexes (source and destination. Then click 'Show Results' to see the Shortest Path between the two e.g. v1,v2
  5. Hit the 'Reset Canvas' Button at any point, to remove the graph and all its elements to start over again

Video of Dijkstra's Canvas in action! https://youtu.be/_1Sd_68PKYE


Features

Features:
Reset Canvas Button: Reset the entire graph and start from scratch
Forward and Reverse Path Finding: Go from v1,v2 or from v2,v1 and get its traversal path in reverse!
Automatic Edge Fix: Click on one vertex and then another, the resulting line will always be drawn from the outer-circumference of both vertexes, and it will never overlap the vertex. It is only drawn from the circumference of the vertex, making edges a breeze!
Available for MacOSX (.app): A GUI has been specifically crafted for MacOSX through testing and developing around the OS's rendering system, making Dijkstra's Canvas look like a native app!

Example

Geeksforgeeks.org has a well-made undirected weighted graph image that I will use as an example and re-create it in Dijsktra's Canvas. If we are given a graph such as this one:

Sample Graph

We can draw the same graph in the program and give it the same edge weights.

Graph Translation

Adjacency Matrix

Once the graph is initialized with all its vertexes, edges, and edge weights, the program will take all the data and create an "Adjacency Matrix." A data structure that the path finding algorithm can read and work with. The Adjacency Matrix for the example graph would look something like this:

Adjacency Matrix

For instance, to get from node 0 to node 1, the distance is 4. We can see this in the first row of the 2D Array "adjancencyMatrix." Each row acts as a vertex, and each value in the row represents a distance to another vertex. The index of each value within each row represents the other vertexes. So adjacencyMatrix[0][1] is 4, from node 0 to node 1 has a distance of 4. Using that same logic, adjacencyMatrix[1][0] is also 4. Going backwards from point 1 to point 0 is still 4. This is how the entire matrix is built up, it is the way in which the program can interpret the visual data and find the shortest path of our sketched out graph. If adjacencyMatrix[x][y] = 0, then it indicates that there is no immediate edge/connection between the two points.


Algorithm Implementation

From the start vertex (row), we look for the smallest value in that row. We move to the next vertex which is the index of the smallest value. From there, we find the next smallest value in that row, if the smallest value in this row points to the last vertex (row) or any previously visted vertex (row), we can't use that one and we look for the next smallest value. Rinse and repeat until the smallest path is found.


Error Handling

  1. Can't place vertexes beyond the allowed canvas space, only below separation line
  2. Can't place an edge from a vertex to itself
  3. Can't have more than 52 edges, edge labeling system uses A-Z and when that runs out, a-z (26+26)
  4. Can't give edge weights for non-existant edges
  5. When trying to get the shortest path of two vertexes, will check to see if the two entered vertexes exist
  6. Shortest path of two vertexes and they are the same, e.g. v1,v1. Will return "Path = None | Distance = 0"
  7. Shortest path of two vertexes that are not connected at some point on the graph, will return "No Connection Found"
  8. If the "Shortest Paths" results bank gets too close to the Canvas Separation Line, it will remove the prior short path results and print the current short path result at the top, clearing the bank
  9. Can't draw an edge if its source and destination vertex are the same
  10. Edge weights can't be greater than 999, can't be 0, a negative number, or a float value

Who is Dijkstra?

Edsgar W. Dijkstra was a famous Dutch physicist, mathematician, and computer science pioneer who spent most of his life in a small Netherlands town known as Nuenen. Dijkstra was a professor at two prestigious universities, was a fellow for research boards, and held several awards such as the ACM A.M. Turing Award. He is the reason why this program was possible.


Dijkstra's Algorithm

An algorithm created by Dijkstra, that is used to find the shortest paths from a given source node, to all other nodes in a graph.


Pseudocode

This is the backbone behind his algorithm alt text


Fun

Dijkstra's Canvas

Dijkstra's Canvas

Dijkstra's Canvas

About

An application written in Python3 and Tkinter that allows users to draw an undirected weighted graph in a canvas using their mouse, and apply Dijkstra's algorithm to it. Built without libraries like networkx and matplotlib.

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages