Skip to playerSkip to main content
Neural Lantern
  • 2 months ago
Hello there. Let's talk about representing a directed, unweighted graph inside your machine using an edge list.

We start with the vertices, then list every outgoing edge as a start-end pair. Direction matters now, so the order in each tuple is the start node first and the end node second.

Then we upgrade the list: swap node values for indexes so you can jump to any vertex in constant time. Scanning edges is still linear in the number of edges, but you no longer scan the whole vertex list too.

Next video: directed and weighted, same edge list idea.

Subscribe if this helped. Leave a comment if something is unclear.

00:00 Intro to directed unweighted edge lists
01:24 Adding directions to the graph
02:32 Graph as vertices plus edges
03:22 Building the vertex list
04:29 Starting the edge list
05:54 Why tuple order matters
06:53 Listing outgoing edges by node
09:32 Counting the edges
10:26 Linear-time scan problem
11:34 Index-based edge list
13:20 Constant-time vertex lookup
14:35 Recap and next video
15:06 Subscribe and wrap-up

edge list, directed graph, unweighted graph, graph representation, adjacency, graph theory, data structures, vertices and edges, directed edges, graph tutorial, computer science, programming graphs, index optimization, constant time lookup, linear time edges

=-=-=-=-=-=-=-=-=

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
Transcript
00:02Hello there. Let's talk about representing a directed, unweighted graph inside your
00:08machine using an edgelist representation.
00:13Okay.
00:20All right, so hopefully you've been watching all my videos in a row. If you haven't, then
00:25this screenshot that you're looking at right now is basically the last slide from showing
00:30how to represent an undirected but weighted graph inside the machine. If you didn't watch
00:35that, that's going to be okay. I'm basically going to do this from scratch just with a
00:39different type of graph, but you probably should have seen my other graph videos because I just
00:44kind of show you some graph terminology like, you know, what do these edges mean? You know,
00:48like what is a graph, stuff like that. So we're going to change this to directed and maybe
00:53for starters, we'll say unweighted. It's still an edgelist representation. I'm going to erase
01:00a whole bunch of stuff here and just try to keep the graph. So directed and unweighted.
01:04Oh man, I got to erase everything. Why did I even copy paste this? I may as well just start
01:10from scratch. Okay.
01:14So yeah, this is unweighted. Bro, what am I doing? Wasted a whole bunch of time. Could
01:18have just drawn a bunch of lines. It would have been a thousand million times faster. Okay.
01:25So yeah, we're going to, we're going to add a direction on every single edge because right
01:28now this is an undirected unweighted graph. We need to make it a directed unweighted graph.
01:33So I'm just going to add an arbitrary direction to every single edge. So man, that circle is
01:38huge. I got to tell that, I got to make that, that dude chill out and calm down and stuff.
01:43It's kind of weird. Man, you're cramping my style. I don't know. This is my style. Maybe
01:50just like a giant, crazy cartoon circle. Kind of cool. All right. So basically, I'm just going
01:55to make sure that every single edge has an arrow going in some direction. And I got to make sure
02:01that there are no edges that have two arrow, arrow directions. So I'm going to look at the three.
02:08It's got incoming, outgoing. Okay. Then I'm going to look at the 13. Seems good. Look at the sixes
02:15edges. Seems good. I mean, a little sloppy, but I'll take it. And then the 12, same thing. It's all
02:23right.
02:2415, same thing. It's all right. 18. It's all right. Okay. So we have a graph. It's directed and there
02:30are no weights on the edges. So it's an unweighted, but directed graph. The first thing that I have
02:35been saying in these videos is that in the edge list representation of a graph inside the machine,
02:41we'll say that your graph is actually a tuple, which is a collection of your vertices and also
02:47your edges. Don't make one of my E's. Dang, you can make one of that E. Try again. Yeah. So
02:54it's a
02:54collection of vertices and also edges. In my previous, in my previous videos, we talked about paths that
03:00use nodes or edges to represent, you know, like where you go, how you can travel around the graph.
03:05That edge list concept is going to come back here for the edge list representation of a graph.
03:11So the first thing I'm going to do is represent my vertices. We'll get this in the previous video.
03:16I'm just going to say that
03:21V is equal to something. Whoops. Should be a list.
03:25We usually say this is a vertex list, but in practice, I like to use a vector
03:30because it's faster to jump to a particular index in a vector.
03:34That's, you know,
03:36that time complexity stuff is for another video, but
03:38I'm just going to say edge list. Keep in mind, you may consider
03:41making a vector instead of a list.
03:43So what am I going to do? I just have to represent every single node, every single vertex in the
03:48entire graph.
03:48So I'm going to start, I'm going to go from left to right. I'm going to start with a 3
03:51and then I'm just going to go 13, 6, 12, 15, 18.
03:56I've said this before in other videos, but you should probably imagine that you're not really storing these
04:01templated data types, you know, the values that the nodes hold.
04:04You probably shouldn't store those values directly in the vertex list.
04:08You should probably store actual nodes like pointers to nodes, smart pointers to nodes, node objects, whatever it is you
04:14want to do.
04:16But I'm just going to do the values for simplicity.
04:20So we got that.
04:22And then I'm going to maybe do like another little representation here for our edge list.
04:29So the vector list is already done.
04:32Like, you know, the collection of, sorry, the vertex list, the collection of vertices or nodes, that's already finished.
04:38That's all you really have to do, just describe what nodes are in the graph.
04:41And now we're going to describe how those nodes are connected to each other, if at all, using the edge
04:47list.
04:47So I'm going to do edge list is a list here.
04:50This probably is going to be a linked list or a list structure and not a vector.
04:56So from left to right, I'm going to look at one node and then I'm going to scan my eyes
05:01to the right
05:01and see if it's connected to anything else on the right, just like we did in the other videos.
05:05So the three node, I'm going to make a tuple here to represent how to describe the three node.
05:11The three node, I'm going to make a mistake in a second just for fun.
05:15It's connected to the right, to the 13 node.
05:18Okay, so the start node and then the destination node and then the weight, if it did exist in this
05:24graph, but it doesn't.
05:25So I'm not going to put the weight.
05:26You could put a one if you wanted to, but like we usually don't do that when we're diagramming an
05:31unweighted graph.
05:33So that's one entry, so that's one edge.
05:36I'm going to do another entry, another tuple, and I'm going to say, what else is the three connected to?
05:40The three is also connected to the 18, and it's also connected to the 12.
05:47But here's the problem though.
05:48Now that this is a directed graph, the order of the nodes really matters.
05:53In the previous two videos that I just did, when we had undirected graphs,
05:58it didn't matter if you swapped the 13 and the 3 because there was no direction on the edges.
06:02But in this graph, we have to obey the direction in the tuple as well.
06:07So we're going to say that the first item in the tuple, I'm just going to do a little example
06:12here,
06:13is the start node and the second item is the end node, just to make it a little bit more
06:18clear.
06:20So that means the 3, it only really goes out to the 13, it doesn't go out to the 12,
06:2612 goes out to the 3, not the other way around.
06:28And same thing for the 18, the 3 doesn't go out to the 18, the 18 comes to the 3.
06:32So that means we're actually done describing the 3 node,
06:35because we're only really supposed to be doing outgoing edges here where,
06:39I mean, if our pattern is we want to have the node that we're looking at be first in the
06:46tuple,
06:46well, that means it's the start node, not the destination node.
06:50So we're basically done with that row.
06:54The next node I'm going to look at is the 13.
06:57So I'm going to say the 13 goes where?
06:59It doesn't go to the 3, we already handled that anyway.
07:02We handle everything that's to the left in the past.
07:05If you look to the right, the 13 does go out to the 6, I'm going to put a 6
07:09right there.
07:10Okay, that's actually it for the 13.
07:12It had an incoming edge on the 3, which was already handled,
07:16plus the 13 can't start for an incoming edge, because the order matters now.
07:20So we're just done.
07:22Now we look at the 6 node.
07:24The 6 node, the nodes on its left that it's connected to are just the 13,
07:29but it had an incoming edge from the 13, so that's already handled.
07:33Notice how it's handled right there.
07:34So we're not going to do that.
07:36The 6 goes out where?
07:37It goes out not to the 18, but it goes out to the 12.
07:41So it goes to the 12, and then the 6 also goes out to the 15,
07:46because that's the direction of the edge.
07:48So now we're finished here with the 6.
07:50I'm going to do another row.
07:52I'll look at the 12.
07:53Does the 12 go out anywhere?
07:55It goes out to the 3.
07:58And in previous videos, at this point, I would have said,
08:00that's already handled because it's off to the left in an undirected graph.
08:04But now that we have a directed graph,
08:06we may have actually skipped naming the 3-12 connection
08:11because the 12 would need to come first,
08:14and I like to kind of say start nodes are the node that I'm looking at.
08:16So just, you know, scan the edge list real fast just to make sure
08:21if, you know, we see a 12 here, 12, 3 is correct.
08:25Do we have another 12, 13 anywhere else?
08:28Do we have a 3, 12, which would have been wrong for sure?
08:30No, we don't.
08:31Okay, so we're okay.
08:32Okay, the 12 doesn't go out to any other nodes.
08:36So we're done looking at the 12.
08:38So now we're going to do the 15.
08:40The 15 doesn't go out anywhere, so we're actually done already.
08:43There's nothing to do for the 15.
08:44Let's look at the 18.
08:46The 18 goes out to four other nodes.
08:49So the 18 goes out to the 3,
08:51and the 18 goes out to the 6,
08:56and the 18 goes out to the 12,
08:59and the 18 goes out to the 15.
09:03Let me just make sure that I've not screwed this up horrendously.
09:06I think at the very beginning of this video, I was saying,
09:08oh, we look at the left, and they're handled already.
09:11But that was a mistake.
09:11That was the other videos.
09:13It's really all about the node you're looking at
09:15is supposed to be the start node,
09:17so you can only look at outgoing edges,
09:19not necessarily left or right.
09:21But I still hit the nodes from left to right
09:23so that I can keep track of which nodes I've done.
09:26Anyway, how many edges do we have?
09:27We have 1, 2, 3.
09:31Oh, my God.
09:321, 2, 3, 4, 5, 6, 7, 8, 9.
09:379 or 10?
09:38How many do we have in this edge list?
09:391, 2, 3, 4, 5, 6, 7, 8, 9, 9.
09:42Why did I think it was 10?
09:431, 2, 3.
09:45You know what?
09:47I'm going to do it the easy way.
09:50This is what you should do, by the way.
09:52Eyeballing things is a really easy way to get everything wrong.
09:56I've done it before.
09:58So we're going to say 1, 2, 3, 4, 5, 6, 7, 8, 9.
10:08Okay, I guess that was all right.
10:10So I'm going to just reorder the graph
10:12so I can continue working on that one right there.
10:16So now we have an edge list representation of our graph
10:20where we have named all the edges and named all the vertices.
10:23So this is great.
10:24So as I said in previous videos,
10:25this presents a little bit of a problem in terms of speed
10:28because what if for the sake of argument,
10:30I was kind of scanning through my edge list.
10:34I'm like, you know, let's look at that one.
10:35Let's look at that one.
10:36Let's look at that one.
10:37And I'm spending, you know, linear time.
10:40If you don't know linear time, that's okay.
10:41I'm going to cover that in some other video.
10:43But basically it's not super fast.
10:46Linear time based on the number of edges.
10:47If I'm scanning all the edges.
10:49At some point I might stop and ask,
10:51you know, what's going on with this 18 and 12 edge?
10:55Maybe I want to manipulate the 18 node and the 12 node.
10:59So, you know, this 18 and 12,
11:02we have to somehow go find those nodes
11:05if we want to manipulate them.
11:06And how do we do that?
11:07We have to scan the vertex list.
11:09So we found the 12 there.
11:11Keep scanning.
11:12That might be another full scan.
11:13And then we found the 18.
11:14So this is linear time to scan the edge list,
11:18which is not super scalable.
11:20And then also linear time for the number of vertices.
11:26So this is kind of bad.
11:28We could make this a lot better.
11:30So I'm going to show you the upgrade
11:31that I've been doing in the previous videos.
11:33So I'm going to make a copy of my edge list here.
11:37Stick it right there.
11:38Yep.
11:39Okay.
11:41We're still going to say that the first node
11:42is the start node and the second node
11:44is the end node.
11:45But now I'm going to index the vertices
11:50instead of just naming their values.
11:53So what do I mean by that?
11:54Again, imagine that this vertex list
11:56is really just like an array or a vector.
11:58That means every single vertex has an index.
12:03So that's index 0 and 1 and 2 and 3 and 4 and 5.
12:09So what if I just went ahead
12:11and changed all of the values
12:14into just indexes?
12:15And we'll have a huge speed up.
12:18So the 3 node, that's really index 0.
12:20The 13 node, that's index 1.
12:22I can put a 1 there.
12:24The 6 node, that's index 2.
12:26I can put a 2 there.
12:27The 12 node, that's index 3.
12:29The 6 node, again, that's index 2.
12:31The 15 node, that's index 4.
12:32Again, all I'm doing is I'm just
12:34looking at the node value.
12:35Like, for example, this 12 here.
12:37I'm just looking at the 12
12:38in the vertex list
12:39and I'm looking at its index
12:41and I'm saying, oh, that's index 3.
12:43So I'm going to put a 3 there.
12:44Then I look at the 3 node.
12:45This can be confusing
12:46because there's actually a 3 node
12:48and a 3 index.
12:49But I'm looking at the 3 node,
12:50which is really index 0.
12:53If I forget to do that on any of these,
12:54leave me a comment.
12:55Sorry.
12:56So the 18 node is index 5.
12:59The 3 node is index 0.
13:0018 is 5 again.
13:036 is index 2.
13:0418 is 5 again.
13:0712 is index 3.
13:0818 is 5 again.
13:1015 is index 4.
13:12So now I've converted
13:13all of the items in the tuples
13:16to an index-based edge list representation,
13:19whereas the one over here
13:20was like the value.
13:22So now if I'm really going to work
13:24with the whole entire graph,
13:25and I'm just scanning everything,
13:27searching, doing some kind of an operation
13:28where you might have to spend
13:30the slow time scanning some edges,
13:33then I did have to spend,
13:35you know, linear time still
13:36based on the number of edges
13:37to go find some edge in particular
13:40or scan all the edges.
13:41But I didn't have to do scanning
13:44for the vertex
13:45because the vertex list
13:46already tells me
13:47exactly where to go.
13:49So for example,
13:49this 3 right here,
13:50that's telling me
13:51go directly to index 3
13:53to find the 12 node
13:54that you're interested in.
13:56Well,
13:57if you have an array
13:58or a vector
13:59for that vertex list,
14:00then you can jump
14:01to any index
14:02in constant time
14:03which is like instantaneous
14:04or it's not necessarily
14:06instantaneous literally
14:07but the time cost
14:09does not grow
14:10with the size of your data set.
14:11So it's like lightning fast.
14:12It's the holy grail
14:14of time complexities.
14:16Nothing I know is better.
14:18I don't know.
14:19So E plus 1,
14:21that's really just
14:21going to end up being
14:22O of E, right?
14:24So just linear time
14:24based on the number of edges
14:26rather than both
14:27the number of edges
14:28and the number of vertices.
14:29So it's a lot faster.
14:33Anyway,
14:34so that's how you represent
14:36a directed and unweighted graph
14:38inside the machine
14:39using an edge list
14:40of representation.
14:42And then there's a little bit
14:43of an optimization
14:44on the right side.
14:46Okay,
14:46this video is already
14:48like 20 minutes.
14:48I'm going to cut it.
14:49In the next video,
14:51we're going to do
14:52the final of the
14:53four graph variations.
14:54We're going to do
14:55a directed and weighted graph
14:58represented with an edge list
15:00just like we did right now.
15:01So thanks for watching
15:02this video.
15:03I hope you learned
15:03a little bit of stuff
15:04and had a little bit of fun.
15:06See you in the next video.
15:07I will still be sitting here
15:08a week later,
15:09I promise.
15:10Anyway,
15:11see you later.
15:12Thanks for watching.
15:13Peeps!
15:15Hey everybody.
15:16Thanks for watching
15:16this video again
15:17from the bottom of my heart.
15:18I really appreciate it.
15:19I do hope you did
15:20learn something
15:21and have some fun.
15:22If you could do me
15:23a please,
15:24a small little favor,
15:25could you please
15:26subscribe and follow
15:27this channel
15:28or these videos
15:29or whatever it is
15:30you do on the current
15:31social media website
15:32that you're looking at
15:33right now.
15:34It would really mean
15:35the world to me
15:35and it'll help
15:36make more videos
15:37and grow this community.
15:38So we'll be able
15:39to do more videos,
15:40longer videos,
15:41better videos,
15:41or just I'll be able
15:43to keep making videos
15:44in general.
15:44So please,
15:45do me a kindness
15:48and subscribe.
15:49You know,
15:49sometimes I'm sleeping
15:50in the middle of the night
15:51and I just wake up
15:52because I know
15:52somebody's subscribed
15:53or followed.
15:54It just wakes me up
15:55and I get filled with joy.
15:56That's exactly what happens
15:57every single time.
15:58So you could do it
15:59as a nice favor to me
16:00or you could troll me
16:01if you want to just
16:02wake me up
16:02in the middle of the night
16:03and just subscribe
16:04and then I'll just wake up.
16:05I promise
16:06that's what will happen.
16:08Also,
16:08if you look at the middle
16:10of the screen right now,
16:11you should see a QR code
16:12which you can scan
16:13in order to go to the website
16:14which I think is also named
16:15somewhere at the bottom
16:16of this video
16:17and it'll take you
16:18to my main website
16:19where you can just kind of
16:20like see all the videos
16:21I published
16:22and the services
16:23and tutorials
16:24and things that I offer
16:25and all that good stuff
16:28and if you have a suggestion
16:32for clarifications
16:33or errata
16:34or just future videos
16:35that you want to see
16:35please leave a comment
16:36or if you just want to say
16:37hey what's up
16:38what's going on
16:39you know
16:40just send me a comment
16:40whatever
16:41I also wake up
16:42for those
16:42in the middle of the night
16:43I get
16:43I wake up in a cold sweat
16:45and I'm like
16:45it would really
16:47it would really mean
16:48the world to me
16:49I would really appreciate it
16:50so
16:51again
16:51thank you so much
16:52for watching this video
16:53and
16:55enjoy the cool music
16:56as I fade
16:57into the darkness
16:59which is coming
17:00for us all
17:33I'll see you next time
20:04Hello there.
20:05Let's talk about representing and balls.

Recommended