Directed Weighted Graph Edge List Representation

Neural Lantern

Learn how to represent a directed and weighted graph using an edge list.  We start from a directed unweighted example, add weights to every edge, then store the graph as a tuple of a vertex list and an edge list. Each edge is a tuple of start node, end node, and weight. Order matters because the graph is directed.  Then we convert node values to indexes so you can jump straight to a vertex in constant time instead of scanning the vertex list. That keeps edge scans closer to O(E) instead of O(E + V).  This is part of a series covering all four combinations: directed vs undirected and weighted vs unweighted. Watch the earlier videos for basic graph terms and the other representations.  Leave a comment if you want a topic covered next.  00:00 Intro to directed weighted edge lists 01:05 Starting from the directed unweighted graph 01:35 Adding a weight to every edge 02:48 Graph as a vertex list plus edge list 03:35 Writing the vertex list 04:18 Node classes versus raw values 05:18 Writing directed weighted edges 05:45 Order matters on directed edges 06:38 Walking remaining outgoing edges 09:08 Why value-based edges scan slowly 10:29 Replacing node values with indexes 12:36 Constant-time jumps after an edge scan 14:13 Series wrap-up 14:45 Subscribe and outro  edge list, directed graph, weighted graph, graph representation, data structures, graph theory, vertex list, adjacency, directed weighted graph, graph tutorial, computer science, algorithms, nodes and edges, index mapping  =-=-=-=-=-=-=-=-=  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://thao.funnymoment.net/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 and weighted graph inside your

00:07machine using an edge list representation words a lot of words okay so um I hope you

00:24watched my previous videos you didn't necessarily need to watch the previous three where we talked

00:28about edge list representation on the other types of graphs we're doing the directed versus

00:33uh undirected and weighted versus unweighted and all four combinations of those so uh you don't need

00:39to watch those others if you're just only interested in this but it's probably a good idea if you watch

00:43my other graph videos because we talk about basic graph terminology and like you know what is a graph

00:48and stuff like that but for now we're just going to continue um the screenshot you're looking at right

00:55now was the last part of the last video where we did a directed unweighted graph so i'm going to

01:00duplicate this real fast and i'm going to start modifying it so we can basically just move on

01:06with our lives so this is going to be directed and also weighted then i'm going to erase a whole

01:13bunch

01:13of other stuff because it's fun to draw again i don't know why but it is i like to do

01:17my drawings

01:19get that and then i'm going to get rid of that stuff okay and i'll get rid of this because

01:29i'd

01:29like to draw it okay i probably should have gotten rid of it first so i guess the real first

01:33thing that

01:33i'm going to do after erasing all that stuff is add weights to all the edges remember this has to

01:37be

01:37a weighted graph so this particular graph you're looking at right now is directed and unweighted so we

01:42have to add weights to all of the edges in my previous videos we talked about what is the meaning

01:48of weights you know these could be a cost these could be like some property like in a video game

01:53whatever you want them to mean these could even be classes with like complicated values

02:00but for now i'm going to say i don't know maybe this is an airport map and the weights are

02:05how much

02:06gas it takes to fly from one city to another maybe a node is a city city number six and

02:10city number

02:1012 you want to fly between them it's like five million jillion gallons of gas so let me just take

02:18a look real fast and make sure that i'm not forgetting any edge every single edge should have a weight

02:24i think there were nine edges here one two three four five six seven eight nine so i should see

02:32nine

02:32weights one two three four five six seven eight nine okay we're now ready to start representing this

02:40and what's going on with this computer okay the first thing uh that we talk about in all of these

02:45you know recent related videos is that in an edge list representation we'll say that our graph

02:51is a tuple meaning just like a collection of some things a tuple where the first item in the tuple

02:58is

02:58a vertex list or a node list and the second item is an edge list again in previous videos we

03:04talked

03:05about representing paths using nodes or using edges so the edge list path is going to come back to haunt

03:11us where we do our edge list graph representation which is different than an edge list path

03:17so how do we do our vertex list that's going to be pretty easy for this diagram

03:23i'm going to say that v is equal to oh it's pink let me change the color to be more

03:28serious okay

03:30the vertex list is going to be a collection of just all the nodes just naming all the nodes or

03:35having

03:35all the nodes i'm going to say it's a vertex list or a node list but really you probably want

03:41this to

03:41be a vector i've been saying that recently because it's faster to jump to a particular index in a vector

03:47than it is in an actual linked list or some other list-like data structure so we've got a vertex

03:53list

03:53i'm just going to name all the nodes so for me particularly i like to go from left to right

03:58you

03:58can sort them you can do whatever you want they just need to all be in there so i'm just

04:01going to

04:01say every node that we see in the graph is going to end up in this vertex list so we've

04:07got one two

04:08three four five six one two three four five six so we've got all the nodes in there

04:13another point that i've been making in the in these recent videos is that in real life in your code

04:19in

04:19your in your computer you don't really want to just have this value three here you don't want to

04:23have this 12 value here that the 12 value that's just the value that the node holds i mean if

04:29you

04:29want everything to be really fast maybe you know keep it bare bones but for me i like to have

04:34a full

04:34node class a full vertex class and make an instance of it so i can add a whole bunch of

04:40custom properties

04:41and functionality and other stuff onto my node so that that means i couldn't really put an integer

04:46there i would have to put a full node so keep in mind for yourself you probably want to try

04:50it both ways

04:51but um you probably might want to want an instance of a node class and maybe stick the instance right

04:57there in the vector or maybe make a smart pointer and so like you allocate you know a new pointer

05:03of

05:04an instance of the class or it's a raw pointer it's a smart pointer whatever so just keep in mind

05:09this

05:09diagram is more simple than your code but we're just diagramming today anyway so we put all the nodes

05:15in there the next thing i need to do is represent the edges so i'm going to put e is

05:19equal to

05:20another list and this probably does need to be a linked list or a list like data structure

05:24and not a vector there's not much point in jumping to an index i don't know you could probably come

05:29up with one but anyway so the edge list is going to be a list of tuples that describe one

05:35edge at a

05:36time so every little parenthesis that i put here that's going to represent one edge so again for me i

05:42like to go from left to right i'm going to start on the left node and i'm going to say

05:45that the start

05:45node is three and uh remember this is a directed graph which means the order if you looked at my

05:52previous videos the hang on uh the order of the nodes actually matters a lot like i can put three

05:59and thirteen but i cannot put thirteen comma three because the first item in the tuple is supposed to

06:05be the starting node and if you see i only have like an edge going from three to thirteen i

06:10don't have

06:10one going from thirteen to three so thirteen comma three would be invalid it would be totally bad

06:16so i'm going to say the three goes out to the thirteen so the three comes first and the thirteen

06:21is second and then i have to describe how much it costs so that's the third item in that one

06:26particular tuple it's going to be a one because the cost of that one particular edge is one one

06:31gasoline one millisecond delay one time whatever so then the next item is going to be where else

06:38of the three go to the three doesn't go anywhere else so we're done representing the three at least

06:44as a start node so next up uh i'm going to look at the thirteen where does the thirteen go

06:49to it goes

06:50to the six it doesn't go to the three the three goes to thirteen but this the thirteen doesn't go

06:55to

06:55the three so thirteen goes to six and it costs six because that's the cost of the edge there's two

07:01sixes

07:01here a little confusing but that's because one is a node and one is a weight the thirteen does not

07:06go out

07:07anywhere else so we're done with the thirteen i like to make you know different rows for every

07:11single start node you don't have to do that next up i'm going to look at the six the six

07:16does not go

07:17out to the 13 the six does not go out to the 18 there is a connection there but it's

07:23going in the

07:23other direction the six goes to the 12 and also to the fixed 15 so the six goes to the

07:2812 and that costs

07:29us five because that was the weight we assigned and the six also goes to the 15 with the cost

07:36of i think

07:36i just wrote seven in a weird way um so we go from six to 15 it costs us seven

07:42and then we're done

07:43looking at the outgoing edges of these six let me just double check out out yes now we're ready to

07:49move on to the uh the 12 node the 12 node has one outgoing connection it goes out to the

07:55three did i

07:56get that wrong in the last video leave a comment i don't know and then we're done with the 12

08:01node

08:02now we look at the 15 node oh that's why i had that feeling because the 15 didn't go anywhere

08:0615 has incoming connections but no outgoing connections so we actually can't write it down

08:10here there's no need then we look at the 18 node the 18 has outgoing connections to four other nodes

08:16to the three with the cost of three am i am i mind tripping myself when i'm doing these duplicates

08:2318 also goes out to uh the six with the cost of eight didn't trick myself that time the 18

08:30also goes

08:31out to the uh the 12 with the cost of two and then uh the 18 also goes out to

08:39uh

08:4115 with the cost of nine i i just realized recently it's a good idea to make faces at the

08:48camera

08:49uh for emotional thumbnails i don't know if you've picked up on that yet but yeah

08:54so let me just double check that i've got like nine edges and nine entries one two three four five

08:58six

08:59seven eight nine so i think i probably did it all right now there's a problem um i've been talking

09:06about this in in the recent videos there's a problem with this type of representation what if you are

09:11scanning through the edge list and you're like well i'm scanning this edge and that edge and that edge and

09:16that edge and that edge and then i come to the 18 uh six edge and i think well now

09:21i found some edge

09:22that was interesting for whatever reason maybe if i was scanning or doing some kind of like a operation

09:27that might have costed linear time so you don't have to know about this uh this is in other videos

09:34but basically it's not incredibly scalable it's not incredibly fast it is technically scalable just not

09:40incredible um linear time based on the number of edges so that kind of sucks um because if i wanted

09:47to

09:47do something with those nodes with the 18 and the 6 node i would then have to do another linear

09:52scan

09:52to find each node i'd have to go into my vertex list and i'd have to say well where the

09:57heck are those

09:58things where's 18 nope nope nope nope nope uh found the 18 and then there's another scan to find the

10:056

10:06so really this is going to end up being um linear time based on uh the number of edges and

10:12also

10:13uh the number of vertices so that's a little bit slower not too great

10:19the upgrade that we're going to do which we've been doing in all the other videos of of these

10:23recent uh edge list representations is i'm going to first i'm going to duplicate the vertex list like this

10:34and then i'm going to show you that uh each node each vertex has an index so i'm going to

10:40say

10:40you know this is index zero this is index one this is index two this index three when i type

10:47too hard

10:47i think my hand shakes the table that kind of sucks i need shock absorbers for my lumpiness oh so

10:55we have

10:56uh an index for every single vertex what if we uh what if we copy pasted the edge list over

11:02here on the left

11:04um what's going on it's not oh there it is dumb okay what if we copy pasted it and then

11:11we converted

11:12all of the values uh or um i guess you um maybe on the left side if you if you're

11:20doing this in the

11:21code you might put pointers instead of uh values so we'll just say that we'll convert the pointers

11:26or these values into indexes so this first tuple we're describing the edge that goes between 3 and 13

11:32with the cost of 1. 3 is sitting at index 0 in the vertex list so i'm going to change

11:37it to a 0. 13 is

11:38sitting at index 1 i'm going to leave the weight alone and then i'm just going to convert every

11:43other tuple to indexes so the 13 node that's sitting at index 1 the 6 node is sitting at index

11:482

11:49leave the weight alone the 6 node is at index 2 the 12 node is at index 3 the 6

11:54node again is

11:55index 2 the 15 node is at index 4 again leave the weights alone the 12 node is sitting at

12:02index 3 the

12:033 node is sitting at index 0 leave the weight alone the 18 node is sitting at index 5 the

12:113 node is

12:12sitting at index 0 i think i'm going too fast i'm probably going to screw something up we got index

12:165 there for the 18 and then 6 is uh index 2 18 is index 5 12 is index 3

12:2518 is index 5 uh 15 is index 4

12:29so all i did was just convert every node value or pointer if it's in your code to an index

12:34that references

12:36the vertex list why would i want to do this okay so like last time we said we would do

12:41o of e it would be

12:43linear time based on the number of edges if we're performing some sort of a search or examination

12:47of all the edges um so we have to like scan all the edges and then eventually we come to

12:52something we're interested in maybe we realize oh that's that's a special edge we want to see what's

12:56going on there maybe we want to grab those nodes and extract more information from them or modify

13:01them or do something to them this representation tells us exactly where to get where to go because uh

13:08this 5 is an index it's not a node value same thing for the 2 so index 5 gives us

13:15the 18

13:16and index 2 gives us the 6 notice how we still actually we're looking for the 18 and 6 nodes

13:23like we were you know in the previous uh i guess representation so now instead of scanning the vertex

13:31list we can just jump directly to an index and uh you know remember like if you're using an array

13:36or a vector it's going to be constant time to jump to an index it's like very very fast it's

13:42the holy

13:42grail of time complexities so it's really going to be something like o of e plus c or one or

13:49whatever you

13:50want to call it but it's going to reduce to just o of e so it's going to be a

13:53little bit faster notice how

13:55you know this one is going to take more time uh than that one maybe i'll put it in red

14:00to make the the more than the greater than operator feel feel bad and evil but anyway this is how

14:08you

14:08do edge list representation if you're interested in the in all four uh types of graphs being represented

14:14with an edge list representation check out all my other videos please leave a comment with ideas for

14:19stuff you want me to go over but uh i think i'm finished with this video it's been 15 minutes

14:24already

14:25i don't remember what i forgot to say but uh i guess we're done now thank you so much for

14:29watching

14:30i hope you learned a little bit of stuff and had a little bit of fun i'll see you in

14:33the next video

14:35i'm gonna get my gear i'm just kidding i'm gonna eat a bunch of cookies i'm just kidding i shouldn't

14:39do that but i probably will hey everybody thanks for watching this video again from the bottom of my

14:48heart i really appreciate it i do hope you did learn something and have some fun if you could do

14:53me a

14:53please a small little favor could you please subscribe and follow this channel or these videos

14:59or whatever it is you do on the current social media website that you're looking at right now

15:04it would really mean the world to me and it'll help make more videos and grow this community so

15:09we'll be able to do more videos longer videos better videos or just i'll be able to keep making videos

15:14in general so please do do me a kindness and uh and subscribe you know sometimes i'm sleeping in the

15:20middle of the night and i just wake up because i know somebody subscribed or followed it just wakes

15:25me up and i get filled with joy that's exactly what happens every single time so you could do it

15:29as a

15:30nice favor to me or you could you control me if you want to just wake me up in the

15:33middle of the night

15:33just subscribe and then i'll i'll just wake up i promise that's what will happen also uh if you look

15:40at the middle of the screen right now you should see a qr code which you can scan in order

15:44to go to the

15:44website which i think is also named somewhere at the bottom of this video and it'll take you to my

15:49main

15:49website where you can just kind of like see all the videos i published and the services and tutorials

15:54and things that i offer and all that good stuff and uh if you have a suggestion for uh uh

16:02clarifications

16:03or errata or just future videos that you want to see please leave a comment or if you just want

16:07to say

16:08hey what's up what's going on you know just send me a comment whatever i also wake up for those

16:12in the

16:13middle of the night i get i wake up in a cold sweat and i'm like this it would really

16:17it really mean the

16:18world to me i would really appreciate it so again thank you so much for watching this video and um

16:25enjoy the cool music as as i fade into the darkness which is coming for us all

16:52so

17:02so

17:03so

19:38Hey there.

Category

Transcript

Comments

Recommended