Sample Mobile Web App Presented at #mobidevday

Yesterday I attended my first MobiDevDay conference and presented a talk titled “Functional Programming for the Rich Mobile Web with F#.

The scenario for the demo’ed sample app is that a central website receives orders for flowers from all across the US. Local florists can look at the orders in their area and choose to fill the ones they can – with the help of the sample app. The app has only two screens as shown below:

Screen1 Screen2

Running sample: http://mdd.apphb.com (needs HTML5 browser and location access). Allow upto 20 seconds for the first page to load. The sample is running is on the free version of AppHarbor which probably provisions some parts on demand. The total data downloaded (including all scripts) is only 250K for the first page.

qrcode.13472867

The first screen shows a list of unfilled orders near the florist’s location. The florist selects from the available list, the orders he/she can fill and then generates a delivery route.

Although the app is small it is representative of a production app in terms of functionality as shown by the architecture diagram below:

Slide6

A real production app would add security and perhaps better error handling.

The mobile web app was built with F#, WebSharper (which I believe is the best method for building such apps), JQuery mobile, and Bing Maps API. It also leverages the SQL type provider for database access.

Source Code: https://mobidevday2013.codeplex.com/

I discovered what I think can be a pattern for building JQuery mobile applications. Load all JQuery mobile views (pages) as statically generated HTML and then wire all the pages with WebSharper generated javascript. The initial pages can be just empty shells which are progressively filled in as needed by the javascript. I found that JQuery mobile page-to-page navigation works much better this way.

One problem that had to be tackled was optimizing the delivery route. The list of orders are geocoded based on the delivery zip code and then a route is generated with each delivery location as a waypoint in the route.You don’t want a route which crisscrosses the entire metro area! This can happen if the route points are arbitrarily ordered.

Optimizing a route is close to the the famous Travelling Salesman Problem which is NP-hard. Consider a single path from a starting point and going through 10 delivery locations (which are all connected in the underlying graph representation):

Slide21

Let’s say you have a distance (cost) between any two pairs of points on the graph. A naïve approach would be to generate all possible paths and add the total distance travelled and then choose the path with the minimum distance. However the number of paths grows exponentially with the number of route points. There 3+ million possible paths with just 10 route points (10!).

To tackle this issue, I worked out a heuristic, greedy algorithm which works by picking the nearest point from the starting point and then the next nearest and the next nearest and so on until all points are covered (note this is not globally optimum but still gives reasonable results in practice).

The algorithm first finds the distance between all pairs of points (given as lat, long) and then constructs and adjacency list representation of the graph. And finally runs the shortestPath heuristic algorithm to find the path. The algorithm was developed using the F# REPL (FSI interactive) and is very idiomatic F# code. The surprising part was that the algorithm – which includes a recursive function – ran, as-in in WebSharper just fine. I just tagged the code as JavaScript and that was it.

open System

let calcDist (lat1, lon1) (lat2, lon2) =
    let r = 3958.75                  // earth radius in miles
    let radPerDegree = 0.017453293   // radians per degree PI/180

    let phi_1 = (90.0 - lat1) * radPerDegree
    let phi_2 = (90.0 - lat2) * radPerDegree

    let th_1  = lon1 * radPerDegree
    let th_2  = lon2 * radPerDegree

    let d = r * Math.Acos(
                    Math.Sin(phi_1) * Math.Sin(phi_2) * Math.Cos(th_1 - th_2)
                    + Math.Cos(phi_1)*Math.Cos(phi_2)
                )
    d

let shortestPath (points:(string*(float*float))[]) =
    let allPairsDist =
        [for i in 0..points.Length-1 do
            for j in i+1..points.Length-1 do
                let z1,p1 = points.[i]
                let z2,p2 = points.[j]
                let dist = calcDist p1 p2
                yield z1, (z2, dist)
                yield z2, (z1, dist)]

    let latLong = points |> Map.ofArray

    let graph =
        allPairsDist
        |> Seq.groupBy (fun (a,b) -> a)
        |> Seq.map (fun (a,xs) -> a,xs |> Seq.map snd |> Seq.toArray |> Array.sortBy snd)
        |> Map.ofSeq

    let shortestPath =
        let startList = [fst points.[0]]
        let visitedSet = Set startList

        let rec sp ((zfrom::_) as path) sDone =
            let edges = graph.[zfrom]
            edges
            |> Array.tryPick (fun (z,d) -> if sDone |> Set.contains z then None else Some z)
            |> function
            | Some z -> sp (z::path) (sDone |> Set.add z)
            | None -> path |> List.rev
        sp startList visitedSet

    shortestPath |> List.map (fun z -> z,latLong.[z])

//testing
let points =
    [|
        "48331",(42.50513,-83.40723)
        "48036",(42.59383,-82.91332)
        "48030",(42.49648,-83.09847)
        "48239",(42.39228,-83.28202)
        "48127",(42.33438,-83.27392)
        "48197",(42.20213,-83.62049)
        "48104",(42.2709,-83.72782)
        "48009",(42.53483,-83.22416)
        "48393",(42.52053,-83.54914)
        "48307",(42.65928,-83.12248)
        "48238",(42.23993,-83.15082)
    |]

shortestPath points
Advertisements

One thought on “Sample Mobile Web App Presented at #mobidevday

  1. Pingback: F# Weekly #19, 2013 | Sergey Tihon's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s