Routing tables

Reading time10 min

In brief

Article summary

In this article, you will learn how to store the result of a traversal in a data structure called a routing table. Then, you will learn how to use that structure to retrieve the path found by the traversal up to a given vertex. After the video, we will link routing tables with some data structures you have seen before.

Main takeaways

Routing tables are a way to store the result of a graph traversal in memory.
They can then be used to analyze the traversal performed, for instance to find a path.
They can be implemented using a list or a dictionary.

Article contents

1 — Video

Please check the video below. You can also read the transcripts if you prefer.

Information

Click here to show the transcripts of the video.

Hi everyone! In today’s lesson, we will see how to build routing tables to navigate a graph, using the spanning trees obtained from graph traversal algorithms, such as the BFS or the DFS.

These routing tables will help the artificial intelligence that you will develop in this course to move between two positions in the maze.

From spanning trees to routing

In the previous lesson you have learnt how to build spanning trees. Once we have such a spanning tree, we need a routing algorithm to be able to navigate between any two vertices in the graph.

Routing from a starting point to a destination is interpreted backwards. We already know what the starting point is, so we need to begin with the destination to find a path. So, a routing algorithm provides a path from the destination to the starting point.

Tracing a path backwards is more intuitive than it might seem. Imagine that you, the blue circle on the map, have to drive to a friend's house, which is the orange circle on the map.

You could start by deciding if you should turn left or right at the next intersection.

Then, at each intersection that you encounter, identify which road can be taken next, until finally you reach your friend's house.

Or, you might think of the best route backwards, by first identifying what street your friend's house is on. Then, which other road accessed this street, etc.

Until knowing if you should turn left or right at the next intersection.

This second way of thinking is how the routing algorithm will work.

To better understand this, let's look at an example we've already seen in the previous lesson that you had with Vincent. Let's consider the path between $v_1$ and $v_7$.

We can see the spanning tree obtained using a DFS on the left, and the spanning tree obtained using a BFS on the right.

Routing from $v_1$ to any other vertex can be easy when we use trees. But to do this, we first need a few more definitions.

A rooted tree is a tree in which we designate a particular vertex as the root, which is also sometimes known as the origin. In this case, we will consider $v_1$ as the root, because it's our starting position. Therefore, the edges of this rooted tree have a natural orientation away from the root.

In a rooted tree, the parent of a vertex is the vertex connected to it on the path from the root. For example, the parent of $v_2$ is $v_3$ in the tree on the left. Every vertex except the root has a single parent. A child of a vertex $v$ is a vertex of which $v$ is the parent. So, $v_2$ is the child of $v_3$ in the tree on the left.

If we apply these concepts on the whole trees, we obtain the following rooted trees, where the orientation of the edges indicates the parents of the vertices. For example, in both graphs, $v_1$ has no parent, the parent of $v_4$ is $v_1$, and the children of $v_6$ are $v_7$ and $v_5$.

Routing tables

We can now build routing tables by considering the parent of each vertex in the path from $v_1$. Routing tables are useful data structures that can be used to reconstruct a path. As we mentioned earlier, routing is considered backwards, from the destination back to the starting position.

A routing table has just one row, and as many columns as there are vertices in the graph. Each column corresponds to one vertex, and the associated value in the table is its parent in the spanning tree rooted in $v_1$.

Let us now see how this table is built step by step using a spanning tree.

Let's start with one obtained from a DFS. We start from an empty table. Vertex $v_1$ is the root, so it doesn't have a parent. We simply note a dot in the $v_1$ column.

Vertex $v_1$ only has one child vertex, $v_4$. So we add $v_1$ in the column corresponding to $v_4$.

Vertex $v_4$ only has one child, $v_3$. So we add $v_4$ in the column of $v_3$.

Now let's simply apply the same principle to vertices $v_2$ and $v_6$, which are the only children of $v_3$ and $v_2$, respectively.

Finally, $v_6$ has two children, $v_7$ and $v_5$. So, let's add $v_6$ in the columns corresponding to $v_5$ and $v_7$. So that's it, the routing table is complete.

To read this table, you can simply start from the desired destination and read the corresponding entry, which refers to the parent vertex of the destination.

For example, if we are looking for the path from $v_1$ to $v_7$, we first read the entry corresponding to $v_7$, which is $v_6$. By definition, the parent of the destination in turn corresponds to the previous vertex in the path from $v_1$ to the destination vertex.

By reading the entries corresponding to each predecessor, you'll eventually reach the starting position $v_1$. So in our example, the next step is to identify the entry corresponding to $v_6$, which is $v_2$. By continuing like this, we obtain the path $(v_7, v_6, v_2, v_3, v_4, v_1)$.

As a second example, let’s also build the routing table from the spanning tree obtained from a BFS.

Here's the spanning tree. Again, we start from an empty table.

Vertex $v_1$ has two children vertices, $v_4$ and $v_2$. So we add $v_1$ in the corresponding columns.

The only child of $v_4$ is $v_3$, and the only child of $v_2$ is $v_6$.

Then, $v_6$ has two children, $v_7$ and $v_5$. The routing table is complete.

If we read the path from $v_1$ to $v_7$ in the table, we obtain $(v_7, v_6, v_2, v_1)$.

We can see that this path is shorter than the one obtained using a DFS, which was $(v_7, v_6, v_2, v_3, v_4, v_1)$. This is an important difference between DFS and BFS. BFS is a more cautious approach than DFS, as BFS gradually increases the distance from the starting position.

Using BFS, we can be absolutely certain that we're going to find the shortest path between two vertices.

Concluding words

That’s it for today. Thank you for your attention! I’ve really enjoyed talking about routing with you.

You should remember that it is not sufficient to build the spanning tree to navigate between vertices in the graph, but that you also need a routing algorithm.

See you soon for more algorithmic adventures!

2 — Implementing routing tables

To implement routing tables in a programming language, you need a data structure that can help you map vertices to their parents along the traversal. In the article on how to represent graphs in memory, you have learned about a few of such structures. With a bit of imagination, all these structures can be used to implement routing tables. Let’s hint how we can do that:

Arrays or lists – Let’s arbitrarily number the vertices in the graph from 1 to $n$. We use an array of size $n$, or a list that we initialize with $n$ entries equal to 0 (or any value outside interval $[1, n]$). Then, when we want to indicate that the vertex at index $i$ is a predecessor of the vertex at index $j$, we just need to put $i$ in the $j^{th}$ entry of the structure. Later, when retrieving the path, it will be necessary to convert indices into actual vertices to get the path.
Dictionaries – Using dictionaries is a bit more straightforward, are they are structures that can directly map variables to others. We thus do not need to number the vertices. Thus, when we want to indicate that $v_1$ is a predecessor of $v_2$, we just need to put associate the value $v_1$ to key $v_2$ in the structure.

To go further

Important

The content of this section is optional. It contains additional material for you to consolidate your understanding of the current topic.

To go beyond

Important

The content of this section is very optional. We suggest you directions to explore if you wish to go deeper in the current topic.