Graph Storage: Edge List and Vertex List | Graph Representation in Memory

[00:00:00]Hello everyone! In our previous lessons we introduced you to graphs and we also looked at and talked about some of the properties of graph but so far we have not discussed how the can implement graph, how they can create a logical structure like graph of in computer's memory, So, let us try to discuss this. A graph as we know contains a set of vertices and a set of edges and this is how we define graph in pure mathematical terms. A graph G is defined as an ordered pair of set V of vertices and a set E of edges. Now to create and store a graph in computer's memory, the simplest thing that we probably can do is that we can create two list, one to store all the vertices and another to store all the edges. For a list, we can use an array of appropriate size or we can use an implementation of a dynamic list. In-fact we can use a dynamic list available to us in language libraries, something like vector in C++ or ArrayList in Java.

[00:01:11]Now a vertex is identified by its name, so the first list the list of vertices would simply be a list of names or strings.

[00:01:22]I just filled in names of all the vertices for this example graph here. Now what should we fill in this edge list here. An edge is identified by it's two endpoints, so what we can do is we can create an edge as an object with two fields.

[00:01:41]We can definde edge as a structure or class with two fields. One to store the start vertex and another to store the end vertex.

[00:01:51]Edge list would basically be an array or list of this type struct edge. In these two definitions of edge that have written here, in the first one I have used character pointers because in C we typically use character pointers to store or refer to strings.

[00:02:12]We could use character array also. In C++ or Java where we can create classes, we have string available to us as a data-type, so we can use that also.

[00:02:23]So we can use any of these for the feilds. We can use character pointer or character array or string data-type, if it's available depends on how you want to design your implementation.

[00:02:35]Now let's fill this edge list here for this example graph.

[00:02:39]Each row now here has two boxes. Let's say the first one is to store the start vertex and the second one is to store the end vertex. The graph that we have here is an undirected graph, so any vertex can be called start vertex and any vertex can be called end vertex. Order of the vertices is not important here.

[00:03:01]We have nine edges here, one between A and B another between A and C another between A and D and then we have B E and B F, instead of having B F as an entry we could also have F B but we just need one of them and then we have C G D H, E H and F H. Actually there is one more.

[00:03:31]We also have G H. We have 10 edges in total here not 9.

[00:03:36]Now once again, because this is an undirected graph, if we are saying that there is a edge from F to H.

[00:03:43]We are also saying that there is an edge from H to F. There is no need to have another entry as H F, we will necessarily be using extra memory.

[00:03:54]If this was a directed graph F H and H F would have meant two different connections which is the start vertex which is the end vertex would have mattered. Maybe in case of undirected graphs we should name the fields as first vertex and second vertex and in case of directed graphs we should name the fields as start vertex and end vertex.

[00:04:17]Now our graphs here could also be a weighted graph.

[00:04:21]We could have some cost or weight associated with the edges. As we know in an unweighted graph cost of all the connection is equal but in a weighted graph, different connections would have different weight or different cost. Now in this example graph here, I have associated some weights to these edges. Now how do you think we should store this data, the weight of edges. Well if the graph is weighted we can have one more field in the edge object to store the weight. Now an entry in my edge-list has 3 fields.

[00:04:55]One to store the start vertex, one to store the end vertex and one more to store the weight. So this is one possible way of storing a graph.

[00:05:04]We can simply create two lists, one to store the vertices and another to store the edges, but this is not very efficient. For any possible way of storing and organizing data we must also see its cost and when we say cost we mean two things - time cost of various operations and the memory usage.

[00:05:30]Typically we measure the rate of growth of time taken with size of input or data, what the also call time complexity and we measure the rate of growth of memory consumed with size of input data, what we also call space complexity. Time and space complexities are most commonly expressed in terms of what we call Big-Oh notation. For this lesson, I am assuming that you already know about time and space complexity analysis and Big-Oh notation.

[00:06:02]If you want to revise some of these concepts then you can check the description up of this video for link to some lessons.

[00:06:09]We always want to minimize the time cost of most frequently performed operations and we always want to make sure that we do not consume unreasonably high number. Okay, so let's now analyze this particular structure that you're trying to use to store our graph. Let's first discuss the memory usage.

[00:06:28]For the first list, the vertex list, least number of rows needed or consumed would be equal to number of vertices. Now each row here in this vertex list is a name or string and string can be of any length.

[00:06:46]Right now all strings have just one character because I simply named the node A B C and so on but we could have names with multiple characters and because strings can be of different lenghts. All rows may not be consuming the same amount of memory like here. Here, I'm showing an intra-city road network as weighted graph.

[00:07:09]Cities are my nodes and road distances are my weights.

[00:07:14]Now for this graph as you can see names are of different lengths, so all rows in vertex list or all rows in edge list would not cost us same.

[00:07:25]More characters will cost us more bytes. But we can safely assume that the names will not be too long. We can safely assume that in almost all practical scenarios average length of strings will be a really small value.

[00:07:41]if we assume it to be always lesser than some constant then the total space consumed in this vertex list will be proportional to the number of rows consumed that is the number of vertices or in other words we can say that space complexity here is Big-Oh of number of vertices.

[00:08:01]This is how we right number of vertices with two vertical bars.

[00:08:05]What we basically mean here is number of elements in set V.

[00:08:09]Now for the edge list, once again we are storing strings in first two fields of edge object.

[00:08:16]So once again each row here will not consume same amount of memory but if we are just storing the reference or pointer to a string like here in the first row instead of having values filled in these two fields, we could have references or pointers to the names in the vertex list.

[00:08:35]If we will design things like this, each will consume same memory.

[00:08:39]This in fact is better because references in most cases would cost us a lot lesser than a copy of the name and as reference we can have the actual address of the string and that's what we're doing when we're saying that start vertex and end vertex can be character pointers or may be a better design would be simply having the index of the name or string in vertex list.

[00:09:05]Let's say A is at index 0 in vertex list and B is that index 1 and C is at index two and I'll go on like this. Now for start vertex and end vertex, we can have two integer fields. As you can see in both my definitions of edge, start vertex and end vertex are of type int now and in each row of edge list first and second field are filled with integer values. I have filled in appropriate values of indices. This definitely is a better design and if you can see now each row in edge list would cost us the same amount of memory. So overall space consumed in edge list would be proportional to number of edges or in other words, space complexity here is Big-Oh of number of edges. Okay, so this is analysis of our memory usage. Overall space complexity of this design would be Big-Oh of number of vertices plus number of edges.

[00:10:14]Is thiis memory usage is reasonably high? Well, we cannot do a lot better than this if we want to store a graph in in computer's memory. So we are alright in terms of memory usage.

[00:10:25]Now let's discuss time cost of operations.

[00:10:29]What do you think can be most frequently performed operations while working with graph. One of the most frequently performed operations while working with graph would be finding all nodes adjacent to a given node, that is finding all nodes directly connected to a given node. What do you think would be time cost of finding all nodes directly connected to a given node.

[00:10:53]Well, we will have to scan the whole edge list. We will have to perform a linear search. We will have to go through all the entries in the list and see if the start or end node in the entry is our given node.

[00:11:06]For a directed graph, we would see if the start node in the entry is our given node or not and for an undirected graph we would see both the start as well as the end node.

[00:11:16]Running time would be proportional to number of edges or in other words time complexity of this operation would be Big-Oh of number of edges. Okay, now another frequently performed operation can be finding if two given nodes are connected or not. In this case also, we will have to perform a linear search on the edge list. In worst case we will have to look at all the entries in the edge list. So worst-case running time would be proportional to number of edges. So for this operation too, time complexity is Big-Oh of number of edges. Now let's try to see how good or bad this running time Big-Oh of number of edges is. If you remember this discussion from our previous lesson in a simple graph, in a graph with no self loop or multi edge. If number of vertices that is the number of elements in set V is equal to n, then maximum number of edges would be N * N-1.

[00:12:21]if the graph is directed.

[00:12:24]Each node will be connected to every other node and of course minimum number of edges can be zero.

[00:12:31]We can have a graph with no edge. Maximum number of edges would be N * N-1 / 2 if the graph is undirected but all in all if you can see number of edges can go almost up to square of number of vertices.

[00:12:48]Number of edges can be of to order of square of number of vertices.

[00:12:52]Let's denote number of vertices here as v, so a number of edges can be of to order of v^2. In a graph, typically any operation running in order of number of edges would be considered very costly. We try to keep things in order of number of vertices.

[00:13:14]When we are comparing the two running times this is very obvious Big-Oh of v is a lot better than Big-Oh v^2.

[00:13:22]All in all this vertex list and edge list kind of the representation is not very efficient in terms of time cost of operations.

[00:13:31]We should think of some other efficient design. We should think of something better.

[00:13:35]We will talk about another possible way of storing and representing graph in next lesson. This is it for this lesson. Thanks for watching.