- 5 days ago
Learn how to represent an unweighted undirected graph using an edge list. We build a sample graph with nodes and edges, then show the vertex list and edge list as tuples. See why storing indexes instead of node values makes lookups faster in constant time. Follow along as we list every connection without duplicates. This is the first in a series covering all four combinations of weighted and directed graphs with edge lists.
00:00 Introduction to Edge List Representation
00:56 Drawing a Sample Graph with Nodes
02:05 Adding Undirected Unweighted Edges
03:10 Graph as a Tuple of Vertex and Edge Lists
03:40 Building the Vertex List
04:24 Storing Nodes as Objects with Indexes
06:13 Creating the Edge List of Tuples
07:00 Listing Edges by Node Values
11:36 Limitations of Storing Node Values
12:30 Switching to Index-Based Edge List
14:08 Constant-Time Lookups with Indexes
16:54 Summary of the Edge List Method
17:16 Preview of Next Videos in the Series
17:44 Closing Remarks and Subscribe Request
edge list, undirected graph, unweighted graph, graph representation, vertex list, node list, graph data structure, edge tuples, graph theory basics, coding graphs, index based edges, constant time lookup, undirected unweighted, graph algorithms, adjacency alternative
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main "pinned" video of this channel for offers and extras
00:00 Introduction to Edge List Representation
00:56 Drawing a Sample Graph with Nodes
02:05 Adding Undirected Unweighted Edges
03:10 Graph as a Tuple of Vertex and Edge Lists
03:40 Building the Vertex List
04:24 Storing Nodes as Objects with Indexes
06:13 Creating the Edge List of Tuples
07:00 Listing Edges by Node Values
11:36 Limitations of Storing Node Values
12:30 Switching to Index-Based Edge List
14:08 Constant-Time Lookups with Indexes
16:54 Summary of the Edge List Method
17:16 Preview of Next Videos in the Series
17:44 Closing Remarks and Subscribe Request
edge list, undirected graph, unweighted graph, graph representation, vertex list, node list, graph data structure, edge tuples, graph theory basics, coding graphs, index based edges, constant time lookup, undirected unweighted, graph algorithms, adjacency alternative
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main "pinned" video of this channel for offers and extras
Category
🤖
TechTranscript
00:00Hello there. Let's talk about representing an unweighted, undirected graph in your machine using an edgelist representation.
00:15Okay, so hopefully you watched my previous videos. If you haven't, you might want to take a step back and
00:19check them out.
00:20We talked about, you know, what is a graph? What are some basic rules and terminology of a graph? Not
00:24graph in paper, but a graph.
00:26And we talked about representing paths in graphs using either a list of nodes or a list of edges.
00:32And we're going to take the edgelist concept one step further, and we're going to actually just say this whole
00:38graph is being represented as an edgelist.
00:40It'll make sense in a little bit.
00:42But, so the first thing I'm going to do is try to set up my stuff, which is always set
00:47up wrong, because I'm the one setting it up and it always gets messed up.
00:51Okay, so I got a graph paper. And, oh, I got to make this other thing full screen.
00:55Sorry. Um, I'm going to draw a random graph just real fast.
01:00So, I'm going to do, I don't know, just some random nodes.
01:06So, remember, a graph is a collection of nodes and edges.
01:09It doesn't even have to have edges, but, you know, we'll just say.
01:12So, we're going to do, that's bad. Let me try one more time.
01:16We'll get that. Okay, so we get, I'm trying to get this circle perfect, because I'm going to have to
01:20duplicate it.
01:21Okay, so I've got a node here, and I'm just going to give it an arbitrary value.
01:26I'm going to say it's got a three, and then I'm going to duplicate it a few times just to
01:30make a graph that is a little bit interesting.
01:32So, we have something to kind of challenge us, I guess, so it's not incredibly boring.
01:39And then I'm going to change some of the values here, and then, well, I'll change the next ones.
01:44And then we'll start looking at edges. Which edges do we want to make?
01:47Okay, so right now we're just making a graph.
01:50Make this graph along with me if you want to, or, you know, after you think you understand, do another
01:55graph on your own.
02:00Okay, so I'm going to make some edges right now.
02:04Remember, this is going to be an undirected, unweighted graph.
02:06So, the edges are just going to be lines. They're not going to have direction on them, and they're not
02:11going to have weights on them.
02:12I'm going to do a line over here.
02:13I'm just randomly doing lines. It doesn't really matter what we do exactly.
02:18The point is going to be, let's practice representing this graph.
02:22Okay, so I'm just making a random graph.
02:24It's kind of like a little bit dense. I don't know.
02:27Maybe I'll just stop there, and then I'll add a wonky line just to prove we can be cool about
02:34this.
02:34I don't know. We'll do another one right here.
02:37So, it's a slightly more interesting graph.
02:39Okay, so that's just a graph, and what I'm going to do is I'm going to say this is a,
02:45you know, an unweighted, oops, weighted, undirected graph.
02:53And we're going to use the edge list representation.
02:57Did I spell check on this? I really hope I do. Nope.
03:02Okay, I guess I forgot to fix that months ago.
03:06All right, so then the next thing we're going to do is we're going to look at the idea of,
03:10like, how do we start with the edge list representation?
03:13Okay, the first thing I'm going to say is that our graph in an edge list representation is a tuple,
03:21just meaning it's, you know, some things put together.
03:23If you know tuples in coding already.
03:25Okay, the tuple is going to consist of a collection of vertices and edges.
03:31Well, it's going to be an edge list.
03:33Don't make fun of my E's, please.
03:35Anyway, so let's do the first thing is going to be the vertex list.
03:39So, how do we represent the vertex list or the node list?
03:43Well, I'm just going to say that my vertex list, V, is equal to something.
03:48And we'll just put inside of this some vertices.
03:52So, the easiest way when you're kind of drawing this right now is I'm just going to start putting the
03:55values of the node.
03:56I'm going to say, well, here's a 3.
03:59And I guess I could sort them for whatever reason if we want to do binary search on them later,
04:04but we're not going to.
04:06I'm just going to, maybe, you know what, I'll go from left to right.
04:08That'll make more sense just visually.
04:10So, I'll go from left to right, 3, 13, 6, 12, and a 15, and an 18.
04:16You can see all of those are nodes, right?
04:18Somebody stop me if I forgot a node.
04:22Okay, here's the thing, though.
04:24What are we actually storing in this vertex list?
04:26You probably don't want to store the node values.
04:28I mean, you could be a little slow and dumb, though.
04:30But we want the option to be a little bit faster later and also the option to, you know, turn
04:36these vertices into full classes.
04:38Like, give them extra properties and whatever.
04:39So, what I'm going to say is that I'm writing down the number 3 and the number 13 here for
04:45you.
04:45But you should imagine in your code, you would have an object of type vertex or node, like a full
04:51class.
04:52And you would basically be stuffing pointers inside of that vector, inside of that list.
04:58I keep saying list.
04:59It is called an edge list representation, but you can probably imagine that this could just as easily be a
05:05vector.
05:05If you've seen my other videos, you know what that is.
05:09But, so I want to be able to index this faster.
05:12So, for me personally, I make this a vector and not an actual list.
05:15But we're going to call it a list.
05:16Anyway, so, 3 should be a pointer to a full node object.
05:22Smart pointer, raw pointer, whatever you want.
05:2413 should be a full pointer to an entirely different node object with just 13 assigned as its template type
05:32value.
05:34Because we're making this a vector, we can actually index the nodes, right?
05:38So, like, this is like index 0 for the 3 node, index 1 for the 13 node.
05:43So, I'm just going to put the indexes here.
05:46Whoops, just to drive the point home a little bit further.
05:48So, if I told you, hey, let's do the node at index 2, you would know that is the node
05:54that is in the very middle with the value of 6.
05:56Because index 0 and 1 and 2 brings you to this node right here, which is a 6.
06:02So, this is going to help us later.
06:03Let me save this real fast, by the way.
06:06I'm just going to do that.
06:08Okay.
06:11So, the next thing that we need to do is make an edge list.
06:16The edge list is really where it's all at.
06:18That's really where all the data is.
06:19It's going to tell us exactly where everything is.
06:21Or it's going to describe the whole graph, pretty much.
06:24So, the edge list is another, we'll say that's a list.
06:27This could be like a linked list or a vector or whatever you want.
06:30I'm just going to say it's a linked list.
06:32And every item in the list is going to be another tuple.
06:36So, remember, above the graph itself was a tuple.
06:39Containing a vertex list and an edge list.
06:41So, the edge list is a list of tuples.
06:44Meaning, you know, items bundled together for one tuple and then just like a list of those.
06:49So, what I'm going to try to do is describe every single edge one by one using one tuple each
06:57inside of the edge list.
06:58So, the first thing I'm going to do just, you know, to make this a little bit easier is I'm
07:02going to ignore the indexes for the vertex list and I'm going to say, let's describe everything happening from the
07:09three node outwards or just to every other node.
07:12So, the three node itself, I'm going to look at its connections from left to right.
07:16So, the three node, let's just start by putting a three here.
07:20Maybe I should describe the legend real fast.
07:24The tuples would basically be the start node and then the end node and then the, well, the weight if
07:32there was a weight but we're doing an unweighted graph.
07:34So, it's really just going to be a tuple of two items.
07:37The other thing to keep in mind is that because this is an undirected graph, it really doesn't make a
07:42difference what node is the start node and what node is the end node.
07:45You can just swap them and it's totally fine.
07:47For me personally, I'd rather, you know, sort before assigning the start node and end node.
07:53That way when I read the graph later, it's a little bit faster because I wouldn't have to check in
07:56both directions.
07:57But, it really honestly doesn't matter right now.
07:59So, start node and end node.
08:01So, the start node here is 3 and the end node is going to be 13.
08:05So, that's the first thing that we're doing.
08:09That's the first tuple.
08:10And then I'm going to say, what else does the 3 connect to?
08:13It connects to the, not the 6, it connects to the 12.
08:17Okay, so the 3 connects to the 12.
08:19Again, we could have said 12, 3, it wouldn't have mattered but I'm just going to try to keep it
08:24sorted.
08:25So, then what else does the 3 connect to?
08:27It connects to the 18, doesn't connect to the 15.
08:31And just confirm that if I'm looking at the 3, I can see 3 lines touching it.
08:35So, that means, okay, there's got to be 3 tuples for the 3.
08:39So, I'm going to say 3 connects to the 18.
08:41And now I've described everything happened to do with the 3 node.
08:45So, I will simply continue, let's see, should I do like a new line?
08:51Maybe I should try to do a new line for every start node.
08:54So, this is easier to look at.
08:57Okay, so I'm going to do that and I'm going to say the next line is,
09:02we'll start at the 13 this time.
09:04So, the 13, the 13 is also connected to the 3 because it goes in both directions with an undirected
09:08graph.
09:08But, we already described that connection with that first row.
09:12So, 3 comma 13 describes 13 comma 3.
09:15I don't want to duplicate edges.
09:17So, forget about that.
09:18Let's look at what else 13 is connected to.
09:20It's connected to the 6.
09:22So, I'm just going to put 13 comma 6.
09:24And then that's the end of the 13's connections.
09:28Oh, I could have used tabs for that.
09:29Hang on, let me do that.
09:31Okay.
09:32So, now let's look at the 6 node.
09:356 is not connected to the 3.
09:37It is connected to the 13.
09:39But, we already described the 13, 6 connection in the previous row.
09:43So, forget that.
09:44And then I'm just going to look to the right.
09:46So, the 6 is connected to the 12 and the 15.
09:50The 12 and the 15.
09:52And also the 18.
09:53So, I'm going to do 6 comma 12.
09:55Maybe I'm going to do a copy paste here real fast just to make it easier.
09:596, 12 and 6, 15 and 6, 18.
10:04So, again, all I'm doing is describing, you know, what other nodes the current node is touching.
10:10And I'm going to do that using a tuple that just has one node and has another node.
10:15And that's pretty much it.
10:16So, when we're done with this, we're going to look at the 12 node.
10:2112 node, it's connected to the 6, already handled.
10:25It's connected to the 3, already handled.
10:27And it's connected to the 18, not handled yet.
10:31So, I'm going to say 12 goes out to 18.
10:34Okay, then we're going to look at the 15 node.
10:3815 and 6, that's already handled in that third row.
10:42So, forget that.
10:4315 and 18, that is not handled yet.
10:46So, we're going to do 15 comma 18.
10:48By the way, this is one benefit of going from left to right visually.
10:52All I really have to do is just look my eyes to the right and I'll see nodes that I
10:55need to take care of.
10:56And if I look my eyes to the left, I'll see nodes that I already took care of, if that
11:00makes sense.
11:02So, now that we're done with the 15, let's see what we did, 3, 13, 6, 12, 15, let's just
11:08take care of the 18.
11:09If there's anything left to take care of, I can guarantee there's not going to be.
11:13Because every node, the 18 is the node on the farthest, you know, the furthest to the right.
11:18So, everything on the left is already handled.
11:20So, we don't even have to put anything for the 18 node.
11:23Okay, give me a second to clean up this graph real fast.
11:26I think I want to maybe move this up a little bit.
11:31Okay.
11:32Now, here's the thing though.
11:33We've only named node values.
11:35So, if we wanted to, I don't know, let's say check to see if the, let's say we have an
11:41edge.
11:41We're looking at the 3, 13 edge.
11:44And we're asking now, do both of those nodes exist?
11:48The edge describes these two nodes.
11:50Do they exist?
11:51Or maybe let's look at the 3 here.
11:54And we want to figure out just, you know, what other nodes does 3 touch?
11:57So, we start iterating through all the edges here.
12:01How can we actually get a pointer to that node to manipulate it in the code?
12:06Right now, it's okay because it's a diagram.
12:08But, you know, this is not very good storing values directly in this notation.
12:12In your code, you probably want to store pointers there.
12:17But maybe not necessarily smart pointers.
12:19They take a little bit of extra memory and it's kind of cumbersome.
12:22But we could store an index into this vertex list to make things a little bit faster.
12:27Let me show you what I mean.
12:29But first, I'm going to duplicate this list that we just made already.
12:35Duplicate it over here.
12:37And maybe I'll label the first one and I'll say, so we already have start node and end node.
12:42I'm going to say E underscore by value.
12:46So, we're storing the edge list by node values.
12:49And then here, we're going to store nodes by their index in the vertex list.
12:55So, what do I mean by index?
12:56Well, okay, right here, the first node that we're mentioning is the 3.
13:00Well, look at the 3 node in the vertex list.
13:03It's at index 0, right?
13:04So, I'm just going to put a 0.
13:05That's it.
13:06Change it to an index.
13:08Then I look at the 13.
13:09That's index 1.
13:10And then I look at the 3 again.
13:12That's index 0.
13:14And then the 12 is index 3.
13:16And then the 3 again is index 0.
13:18And the 18 is index 5.
13:21If that was too fast, I'm sorry.
13:22Just rewind and play it back in slow motion.
13:25I think this video is already getting way too long.
13:27So, then I do the same thing for every single other tuple.
13:31So, the 13 node, that is index 1.
13:35So, I'm going to put a 1 there.
13:36The 6 node is index 2.
13:38Go on to the next node.
13:40So, the 6 node is index 2.
13:43And then the 12 is index 3.
13:46The 6 is 2.
13:47And the 15 is actually 4.
13:49The 6 again is 2.
13:51The 18 is 5.
13:54Move on to the 12 node here.
13:56That's index 3.
13:5718 node is index 5.
14:00And then the 15 is index 4.
14:02And then 18 again is index 5.
14:05So, now on both sides, like in both of these edge lists, I'm representing the graph.
14:10It's just that one can be a little bit more efficient than the other.
14:13For example, if I was going to, let's just say I wanted to scan every single edge in the graph.
14:18Well, I could scan this list right here in linear time.
14:22So, linear time based on the number of edges.
14:25And every single time I see an edge, I can jump directly to the corresponding vertex or node in constant
14:32time because I have an index.
14:34So, for example, let's say, you know, this 6 node touching the 15 node.
14:40So, that particular edge right there.
14:42Let me, I want to be more interactive here.
14:45How can I do this?
14:47Okay.
14:49Suppose I want to do this node right here.
14:55This 612 node.
14:57And so, that's going to be pointing to this edge right up here.
15:01I want to see, you know, what's going on with both of those nodes.
15:05Well, if I was looking at the value based edge list.
15:09And I wanted to get a hold of, let's say, the 6th node itself.
15:11So, I can, like, do something with that vertex.
15:14Like, delete it or move it or just whatever.
15:15I would have to then scan the entire vertex list.
15:20I'd have to go, you know, this one, this one, this one, this one, this one.
15:22Until I eventually found the corresponding value.
15:26This wouldn't really support duplicate values either.
15:28It would be kind of hard to do that.
15:31But I've slowed down the program.
15:33It's linear time based on the number of vertexes.
15:36And if you were already doing linear time based on the number of edges,
15:38this is, like, it's technically still a scalable data structure.
15:42But it's not super fast.
15:43It could be faster.
15:44On the other hand, so, like I just said, sorry for repeating myself.
15:50If we did the index based edge list, it says 2, 3 here, which is the 6, 12.
15:59How can I find the 6 node?
16:01Well, I just look at index 2.
16:04And instead of scanning, oh, gosh, hang on.
16:10Not as fast as I used to be.
16:11Okay.
16:12Dude, there's, like, did you see that?
16:14There's a whole bunch of pink dots everywhere now.
16:17What have I done?
16:18Okay.
16:20So, uh, I'm looking at the 6, 12 edge.
16:23I see that the indexes are 2 and 3.
16:25That means in constant time, I can just jump directly to, I guess I'll put it in red.
16:33In constant time, index 2 right there.
16:36And index 3 right there.
16:38I do not have to scan the vertex list or the vector.
16:42I guess if it was a vertex list, like an actual linked list, then I'd still have to scan.
16:46Because it's linear time to do it.
16:48But, um, if it's a vector or an array, I can just jump to an index in constant time, so
16:53it's way faster.
16:54So, what I'm trying to say is that this representation is what you want to do in the code when
17:00it comes to, I don't know, representing diagrams and stuff.
17:02I don't know.
17:03The one on the left is more human friendly.
17:06So, this is the basic idea for how to represent an unweighted and also undirected graph in the machine using
17:12the edge list method of representation.
17:15So, I guess I'm going to cut the video.
17:18I hope you learned a little bit of stuff and had a little bit of fun.
17:21In the next video, I think I'm going to do, uh, weighted undirected graphs.
17:28So, I'm going to do four videos for this one representation type.
17:31I'm going to do unweighted, undirected, and then weighted, and undirected, and then unweighted, and directed.
17:37I'm going to do all four combinations.
17:39All right, see you in the next video.
17:41Thanks for watching.
17:44Hey, everybody.
17:45Thanks for watching this video again from the bottom of my heart.
17:48I really appreciate it.
17:49I do hope you did learn something and have some fun.
17:52If you could do me a please, a small little favor, could you please subscribe and follow this channel or
17:58these videos or whatever it is you do on the current social media website that you're looking at right now?
18:03It would really mean the world to me and it'll help make more videos and grow this community.
18:08So, we'll be able to do more videos, longer videos, better videos.
18:11Or just I'll be able to keep making videos in general.
18:14So, please do me a kindness and subscribe.
18:18You know, sometimes I'm sleeping in the middle of the night and I just wake up because I know somebody
18:22subscribed or followed.
18:23It just wakes me up and I get filled with joy.
18:25That's exactly what happens every single time.
18:28So, you could do it as a nice favor to me or you could troll me if you want to
18:31just wake me up in the middle of the night.
18:32Just subscribe and then I'll just wake up.
18:35I promise that's what will happen.
18:38Also, if you look at the middle of the screen right now, you should see a QR code, which you
18:42can scan in order to go to the website, which I think is also named somewhere at the bottom of
18:46this video.
18:47And it'll take you to my main website where you can just kind of like see all the videos I
18:51published and the services and tutorials and things that I offer and all that good stuff.
18:58And if you have a suggestion for clarifications or errata or just future videos that you want to see, please
19:05leave a comment.
19:06Or if you just want to say, hey, what's up?
19:08What's going on?
19:09You know, just send me a comment, whatever.
19:11I also wake up for those in the middle of the night.
19:12I get, I wake up in a cold sweat and I'm like, it would really, it would really mean the
19:18world to me.
19:18I would really appreciate it.
19:19So again, thank you so much for watching this video and enjoy the cool music as, as I fade into
19:27the darkness, which is coming for us all.
Comments