Graphs of road networks and algorithms for working with them
In mathematics, the road network (automobile and not only) is represented as a weighted graph. Localities (or intersections) are the vertices of the graph, the ribs are the roads, the weights of the ribs are the distances along these roads.
Weighted graphs offer many algorithms. For example, the popular Dijkstra algorithm for finding the shortest path from one vertex to another. All of these algorithms have a common principal (for mathematics) peculiarity - they are universal, i.e. can be successfully applied to graphs of any construction. In particular, for each algorithm its complexity is known - it roughly corresponds to an increase in the execution time of the algorithm depending on the number of vertices of the graph. All this can be read in detail, for example, in Wikipedia.
Let's return to practical tasks. Roads are represented by a weighted graph, but roads are not any graph. In other words, it is impossible to build a road network from any graph. In contrast to the virtual graph as a mathematical abstraction, the roads are built by people from real materials and cost quite a lot of money. Therefore, they are laid not as horrible, but according to certain economic and practical rules.
')
We do not know these rules, however, working with road networks, it is possible to use algorithms that are effective for graphs of roads, although they are not suitable for graphs in a universal or mathematical sense. Consider here two such algorithms.
1. We will use weighted undirected graphs with non-negative edge weights. In particular, roads within a region (country) are just such a graph.
2. The matrix of shortest distances (MKR) - its small and simple example can be found in many road atlases. This tablet is usually called something like this: “distances between the most important cities”. It looks like a part of the matrix below or above the main diagonal (from the top left to the bottom right corner), because on the other side of the main diagonal there are exactly the same numbers, in other words, the element M (i, j) = M (j, i). This happens because the graph, as the mathematicians say, is undirected. Rows and columns correspond to cities (tops of the graph). In reality, such a table is much larger, since all villages and crossroads are included at the top of the graph, but it is naturally impossible to print such a large table in the atlas.
First of all, we will continue (mentally) our table to the upper part, we will get an MKR symmetric with respect to the main diagonal and we will keep in mind such a table. In this case, a column with a certain number is equal to a line with the same number and it does not matter which of the concepts to use. We use the one and the other to cross them.
Our MCM may be: a) known in advance, because we calculated it with one of the MCM search methods; b) we may not know the MCR, but define it line by line as needed. Line by line - this means that for the required line, the distances are calculated only from the corresponding vertex to the other vertices, for example, using the Dijkstra method.
3. A couple more concepts. The eccentricity of a given vertex is the distance from this vertex to the farthest from it. The radius of the graph is the smallest eccentricity of all vertices. The center of the graph is a vertex whose eccentricity is equal to the radius.
How it looks in practice. The center of the road network is a city or intersection, the least distant from all other points of this network. The radius is the maximum distance from this central node to the most distant.
4. The degree of the vertex is the number of edges that is attached to the vertex.
In graphs of road networks, the average degree of all peaks is in the region from 2 to 4. It is quite natural - it is difficult and expensive to build intersections with a large number of adjacent roads, it is no less difficult to use such a road network. Graphs with a low average degree of vertices are called sparse, as we can see, graphs of road networks are just like that.
Note that a graph may have several centers, but we want to find any of them.
How is the problem solved in the general case? Full view of the FIBC. The maximal element in the line is searched (eccentricity of each vertex), and then the minimal element is found from these maximal elements.
This is not the fastest way. What is needed faster, if, apparently, the radius and center of the graph can be found once? For example, there are tasks and algorithms on them, where during the search the vertices are constantly “reunited” into groups, and the criterion for each group is its radius. In this case, the radius is recalculated many times, and the speed of its search becomes an important parameter. How to find the radius faster?
The secret is that for road network graphs, all elements are not required to be viewed. In practice, it is enough to look at a very small part of all the lines.
Let's see how this turns out. Consider the values ​​in one row of the matrix MKP, in other words, consider the distance from one vertex to all others. It is easy to prove that the radius of the graph can not be greater than the maximum value in this line, and can not be less than the minimum value in this line. Mathematically speaking, we found the upper and lower limits of the number, and if they match, we will find the number.
Suppose we found values ​​in only two rows A and B. In this case, the maximum value in row A is equal to the minimum value in row B (this value will be at the intersection of column A and row B). It is easy to prove that A is the center of the graph, and the value found is its radius. Problem solved.
This is great, but such a situation on the graphs of road networks is unlikely and the problem cannot be solved in this way. Let's get smarter.
Take a couple of lines B1 and B2. Of these, we form the vector M in the following way: M (i) = max [B1 (i), B2 (i)]. It is easy to prove that if for all rows i the value min (M (i)) is equal to the maximum value in column A, then, again, A is the center, and the min (M (i)) found is the radius.
If a pair of lines is not enough, you can take several lines, for example three: B1, B2 and B3, then M (i) = max [B1 (i), B2 (i), B3 (i)]. The peculiarity of road network graphs is that you will not need many lines (you will be able to keep within ten). It is easy to verify by experimenting on existing graphs of networks, downloading them from the Internet: link .
In the general case, and from the point of view of mathematics, this, of course, is not so. It is quite possible to build a theoretical graph in which you will have to use a lot of lines B (almost everything except A). It’s just impossible to build a real road network of this kind - there’s not enough money.
There remains the last task. How to quickly find these successful lines B1, B2, etc. For graphs of real road networks, this is done very simply and quickly. These will be vertices as far from each other as possible, but not necessarily the most distant (mathematically, we do not need to find the diameter of the graph). We take any vertex, we find for it the most distant one, for the new one again the most distant one and so, until a pair of peaks is the most distant for each other.
We got a pair of vertices B1 and B2. Find for a pair of vector M, as described above. The line in which we found min (M (i)) is a candidate for the center, denote it A. If in column A the value min (M (i)) is maximum, then the center and radius have already been found. If not, then the maximum value in column A corresponds to the distance to another vertex (not B1 and not B2). So, we got a new vertex B3 to the list to search for the vector M. Alternatively, we can also search for the most remote vertex for B3, and if it is not B1 and not B2, add it as B4. Thus, we increase the list of vertices of B until the center and radius are found.
More strictly, with the algorithm and the necessary proofs, this algorithm is described in , it also shows the results of its use on some columns of the US road networks, and in the link and link it is described less academically, but more clearly.
The most popular FIBC search algorithms (Floyd-Warshell, for example) are described here . All of them are universal, and one of them, Dijkstra’s binary heap algorithm, takes into account such a concept as a sparse graph. However, he also does not use the features of road networks.
We will use them both on a completely different algorithm and on existing graphs, we will get acceleration tenfold compared to the Dijkstra algorithm. We note right away that the peculiarity of this algorithm is that it is the MCR that is looking for, and all at once and precisely (ie, not approximately, not heuristically).
Consider the basic idea of ​​the algorithm. Its essence is to remove the vertices of the graph without changing the shortest distances for the remaining points. If we do this by memorizing to which points and at what distances the remote vertex was attached, we can remove all the points except one, and then collect them back into the graph, but with the distances already calculated.
Let's start with a simple, from the top with degree 1. It can be removed in any case. No shortest paths pass through it, except for the paths to the very top, and they go exactly through that peak to which the deleted vertex was attached.
Let A be a vertex with degree 2 and it is connected to the vertices B1 and B2. If route B1-A-B2 is longer or equal to edge B1-B2, no routes pass through point A, except for routes to point A itself (all the rest pass through B1-B2). Therefore, point A can be deleted. Otherwise, i.e. if B1-A-B2 is shorter than B1-B2 or there is no edge B1-B2 at all, you can remove vertex A by setting the weight of the edge B1-B2 to be the sum of the weights: | B1-A | + | A-B2 |. The route from A to other points passes either through B1 or through B2, if distances for B1 and B2 are known, distances from A are also easy to calculate.
By the same principle, it is possible to remove a vertex with any degree, replacing, as necessary, Bi-A-Bj with Bi-Bj. True, we must understand that the greater the degree of the vertex, the more possible edges must be checked. For a vertex of degree n, this number is n (n-1) / 2.
Theoretically, this way you can remove all the vertices in any graph, however, in general, we are in trouble due to the increasing number of edges. When deleting a vertex with degree n, the degree of vertices adjacent to the deleted one can: decrease by -1, not change, increase to n-2. It follows that when deleting vertices with degree 3 and higher, the degree of the remaining vertices, in general, grows, the graph becomes less sparse and, eventually, deleting the vertices will turn into a rather laborious task. The algorithm, in general, is extremely time-consuming and practically useless, but it is in the general case.
Road network graphs have a unique feature of this kind: many vertices can be removed not only without growth, but also with a decrease in the degree of adjacent vertices. Moreover, if some vertex cannot be “successfully” deleted now, it can be “successfully" deleted later, after deleting some vertices adjacent to it.
Accordingly, we simply need at each step to correctly select the vertices to be deleted, starting with those that are deleted more "successfully."
The algorithm itself can be found in more detail here . It describes how to remove the vertex, keeping the distances and paths between the remaining ones. This process is called disassembly. It describes how to restore the graph back then, adding vertices in reverse order one by one, how to recalculate the MCR. This process is called assembly.
It also shows the results of using the algorithm on the US road network graphs by reference .
If we consider road networks not as graphs in general, but as graphs with some special properties, we can create and successfully use more efficient algorithms for many practical problems.
Weighted graphs offer many algorithms. For example, the popular Dijkstra algorithm for finding the shortest path from one vertex to another. All of these algorithms have a common principal (for mathematics) peculiarity - they are universal, i.e. can be successfully applied to graphs of any construction. In particular, for each algorithm its complexity is known - it roughly corresponds to an increase in the execution time of the algorithm depending on the number of vertices of the graph. All this can be read in detail, for example, in Wikipedia.
Let's return to practical tasks. Roads are represented by a weighted graph, but roads are not any graph. In other words, it is impossible to build a road network from any graph. In contrast to the virtual graph as a mathematical abstraction, the roads are built by people from real materials and cost quite a lot of money. Therefore, they are laid not as horrible, but according to certain economic and practical rules.
')
We do not know these rules, however, working with road networks, it is possible to use algorithms that are effective for graphs of roads, although they are not suitable for graphs in a universal or mathematical sense. Consider here two such algorithms.
Some important concepts and conventions
1. We will use weighted undirected graphs with non-negative edge weights. In particular, roads within a region (country) are just such a graph.
2. The matrix of shortest distances (MKR) - its small and simple example can be found in many road atlases. This tablet is usually called something like this: “distances between the most important cities”. It looks like a part of the matrix below or above the main diagonal (from the top left to the bottom right corner), because on the other side of the main diagonal there are exactly the same numbers, in other words, the element M (i, j) = M (j, i). This happens because the graph, as the mathematicians say, is undirected. Rows and columns correspond to cities (tops of the graph). In reality, such a table is much larger, since all villages and crossroads are included at the top of the graph, but it is naturally impossible to print such a large table in the atlas.
First of all, we will continue (mentally) our table to the upper part, we will get an MKR symmetric with respect to the main diagonal and we will keep in mind such a table. In this case, a column with a certain number is equal to a line with the same number and it does not matter which of the concepts to use. We use the one and the other to cross them.
Our MCM may be: a) known in advance, because we calculated it with one of the MCM search methods; b) we may not know the MCR, but define it line by line as needed. Line by line - this means that for the required line, the distances are calculated only from the corresponding vertex to the other vertices, for example, using the Dijkstra method.
3. A couple more concepts. The eccentricity of a given vertex is the distance from this vertex to the farthest from it. The radius of the graph is the smallest eccentricity of all vertices. The center of the graph is a vertex whose eccentricity is equal to the radius.
How it looks in practice. The center of the road network is a city or intersection, the least distant from all other points of this network. The radius is the maximum distance from this central node to the most distant.
4. The degree of the vertex is the number of edges that is attached to the vertex.
In graphs of road networks, the average degree of all peaks is in the region from 2 to 4. It is quite natural - it is difficult and expensive to build intersections with a large number of adjacent roads, it is no less difficult to use such a road network. Graphs with a low average degree of vertices are called sparse, as we can see, graphs of road networks are just like that.
Task 1. Find the radius and center of the graph by the shortest distance matrix
Note that a graph may have several centers, but we want to find any of them.
How is the problem solved in the general case? Full view of the FIBC. The maximal element in the line is searched (eccentricity of each vertex), and then the minimal element is found from these maximal elements.
This is not the fastest way. What is needed faster, if, apparently, the radius and center of the graph can be found once? For example, there are tasks and algorithms on them, where during the search the vertices are constantly “reunited” into groups, and the criterion for each group is its radius. In this case, the radius is recalculated many times, and the speed of its search becomes an important parameter. How to find the radius faster?
The secret is that for road network graphs, all elements are not required to be viewed. In practice, it is enough to look at a very small part of all the lines.
Let's see how this turns out. Consider the values ​​in one row of the matrix MKP, in other words, consider the distance from one vertex to all others. It is easy to prove that the radius of the graph can not be greater than the maximum value in this line, and can not be less than the minimum value in this line. Mathematically speaking, we found the upper and lower limits of the number, and if they match, we will find the number.
Suppose we found values ​​in only two rows A and B. In this case, the maximum value in row A is equal to the minimum value in row B (this value will be at the intersection of column A and row B). It is easy to prove that A is the center of the graph, and the value found is its radius. Problem solved.
This is great, but such a situation on the graphs of road networks is unlikely and the problem cannot be solved in this way. Let's get smarter.
Take a couple of lines B1 and B2. Of these, we form the vector M in the following way: M (i) = max [B1 (i), B2 (i)]. It is easy to prove that if for all rows i the value min (M (i)) is equal to the maximum value in column A, then, again, A is the center, and the min (M (i)) found is the radius.
If a pair of lines is not enough, you can take several lines, for example three: B1, B2 and B3, then M (i) = max [B1 (i), B2 (i), B3 (i)]. The peculiarity of road network graphs is that you will not need many lines (you will be able to keep within ten). It is easy to verify by experimenting on existing graphs of networks, downloading them from the Internet: link .
In the general case, and from the point of view of mathematics, this, of course, is not so. It is quite possible to build a theoretical graph in which you will have to use a lot of lines B (almost everything except A). It’s just impossible to build a real road network of this kind - there’s not enough money.
There remains the last task. How to quickly find these successful lines B1, B2, etc. For graphs of real road networks, this is done very simply and quickly. These will be vertices as far from each other as possible, but not necessarily the most distant (mathematically, we do not need to find the diameter of the graph). We take any vertex, we find for it the most distant one, for the new one again the most distant one and so, until a pair of peaks is the most distant for each other.
We got a pair of vertices B1 and B2. Find for a pair of vector M, as described above. The line in which we found min (M (i)) is a candidate for the center, denote it A. If in column A the value min (M (i)) is maximum, then the center and radius have already been found. If not, then the maximum value in column A corresponds to the distance to another vertex (not B1 and not B2). So, we got a new vertex B3 to the list to search for the vector M. Alternatively, we can also search for the most remote vertex for B3, and if it is not B1 and not B2, add it as B4. Thus, we increase the list of vertices of B until the center and radius are found.
More strictly, with the algorithm and the necessary proofs, this algorithm is described in , it also shows the results of its use on some columns of the US road networks, and in the link and link it is described less academically, but more clearly.
Task 2. Finding the shortest distance matrix
The most popular FIBC search algorithms (Floyd-Warshell, for example) are described here . All of them are universal, and one of them, Dijkstra’s binary heap algorithm, takes into account such a concept as a sparse graph. However, he also does not use the features of road networks.
We will use them both on a completely different algorithm and on existing graphs, we will get acceleration tenfold compared to the Dijkstra algorithm. We note right away that the peculiarity of this algorithm is that it is the MCR that is looking for, and all at once and precisely (ie, not approximately, not heuristically).
Consider the basic idea of ​​the algorithm. Its essence is to remove the vertices of the graph without changing the shortest distances for the remaining points. If we do this by memorizing to which points and at what distances the remote vertex was attached, we can remove all the points except one, and then collect them back into the graph, but with the distances already calculated.
Let's start with a simple, from the top with degree 1. It can be removed in any case. No shortest paths pass through it, except for the paths to the very top, and they go exactly through that peak to which the deleted vertex was attached.
Let A be a vertex with degree 2 and it is connected to the vertices B1 and B2. If route B1-A-B2 is longer or equal to edge B1-B2, no routes pass through point A, except for routes to point A itself (all the rest pass through B1-B2). Therefore, point A can be deleted. Otherwise, i.e. if B1-A-B2 is shorter than B1-B2 or there is no edge B1-B2 at all, you can remove vertex A by setting the weight of the edge B1-B2 to be the sum of the weights: | B1-A | + | A-B2 |. The route from A to other points passes either through B1 or through B2, if distances for B1 and B2 are known, distances from A are also easy to calculate.
By the same principle, it is possible to remove a vertex with any degree, replacing, as necessary, Bi-A-Bj with Bi-Bj. True, we must understand that the greater the degree of the vertex, the more possible edges must be checked. For a vertex of degree n, this number is n (n-1) / 2.
Theoretically, this way you can remove all the vertices in any graph, however, in general, we are in trouble due to the increasing number of edges. When deleting a vertex with degree n, the degree of vertices adjacent to the deleted one can: decrease by -1, not change, increase to n-2. It follows that when deleting vertices with degree 3 and higher, the degree of the remaining vertices, in general, grows, the graph becomes less sparse and, eventually, deleting the vertices will turn into a rather laborious task. The algorithm, in general, is extremely time-consuming and practically useless, but it is in the general case.
Road network graphs have a unique feature of this kind: many vertices can be removed not only without growth, but also with a decrease in the degree of adjacent vertices. Moreover, if some vertex cannot be “successfully” deleted now, it can be “successfully" deleted later, after deleting some vertices adjacent to it.
Accordingly, we simply need at each step to correctly select the vertices to be deleted, starting with those that are deleted more "successfully."
The algorithm itself can be found in more detail here . It describes how to remove the vertex, keeping the distances and paths between the remaining ones. This process is called disassembly. It describes how to restore the graph back then, adding vertices in reverse order one by one, how to recalculate the MCR. This process is called assembly.
It also shows the results of using the algorithm on the US road network graphs by reference .
Conclusion
If we consider road networks not as graphs in general, but as graphs with some special properties, we can create and successfully use more efficient algorithms for many practical problems.
Source: https://habr.com/ru/post/180269/
All Articles