Linux
Raiting:
17

Quick search library on the graph


Hello friends!
I wrote a library for finding paths on arbitrary graphs, and I would like to share it with you .
An example of use on a huge graph:

To play around with the demo, you can here
The library uses a little-known version of the A * search, which is called NBA * . This is a bidirectional search, with relaxed requirements for the heuristic function, and a very aggressive termination criterion. Despite its little-known algorithm, the algorithm has an excellent speed of convergence to the optimal solution.
The description of the various variants of A * has already been found on the hub several times. I really liked this is , so I will not repeat this article. Under the cut I will explain in more detail why the library works quickly and how the demo was done.
Why does the library work fast?
<blockquote> "Somehow I do not believe that so quickly.
The reaction of the friend who first saw the library. <Tgsrbq> Immediately I must admit, I do not believe that my implementation is the fastest possible. It works quite quickly considering the environment in which it is located (browser, javascript). Its speed will strongly depend on the size of the graph. And, of course, what is now in the repositories can be speeded up and improved.
Statistics
To measure performance, I took a road graph from New York (730,000 ribs, 260,000 knots). The table below shows the statistics of the time required to solve one task of finding a path from 250 randomly selected:
Average Median Min Max p90 p99
A * lazy (local) 32ms 24ms 0ms 179ms 73ms 136ms
NBA* 44ms 34ms 0ms 222ms 107ms 172ms
A *, unidirectional 55ms 38ms 0ms 356ms 123ms 287ms
Dijkstra 264ms 258ms 0ms 782ms 483ms 631ms
Each algorithm solved the same problem.A * lazy fastest, but its solution is not always optimal. In essence, it is bidirectionalA * which immediately goes out as soon as both searches have met.NBA * bidirectional, converges to the optimal solution. In 99% it took less than 172 milliseconds to find the shortest path (p99).
Optimizations
The library works relatively quickly for several reasons.
First, I changed the data structure in the priority queue in such a way that the priority update of any element of the queue takes O (lg n) time. This is achieved by the fact that each element monitors its position in the heap during rebuilding the queue.
Secondly, during the stress tests, I noticed that garbage collection takes considerable time. This is not surprising, since the algorithm creates many small objects when it walks the graph. A problem is solved with the garbage collector using the object pool . This is a data structure that allows you to reuse objects when they are no longer needed.
Finally, the NBA * search algorithm has a very nice and tough criterion for visiting sites.
To admit, I think that this is not the limit of perfection. It is likely, if you use a hierarchical approach, described by Boris will be able to speed up the time for even larger graphs.
How does the demo work?
Creating a library is, of course, very interesting. But I think the demo project deserves a separate description. I learned a few lessons, and I would like to share with you, in the hope that it will be useful.
Before we start. Someone asked me: "But this is a graph, how can I present the card as a graph?". It is easiest to present each intersection with a node of the graph. Each intersection has a position (x, y). Each straight section of the road will be made by the edge of the graph. The bends of the road can be modeled as a special case of intersections.
Preparing the data
Of course, I heard about https://www.openstreetmap.org , but their appearance did not attract me much. When I discovered APIs and tools like http://overpass-turbo.eu/ - this is how the new world opened before my eyes :). Data they give under the ODbL license, which requires that they be mentioned (the more people know about the service - the better the service becomes).
The API allows you to make very complex queries, and gives tremendous amounts of information.
For example, such a request will give all the bicycles in Moscow:
[out:json];
// Save the scope to the variable `a`
(area ["name" = "Moscow"]) ->. a;
// Download all roads inside a with the attribute `highway == cycleway`
way["highway"="cycleway"](area.a);

// and merge the roads with the nodes of the graph (nodes contain a geo- position)
node(w);

// Finally, return the results
out meta;
The API is very well described here: http://wiki.openstreetmap.org/wiki/Overpass_API
I wrote three small scripts to automate the receipt of roads for cities, and save them to my format graph.
Save the graph
Data OSM gives in the form of XML or JSON. Unfortunately, both formats are too large - the map of Moscow with all roads takes about47MB. My task was to make the site load as quickly as possible (even on a mobile connection).
You could try to squeeze gzip'om - a map of Moscow from 47MB turns into 7.1MB. But with this approach, I would not have control over the speed of unpacking the data - they would have to be javascripted on the client, which would also affect the initialization speed.
I decided to write my own format for the graph. The graph is divided into two binary files. One with the coordinates of all vertices, and the second with the description of all the edges.
A file with coordinates is just a sequence of x, y pairs (int32, 4 bytes per coordinate). The offset along which the pair of coordinates are located is considered as the nodeId verifier nodeId).
image
The edges of the graph are transformed into the usual sequence of parfromNodeId, toNodeId.
image
The sequence in the picture means that the first node refers to the second, and the second refers to the third, and so on.
The total size for a graph with V nodes and E edges can be calculated as:
storage_size = V * 4 * 2 + # 4 bytes per pair of coordinates per node
                E * 4 * 2 = # 4 bytes per pair of vertex identifiers
                (V + E) * 8 # in total, in bytes
This is not the most efficient compression method, but it is very easy to implement and you can quickly restore the initial graph to the client. Typed arrays in javascript'e work faster than parsing JSON'a.
At first I wanted to add also the weight of the edges, but stopped myself, because downloading on a weak mobile connection even for small graphs will become even slower.
First of all, mobile phones
When I was writing a demo, I thought I'd write about it on Twitter. Twitter most people read with mobile phones, and therefore the demo should be primarily designed for mobile phones. If it does not load quickly, or it does not support touch-write, it's gone.
A couple of days after the announcement, you can recognize the logic above justified. Tweeting with the demo demo became the most popular tweet in the life of my Twitter.
I tested the demo primarily on the platforms of the iPhone and Android. For tests on Android, I found the cheapest phone and used it. This greatly helped with debugging performance and ease of use on a small screen.
Asynchrony
The slowest part in the demo was the initial download of the site. The code that initialized the graph looked something like this:
for (let i = 0; i < points.length; i += 2) {
let nodeId = Math.floor(i / 2);

let x = points[i + 0];
let y = points[i + 1];

    // graph is https://github.com/anvaka/ngraph.graph
graph.addNode(nodeId, { x, y })
}
At first glance - nothing wrong. But if you run it on a weak processor and on a large graph - the page becomes dead while the main thread is busy iterating.
Exit? I know some people use Web Workers. This is a great solution, considering that everything is now multi-core. But in my case, using the web workers would greatly extend the time it takes to create a demo. It would be necessary to think about how to transfer data between threads, how to synchronize, how to save battery life, how to be when web workers are not available, etc.
Since I did not want to spend more time, I needed a more lazy solution. I decided to just break the loop. Just run it for a while, see how much time has passed, and then callsetTimeout () to continue at the next iteration of the event loop. All this is done in the rafor library.
With this solution, the browser has the opportunity to constantly inform the user about what is happening inside:
image
Rendering
Now that we have the graph loaded, we need to show it on the screen. Of course, using SVG to draw a million elements is not good - the speed will start to sag after the first ten thousand. You could cut the graph into tiles, and use Leaflet or OpenSeadragon to draw a big picture.
I also wanted to have more control on the code (and learn WebGL), so I wrote my WebGL renderer from scratch. There I use the "scene graph" approach. In this approach, we build a scene from a hierarchy of elements that can be drawn. During the drawing of the frame, we go through the graph, and let each node accumulate transformations or bring itself to the screen. If you are familiar with three.js or even the usual DOM, the approach will not be a novelty.
The renderer is available here , but I intentionally did not document it strongly. This is a project for my own learning, and I do not want to give the impression that they can be used :)
Battery
image
Initially, I repainted the scene on every frame. Very quickly, I realized that it was heating the phone very hard and the battery was going off at a remarkable speed.
To write code under such conditions was just as inconvenient. To work on the project, I usually sat in a coffee house in my spare time, where there were not always outlets. So I needed to either learn to think faster, or find a way to not plant a laptop so quickly.
I still have not found a way to think faster, because I chose the second option. The solution was naive simple:
<blockquote> Do not draw a scene on every frame. Draw only when asked, or when you know that it has changed. <Tgsrbq> Maybe it will seem too obvious now, but it was not so at first. After all, basically all the examples of using WebGL describe a simple loop:
function frame() {
    requestAnimationFrame (frame); // Plan the next frame

    renderScene (); // draw the current frame.
    // Nothing wrong with that, but we can put the battery so quickly
}
With a "conservative" approach, I needed to render thequestAnimationFrame () out of the function frame ():
let frameToken = 0;

function renderFrame() {
if (!frameToken) frameToken = requestAnimationFrame(frame);
}

function frame() {
frameToken = 0;
renderScene();
}
This approach allows anyone to request the next frame. For example, when a user dragged a map and changed the transformation matrix, we call renderFrame () .
The variable frameToken helps avoid calling thequestAnimationFrame again between frames.
Yes, the code gets a little harder to write, but the battery life was more important to me.
Text and lines
WebGL is not the easiest API in the world. It is especially difficult to work with text and thick lines (for which the width is more than one pixel).
image
Given that I'm quite new to this business, I quickly realized that it would take me a long time to add support for text / lines.
On the other hand, from the text I had to draw only a couple of labels A and B. And from the thick lines - only the path that connects the two peaks. The task is quite possible for DOM'a.
As you remember, our renderer uses the scene graph. Why not add one more element to the scene, whose task will be to apply the current transformation to ... SVG element? This SVG element will be made transparent, and put it on top of the canvas. To remove all events from the mouse - set itpointer-events: none ;.
image
turned out very quickly and angrily.
Moving around the map
I wanted to make navigation look like typical behavior of a map (as in Google Maps, for example).
I already wrote a navigation library for SVG: anvaka / panzoom . It supported touch and kinetic attenuation (when the card continues to move by inertia). In order to support WebGL, I had to slightly tweak the library.
panzoom listens to events from the user mousedown, touchstart, etc.), applies smooth transformations to the transformation matrix, and then, instead of directly working with SVG, it gives the matrix to the "controller ". The task of the controller is to apply the transformation. The controller can be for SVG, for DOM or even my own controller , which applies a transformation to the WebGL scene.
How to understand what is clicked?
We discussed how to load a graph, how to draw it, and how to move it. But how to understand what was pressed when the user touches the graph? Where to pave the way and where?
When the user clicked on the map, we could most easily bypass all points in the graph, look at their positions and find the nearest one. In fact, this is a great way for a couple of thousand points. If the number of points exceeds tens / hundreds of thousands, the productivity will not be acceptable.
I used quad tree to index the points. After the tree is created - the speed of finding the nearest neighbor becomes logarithmic.
By the way, if the term "quad tree" sounds awesome - do not be upset! In fact, quad-trees are very, very similar to ordinary binary trees. They are easy to learn, easy to implement and easy to apply.
In particular, I used my own implementation, yaqt library, because it is unpretentious from memory for my data format. There are better alternatives, with good documentation and community (for example, d3-quadtree ).
Looking for the path
Now all the parts are in their places. We have a graph, we know how to draw it, we know what was pressed on it. It remains only to find the shortest path:
// pathfinder is the object https://github.com/anvaka/ngraph.path
let path = pathFinder.find(fromId, toId);
Now we have an array of vertices that lie on the found path.
Conclusion
I hope you enjoyed this little trip to the world of graphs and shortcuts. Please let me know if the library came in handy, or if there are tips on how to make it better.
I sincerely wish you well!
Andrei.
KlauS 21 october 2017, 10:55
Vote for this post
Bring it to the Main Page
 

Comments

Leave a Reply

B
I
U
S
Help
Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute