One particularly nasty and cold day, in the middle of February, our users, cartographers, came to visit us, developers. And they looked worried.
We offered them hot tea and chocolate candy. By gentle nudging and careful questioning we managed to understand what was bothering them.
They wanted the roads to be good.
We were developers working on a map-creating program in a company which makes maps (read more here), and our users were cartographers – the people who draw the map. Lately they were busy creating a new layer on the map – the roads. You know, these places out there in the city where you’re allowed to drive a car? These places where you have fun in traffic jams? These places which you cross when you get out of the car, and all other cars suddenly want to run over you? Rings a bell?
Our cartographers were improving the city map by adding roads to it.
How did the company use these roads after they were created? End-users (common people who live in the city) would install a map app or go to the website, click on any place in the city, and the app showed them how to drive there. Pretty neat, immensely useful, users loved it. Great roads. We built them.
So, our cartographers were drawing single roads as lines, connecting the ends of lines together to make… Guess what? Right. It’s a road graph.
What makes the roads “bad”
Sometimes the cartographers clicked in the wrong place, missed the other road line just by a couple of pixels, and the ends of lines became disconnected. If they are disconnected, the app can’t “drive” there.
Roads have directions. If you set a direction wrong, the graph is also all wrong.
Some maneuvers and turns can be forbidden. This is a very powerful mechanism, and it must be handled very carefully. For example, on a T-section, like the one on the picture, it can be forbidden to turn left. But if you accidentally forbid both left and right turns, you’re in a dead end!
Our cartographers were upset about all these problems, because it’s not very easy to manually check for mistakes the whole road graph of a big city with 1.5 million of people.
And, of course, they didn’t have only one single city to draw roads for.
The problem immediately became ours, developers’. Because we loved our users and wanted them to have the best tools ever!
Long story short, we invented several ways to validate our roads.
Kosaraju’s algorithm for graph validation
That was our heaviest artillery!
This algorithm finds the number of strongly connected components in the graph.
A strongly connected component is a part in the graph where any point of that component is reachable from any other point in that very same component. Read: you can drive a car from any place in the city to any other place in the city. Pretty handy, huh?
Thus, a graph in a city definitely must have exactly one connected component. If there’re more, we’re in trouble. It means that we can’t drive our cars from one part of the city to another. And we were pretty sure that everyone is entitled to this luxury. Imagine you can’t get from home to work? Or worse: you can get from home to work, but then you can’t get back home! EVER!
So, we’ve implemented this algorithm, and if it found one component, it told the users everything’s fine. If it found more, it told them “Uh oh!”. We conveniently highlighted the resulting components on the map, so that users could easily see how the components look and who’s The Weakest Link.
The Kosaraju’s algorithm itself is pretty straightforward, you can read about it in the wiki article. Basically, it’s just two depth-first searches, the first one on the original graph, the second one – on a graph with opposite directions.
But there’re a couple of interesting things to say about our implementation.
Making roads into a graph
Cartographers drew their roads on a map, as vector objects. They knew nothing about graphs, or graph algorithms. But we did, and we had to convert these two-dimensional roads into a graph with edges and vertices.
One road on a map could consist of many points, but we cared only about start and end points.
If a start point or an end point is exactly the same in two vector roads, they are considered “connected”, and they are being made into two graph edges with one common vertex.
Cartographers could set the direction on a vector road. It could be one-directional or two-directional. The latter we split into two graph edges with opposite directions.
A tale of failed recursion
First we implemented the depth-first search recursively, and it worked well for some time.
Then our cartographers got a taste in graph drawing, the graphs grew bigger, and the recursion started to stackoverflow. We had to rewrite it in a loop.
The moral is: know your scale in advance!
Handling forbidden maneuvers in the Kosaraju’s algorithm
Remember, we had forbidden maneuvers on some crossroads in our graph? The standard depth-first search can’t “forbid” maneuvers. You’re always allowed to go from one graph edge to another, if they are connected via a common vertex.
It becomes even more complicated in the second part of the algorithm, when you reverse directions in the graph.
We mused on this problem a bit and decided to split each vertex with forbidden maneuvers on it in several vertices, and put additional edges between these temporary vertices.
For example, let’s say we have a small graph of three bi-directional road edges. It’s a T-section, where you can’t turn left.
If you need to go left, you can turn right, make an U-turn and then go. In this example, we don’t forbid U-turns on the ends of the left, right and bottom edges.
We would split this beauty into a monstrous thing, where one crossroad-vertex is split into six, and all of them are connected with additional edges. Red ones represent the forbidden maneuvers and have zero weight, which means that our depth-first search won’t go by them. Green ones are allowed maneuvers.
How many vertices will be there after a split? Equal to the number of one-direction roads. In our example, it’s six, because we had three two-dimensional roads, and each two-dimensional road is split into two one-dimensional roads.
Still with me? Great.
How many additional roads will go in and out of each split vertex? Equal to the number of one-direction roads which go in the original vertex.
Don’t worry, we split only vertices that had forbidden maneuvers, otherwise we’d end up with an immensely bloated graph.
This solved our problem and worked like a charm. Though we wasted quite some paper (and even more nerve cells), drawing all the possible combinations while debugging.
Other road validations
Other than the big and complex Kosaraju’s algorithm, we implemented a big set of validations, helping our users to find all mistakes.
They were able to do a simple route search from an arbitrary point to another arbitrary point. They ran it on small suspicious places. If the algorithm doesn’t drive as you would expect a car to drive, there’s something wrong with the graph in this place.
We implemented some purely spatial (and not graph-related) validations. For example, if two road ends are very close to each other, with a distance between them less than a meter, but they are not precisely connected – usually, it’s a mistake and needs to be fixed.
However, there can be a curb or a flowerbed between the two road ends, and the car couldn’t go in there. (Or, at least, shouldn’t. Flowerbeds are both a temptation for drivers and a weak point for road services…). In this case, a cartographer can mark this place as a “intended” one, and we will stop bothering them.
If there’s a one-directioned road, and it doesn’t connect with any other roads on one end or another, it’s obviously a mistake.
Also, there were various validations on the number and configuration of forbidden maneuvers in a crossroad. Some configurations were considered dangerous, like, for example, if everything is accidentally forbidden.
All these validations improved the cartographers’ life immensely, and the data quality was much better than before.
This was all about algorithms, but how did we manage to implement all these algorithms in practice? Especially at scale?
Luckily, I already have an article ready for you! Read here how we designed the whole system for the road graph validations.
Interested? Read more about our GIS-system development.
Part 1: Requirements.
Part 2: Architecture.
Part 3: Map navigation in details.