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
17:03so
17:03so
17:03so
17:03so
19:38Hey there.
Comments