## Finding my way with F# – Part 3 of 3

In Part 1 of this series, I laid out the algorithm for finding the number of distinct paths from a given point in a city to another. In Part 2 of this series, I went through the solution for cities where cyclical routes weren’t possible. In today’s post, Part 3, I’ll extend this solution to support cities that have cyclical routes possible.

**Modifications to "Possible Routes (Round 1)"**

Oddly enough, detecting when I was in an infinite route was not the hard part. If I try to add a new point to a route, and that point is ALREADY in the route, then I have an infinite route on my hands. The hard part was two-fold.

First, how do I represent an infinite route? To represent an infinite route in the final matrix, the question (#2 from the UC Berkeley from the Fall 2010 Programming Contest, http://www.cs.berkeley.edu/~hilfingr/programming-contest/f2010-contest.pdf) required that I show this with a -1. That would mean that there were an infinite number of ways to get from point A to point B. Since all of my data structures boiled down to lists of integers, I decided stored -1 in the route would be a sufficient flag.

Second, how do I keep going after I found the infinite part of the route? An infinite route could look like this:

012121212345

Where points 1 and 2 have one-ways going between them, allowing for the cycle. However, there is another one-way going from point 2 to point 3, allowing you to get out of the loop. (It feels very much like being trapped in a traffic circle – miss your exit and you’re goin’ around again.) Once I’ve identified that the subroute 12 can repeat, how do I break out of that to get to point 3?

Both of these are addressed by the extended BuildRouteBranch method:

let rec BuildRouteBranch cityStreets startingPoint routeSoFar = let NextSteps = List.filter(fun (route:int list) -> route.Head = startingPoint) cityStreets seq { if NextSteps.IsEmpty then // We're at the end of this branch, so return it; since it was built up in reverse order // re-reverse it now. yield List.rev(startingPoint::routeSoFar) else // We still have at least one step to go down this branch, so find all of the sub-branches // and recurse to flesh them out. for nextStep in NextSteps do if List.exists(fun(currentItem:int) -> currentItem = startingPoint) routeSoFar then // If startingPoint already in the list, then we've found an infinite route if doesContainNegativeOne routeSoFar then // If this route is ALREADY flagged as infinite, then just return it yield List.rev routeSoFar else // Up to this point, this route has not been flagged as infinite; so, tack on a -1 to NOW // flag it as infinite, and then recurse as normal. I still tack on startingPoint so that // circular paths from point X to X are represented correctly as infinite in the final matrix. yield! Seq.toList(BuildRouteBranch cityStreets nextStep.Tail.Head (-1::(startingPoint::routeSoFar))) else // startingPoint isn't already in the list, so tack it on, and recurse with the next step yield! Seq.toList(BuildRouteBranch cityStreets nextStep.Tail.Head (startingPoint::routeSoFar)) }

Previously, the meat of the "for nextStep in NextSteps do" loop was to simply call BuildRouteBranch recursively. To support cycles, I have to now check if the item I’m about to add to the route – startingPoint – already exists in the route.

If it does already exist, then we have an infinite route on our hands. I then check to see if I’ve already flagged this route as infinite (by checking to see if there is already a -1 in the route). If I haven’t, then I call BuildRouteBranch recursively, and add not only startingPoint to the route, but a -1 as well. So, in our previous example, the partial route would look like this at this point:

012-1

When I call BuildRouteBranch, I pass it nextStep.Tail.Head as the new startingPoint, just as before. That’s because I want to make sure there aren’t other ways out of point 2 than just going back to point 1.

Now, to get back to the case where I find I’m in an infinite route, and this route is ALREADY flagged as being infinite, I just return the current route. Basically, I treat this as a dead-end, and I don’t go further with it.

These modifications allow me to detect and flag the route as being infinite, and then keep going to find any subsequent, non-infinite pieces of the route.

**Modifications to "Possible Routes (Round 2)"**

Expanding the initial set of routes to find all possible subroutes turned out to be very easy. I want to preserve the -1s in the routes, because I’m going to use these as markers later when I count up the possible paths. What I want to avoid is a "possible subroute" that consists of a -1 and some other number. The -1s are purely flags – they aren’t real data points.

So, I added a new check to FindRoutesInBranchWithThisHead, specifically the check for where the incoming route has exactly 2 points.

let rec FindRoutesInBranchWithThisHead (currentRoute:int list) routesWithHead = if currentRoute.Length < 2 then [] elif currentRoute.Length = 2 then if doesContainNegativeOne currentRoute then [] else currentRoute::routesWithHead else let newSubRoute = currentRoute |> Seq.take (currentRoute.Length-1) |> Seq.toList FindRoutesInBranchWithThisHead newSubRoute (currentRoute::routesWithHead)

If one of those two points is a -1, I just return an empty list; otherwise, I tack that 2-member route onto the routesWithHead accumulator, just as before.

**Modifications to "Distinct Routes"
**Since I want to pass the -1s through to the counting step, I can treat them as valid points here, and let the de-duping process work just as before. As a result, there are not modifications to this step.

**Modifications to "Route Matrix"
**It is in this step that I use the -1s as the flags that they are.

let rec CountTheRoutes (cityRoutes:int list seq) routeCounts: int[,] = match Seq.toList(cityRoutes) with | [] -> routeCounts | topRoute::remainingRoutes -> let routeStart = topRoute |> List.head; if doesContainNegativeOne topRoute then // If we found an infinite version of this route, flag it in the matrix as such // If the proposed route end is the negative -1, back up one more to get the real end of the route let routeEnd = if (topRoute |> List.rev |> List.head < 0) then (topRoute |> List.rev |> List.tail |> List.head) else (topRoute |> List.rev |> List.head) routeCounts.[routeStart,routeEnd] <- -1 else let routeEnd = topRoute |> List.rev |> List.head; // Make sure this pair wasn't already flagged as infinite if routeCounts.[routeStart,routeEnd] >= 0 then routeCounts.[routeStart,routeEnd] <- routeCounts.[routeStart,routeEnd] + 1 CountTheRoutes remainingRoutes routeCounts

Where can the -1s be in a given route? As it turns out, through the process above, a route cannot start with a -1. Therefore, I can compute the routeStart variable just as before. A route can contain a -1 or it can terminate with a -1. The latter fact means that the calculation for routeEnd needs to be modified since -1 is not a valid index.

First, I check to see if the current route contains a -1 at all. If it does, then the corresponding cell in the matrix will be set to -1 – regardless of the value that is currently there. I have routeStart, so now I need to calculate routeEnd. To do this, I need to take into the possibility that there is a -1 at the end of the route. If we have a route like this:

123-1

Then we can’t use the -1 as the index. What we really want is is the 3, since that is the true end of this route. To calculate routeEnd, then, I use a ternary operator. If the last point in the route is negative, grab the second-to-last point; else use the last point. (The case where the -1 appears somewhere in the middle of the route will fall into the latter case.)

If I didn’t have a -1 in the route at all, then I can calculate routeEnd just as we did before – reverse the list and take the head.

Before we update the matrix, however, I need to check to see if there is a -1 there already. If there is, then this particular route has already been marked as infinite, so I move on to the next route. If it’s 0 or something positive, then I can increment like I did before.

**Final Thoughts**

Looking back, I don’t think this is a horrible solution. It certainly works, but I feel like there should be a simpler way to solve this. It seems like there should be a way to merge BuildRouteTree and BuildRouteBranch into a single routine, and that I should be able to merge GrowRouteTree and FindRoutesInBranchWithThisHead into a single method. Doing that may also mean that a lot of the duplication of routes would disappear, eliminating the need for the third step of the algorithm.

All of my data sets were tiny, so performance bottlenecks weren’t evident. I have to believe that they’re there given the amount of looping and recursion I’m doing – just not evident.

Full source code for the general solution (cyclical and non-cyclical cities) can be found in the OneWays.zip archive at http://TinyURL.com/MarkGilbertSource. This solution was developed with Visual Studio 2008, with F# installed (the latter can be downloaded for free here: http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/release.aspx).

And finally, don’t ever visit to City C – you’ll be driving around in circles for hours. For that matter, don’t go to Cities A or B, either – there are whole sections of each that you either can’t get to, or can’t get out of.

## 1 Comment

Sorry, the comment form is closed at this time.

Thanks.

PLH OOE Art

Comment by Art Scott (@Semasiographic) | January 5, 2012