How I created JamJam

I am a person who lives in Kathmandu, Nepal, I don't have my personal vehicle so getting from one place to another is a big hassle. Public buses are the only option for me. But they also have a problem, there is no public information about bus route or bus fare in Nepal. You need to memorize every bus route in Kathmandu. Getting fed up from this problem one day I decided to create a website that would solve this problem for me.

Coming up with a solution for this problem was hard as I had never dealt with such projects before. I had payed attention to my Data Structures & Algorithms classes so I knew about graphs and shortest path algorithms. But how do you just go from bus routes to a graph structure. Lots of planning and thinking was required. Unlike other countries, there is no public transportation route information in my country so at first I collected about 3/4 bus routes on my own just to start.

I manually gave each route a ID and created my own version of CSV.

1|swoyambhu,0|sitapaila,900|bafal,550|syuchatar,450|kalanki,800|solteemode,1200|kalimati,600|teku hospital,750|tripureswor-1,500|rnac bus stop,1300|jamal,800

That "1" is the route ID, each bus point is separated by a pipe symbol (|), the name represents the name of the location and the number on its right represents the distance in meters between that location and the location before it. The first location has 0 as it is the first location in the route.

I also stored each location name and its coordinates in a array in a different file so I could display on where to pick the bus in a map, instead of having to google "where this location is located". The other file looked like this

let coords = [ "bafal,27.702954,85.282020", "syuchatar,27.699607,85.281567", "kalanki,27.693446,85.281979", "solteemode,27.696659,85.293725", "kalimati,27.698388,85.299315"...

Using a hash table would have been better but for just some routes it would be an overkill to use hash table. giving each route a ID and distance between location is a really bad I know there must be a better way than this, but this was the quick and dirty solution I could think of at that time. I also didn't use database because storing data in file was enough for this project.

After I had 3/4 bus routes like this, I wrote a function that would create a adjacency list graph from the routes. I intially tried a adjacency matrix first, but working with it was too confusing and it would have wasted a lot of space as the number of routes would increase. The adjacency list was implemented in a HashMap. The keys would be all of the node locations and its value would be next location that could be reached from there. The type for the graph looked like this

let G = new Map<string, Edge[]>(); export interface Edge { end_location: string; distance: number; routeIDs: Set<number> }

routeIDs contains the set of route ID that the location resided in. After creating a graph, now I needed to run a shortest path algorithm in the graph. But there was a big problem, shortest path algorithms don't account for specific routes. They just give you the shortest path not the shortest route path. So I had to come up with a solution to this. I chose Dijkstra's algorithm as it seemed simpler than other algorithms. I modified dijkstra's algorithm so that if a route change was detected in the graph, some weight would be added to the path.

        /* If route change is detected, add additional cost */
        /* Imagine x -> u -> v, 
          then we only need to compare routeIDs of xu and uv 
        */
        if (u != src) {
          const x = prev.get(u);
          if (x == undefined) {
            return false;
          }
          const xu_routeIDs = get_routeIDs(G, x, u);
          const uv_routeIDs = get_routeIDs(G, u, v.end_location);
          /* If there is no intersection the two sets of route IDs between xu and uv
           * then it means there is a route change
           */
          if (intersection(xu_routeIDs, uv_routeIDs).size == 0) {
            alt += change_weight;
            route_changed = true;
          }
      

this is the code that would detect route change and add weight. If there was a route with nodes x -> u -> v then we just need to get the routeIDs set of edge xu and uv then check for any intersection in the two sets. If there is no intersection then route change is detected. I also used a min heap to speed up the dijkstra algorithm.

After finding the shortest route, the code would create a array containing the location names and its route IDs. It would look something like this

[['A', [1,2]], ['B', [2,3]], ['T', [5,8]]]

Now I had all the routes I needed to flatten the routeIDs with the most common routeIDs so that the number of times bus needed to be changed would be minimized. While solving the problem, I came to know to that it is a NP hard problem. After taking the help from Stackoverflow, I flattened the list like below.

[['A', 2], ['B', 2], ['T', 5]]

Then I wrote a simple prompt text builder that would return something like

          Take bus from point A to B 
          Get off from bus 
          Take bus till T 

You can find the full code here. I apologize if the article was hard to understand it is my first time writing a blog.