Video 6-9: Graphs via Wavelet Trees

0:02 Let's come to um to a more general data type, namely graphs, but let's only look at a very simple small trick of what you can do with graphs. I think um what I've shown you up to now, there's a lot of research and it's kind of very settled that we have good succinct data structures for this. Graphs are the boundary where it's a bit less clear what the ultimate solution is. It's not maybe known yet. Um and I'm going to show you a simple version um of what you can do. Um maybe let me just show the animation.

0:49 I can take a screenshot to remind you what this was what this was about. So, what what are you going to what we're going to do is we take our our graph and we take its adjacency string, which is just the adjacency list of all the vertices concatenated.

1:16 The vertices have labels one up to n. So, there's a fixed order in which I can write them down. Uh let me make it a bit bigger. Now, I'm I'm going to store this graph with two components. One is this string, which is a sequence, and we know how to store that, namely with wavelet trees. So, this sequence we'll store as a wavelet tree. And you'll see in a second why this is useful. But the the string itself would lose the connection would lose the boundaries between the neighborhoods. That would just read 3 5 3 4 5 1 3 4. But we also need to keep in mind when one node's neighborhood ended. And for that we'll have a second data structure, a bit vector, that is in as similarity to Louds is just the unary out-degree of each vertex. Uh to confuse everyone a bit is is using zero and one in the opposite way. So I put a one before the node before the vertex here and then as many zeros as it has out neighbors.

2:30 This you could also do differently, like it's a uh just a convention. But the ones now separate the different neighborhoods and so you can do rank and select to find your way through um the sequence. And with these together, you can answer all kinds of operations on the graph that you might be interested in. Or maybe more fairly I should say, you can answer precisely the operations that an adjacency list representation could also do. Um but we're a bit more space efficient. For example, um I can take the out neighbor, say of vertex two, um the second out neighbor. So the four, right? And how do I get there? Well, first of all, I need to know um where to where where does the neighborhood of vertex two start? That's the position of this one. So I'm doing a rank. Uh sorry.

3:35 I do a rank operation on my bit vector for the second one. A select operation for the second one. That gives me a position. And that position minus the ones I have, so minus two, is the starting position in the string of this guy's neighborhood. And because I want the second out neighbor, I just add two.

3:57 So, here um select gives me a position four in the bit vector. It's all It's one-based here. Um and then the second one and then I add That's the neighborhood. Okay, and I take the second out of these, take the starting position at at two. And then I can use access in the sequence to read out the out neighbor. Okay, that's kind of easy. Now, um I can also ask about the degree of a vertex. How do I do that? Well, I'm I'm going to find this one and this one and subtract their positions. Or I can do can go to the That's the easiest. So, we find the range by um selecting the second one and the third one and I look how far they are apart. These are my neighbors. And then I get these three.

5:03 Um Now, a bit more interesting is I can also ask for the edges in the opposite direction, which is something normally uh adjacency lists cannot do for a directed graph. You would not want to store the edges in both directions, but here we don't need to because the wavelet trees can do that. So, for example, um let's pick vertex three that has some incoming edges. Say I want the second incoming edge of vertex three in the order of the vertices, so this should be the one from uh vertex two. Okay? Now, how do I find that? Well, if I have an edge to vertex three, that's an occurrence of three in the string. So, I'm going to use rank on the string with character three.

6:04 Uh I want the second. Hey. It's a bit um uh clumsy, but so I want the three. And I want the second incoming neighbor, so I find the second occurrence of three in the adjacency string. That the wavelet tree can do for me. Now, I know where in that string that is. Now, which node does this belong to? Well, I use the bit vector. Specifically, a rank query to the left of this position gives me those two ones, so I'm in the second node's neighborhood. All right. Uh this is the position. And so, uh I find that this belongs to vertex two. Okay? So, now we can also do edges in the opposite direction, so we can do in-degree by just counting how many occurrences of three there are. Uh and I can also check if two are two vertices are adjacent um by This is also cute. So, is vertex two Does vertex two have an edge to vertex three?

7:12 Well, we find where's the neighborhood of vertex two, the out neighborhood. And we check if in that range there is an occurrence of four by asking rank of four at the end and rank of four at the beginning. If there is a difference between the number of occurrences of four to the left of these two positions, then there is a four in between. And so, two has an outgoing edge to four.

7:36 Okay. You can play with this a bit more if you want. Um >> So, just briefly what if we did what we what if we seen?

8:04 Wavelet tree over concatenated neighbor out neighborhoods. And a bit vector containing the unary out degree sequence. And so we can support in and outgoing Um now the running time for this is dominated by what the wavelet tree needs for rank and select. And that is uh log sigma. Now sigma here is the number of nodes. Okay, now as many different letters in my string. Um So here we have a a penalty in running time, but we can do this navigation in in both directions.

9:15 And the space we use for that is what the wavelet tree needs, which is all the bit vectors. So n log n plus big O of n bits.

9:32 And uh Sorry, this is m, the number of edges. The length of S is the number of edges. So, I store precisely log n bits. It's It's as space efficient as you can be if you have to write down uh an arbitrary list of edges. Uh and everything else is kind of for free. Note that a standard adjacency list representation is much uh much more wasteful. It would store for every edge a pointer, usually, if it's a linked list. And it may store another pointer per node.

10:24 It uses something like m log n Okay. Uh that's just one example. In general for graphs, um if if any graph is possible, then you can't do all that much better than this. And uh when you have specific when you know more about your graph, you can be more space efficient. But that's a bit more of a a wide open field what to do exactly in all cases. I'll leave it with that for succinct data structures. There's a lot more um that you can can read about uh for many kind of uh special case applications. They may be well known, and often times it's not so far to be to build one if you know your bit vectors well. That's often the core step to know.