sukhrobjon/self-driving-cars-graph

CS-2.2 Graph project proposal

Modeling Map Using Graph Theory

Project Proposal

• This project will tackle the common problem of modeling maps. When we use maps we always want choose the fastest route or sometimes safest route. The entire premise of Google Maps is using a big giant graph with nodes and edges to figure out fastest or shortest way to travel. That’s all Google Maps is–a big graph with lots of nodes and edges.resource

Getting Started

This project solve the followings:

1. Shortest Path from A to B(using Dijkstra's algorithm)
2. The busiest intersection(most connected vertex)
3. Find near me(find all location near by specified miles)

Graph component specific to this project:

• Vertices are the locations on the map.
• Weights are the distance(in miles) between them.

Details

• It is assumed that the graph is undirected
• Documentation can be found here
• Blog post on medium

Installing

Clone the project

git clone https://github.com/Sukhrobjon/self-driving-cars-graph.git

Running on Terminal

cd self-driving-cars-graph

python3 run.py Graphs/inputs/maps_data.txt

Sample Output

=========================Visualize the map: Make a graph=========================
Vertices: ['A', 'B', 'C', 'D', 'E', 'F', 'G']
Number of Edges: 9
The Edge List:
('A', 'D', 15)
('A', 'E', 12)
('A', 'F', 72)
('A', 'G', 7)
('G', 'B', 55)
('B', 'C', 12)
('C', 'D', 7)
('D', 'E', 33)
('E', 'F', 11)
=========================Problem One: Fastest Route=========================
Fastest route from A to C is: A->D->C with total distance of 22 miles!
=========================Problem Two: Busiest Intersection=========================
A connected 4 of intersections.
=========================Problem Three: Find near me=========================
These locations are 25 away from A.
Locations are: C, D, E, F, G

Authors

• Sukhrob Golibboev - Initial work - Modeling Maps

License

This project is licensed under the MIT License - see the LICENSE.md file for details

self-driving-cars-graph's Issues

Final Project Feedback

Final Project Feedback

Overall 20/ 33 (> 20 Passing):

• Proposal 1/4
• Code Graph Data structure 3/4
• Code: Solution 1: 3/4
• Code: Solution 2: 3/4
• Code: Solution 3: 3/4
  • Solutions work on hardcoded graph file. There is no discussion of working at scale.
• Code Documentation 2/4
• Code Testing 1/4
  • add tests around all methods
• Blog / Presentation 4/5
  • Good start, make sure you discuss all solutions and provide information on how the algorithms work.

Proposal Feedback.

Proposal 1/4 - Please resubmit for full points and to verify your project will meet the requirements.

Your proposal needs to have the problem context and how it is described as a graph as well as the three things you want to solve in this context and the algorithms you will use to do this.