Graph theory - Notes

algorithms.md

Best graphs and its appliance

• Prim, Kruskals - Network Spanning Tree Protocol.
• Dijkstra - Maps and routing eg. Maps Google. (A * is an improved version of this algorithm).
• DAG - For easy implement tree hierarchy.
• Bellman-Ford - RIP Networks and negative paths.

Prim (Minimium spanning tree)

Algorithm

1. Create a set mstSet that keeps track of vertices already included in MST.

2. Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.

3. While mstSet doesn’t include all vertices

   • Pick a vertex u which is not there in mstSet and has minimum key value.
   • Include u to mstSet.
   • Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v

Dijkstra

Algorithm

1. Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.

2. Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.

3. While sptSet doesn’t include all vertices

   • Pick a vertex u which is not there in sptSetand has minimum distance value.
   • Include u to sptSet.
   • Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

A *

The best option and optimized version for finding routes but not always finds the shortest path.

Algorithm

1. Initialize the open list

2. Initialize the closed list put the starting node on the open list (you can leave its f at zero)

3. while the open list is not empty a) find the node with the least f on the open list, call it "q"

   b) pop q off the open list

   c) generate q's 8 successors and set their parents to q

   d) for each successor i) if successor is the goal, stop search successor.g = q.g + distance between successor and q successor.h = distance from goal to successor (This can be done using many ways, we will discuss three heuristics- Manhattan, Diagonal and Euclidean Heuristics)

     successor.f = successor.g + successor.h
   
   ii) if a node with the same position as 
       successor is in the OPEN list which has a 
      lower f than successor, skip this successor
   
   iii) if a node with the same position as 
       successor  is in the CLOSED list which has
       a lower f than successor, skip this successor
       otherwise, add  the node to the open list
   

   end (for loop)

   e) push q on the closed list end (while loop)

Helpers

• Build routes using specific points https://developers.google.com/maps/documentation/directions/intro?hl=es-419#Waypoints
• Calculate distance and time https://developers.google.com/maps/documentation/distance-matrix/intro?hl=es-419
• Calculates traffic for a given route https://developers.google.com/maps/documentation/directions/intro?hl=es-419#traffic-model

References

https://stackoverflow.com/questions/2733051/bellman-ford-dijkstras-prims-algorithm-kruskals-directed-acyclic-graph https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/ https://www.geeksforgeeks.org/?p=27455 https://www.geeksforgeeks.org/a-search-algorithm/

proposals.md

Graph Solutions

Here are our two proposals for the project

---

Proposal 1

---

Login y registro

En el registro se pide dato unico y con eso se asigna el rol? ID? email empresa? celular? Dependiendo del rol se redirecciona a cada pantalla y solo se tiene acceso a esa funcionalidad.

Roles

Employee

• ‎Ver ruta actual y paradas
• modify info:
  • employee preferred location or pick up: Mientras escoje puede ver los puntos seleccionados por los demas para sumarle puntos, haciendo paradas preferidas

Driver

• Al conductor se le permitira ver la ruta.
  • Rediccionar a google maps?
• Puede cambiar las paradas?

Admin

• Puede cambiar los puntos
• Ver usuarios

System

• Cron o algo una vez al mes o x tiempo:
  • takes all stored locations maybe appends some points over important stops or stations into single list
  • calculate knn with latitude and longitude from points to see which clusters are made with different k points
  • take the centers of each cluster as the most concentration of employees points
  • sort points in a line or multiple routes in the direction of the campus
  • use Google maps api to produce a route between those points or ?dijkstra? over the addresses?
  • store points for use in displaying route in an embedded maps in the show map feature

---

Proposal 2

---

• Ask for the user's location data
• Get the distances and location data using the Google API
• Build the graph using the python's library Networkx with this data
• Apply the A* algorithms the find the best paths
• Expose this service using the Flask framework with microservices with a Restful API
• Consume this data using the Oracle JET client