00:00Hello there! Let's talk about representing a directed, unweighted graph inside your machine using an adjacency matrix.
00:08It's going to be fun!
00:20Okay, sorry about that. Anyway, um, so I hope you've been watching my previous videos.
00:24We covered already how to do an undirected weighted graph and also unweighted graph using an adjacency matrix.
00:31We're going to basically represent a graph inside of the machine.
00:35Like, this is one of the ways that your machine can do it.
00:38We're not going to talk about code exactly, but, you know, kind of allude to code.
00:41But this is a really good way to, you know, get started in practicing the concept.
00:45Okay, first thing I want to say, I've said this in my previous videos, I'm sorry if you've been watching
00:50all of them,
00:51is that this matrix, this two-dimensional matrix, it's really just a one-dimensional array.
00:56Think about this, we have some numbers in an array. I'm going to put six numbers in there.
01:01We could just as easily represent this as a two-dimensional matrix, a two-dimensional array, right?
01:08It's the same amount of numbers.
01:10What's really happening under the hood when you have a two-dimensional array,
01:13is your computer just has it as a one-dimensional array.
01:16Okay, so the question is, why is that useful?
01:22Oh, hang on.
01:23Okay, anyway, so what I wanted to say is that you see a two-dimensional matrix,
01:27but really what's happening inside your computer is a one-dimensional matrix.
01:30I'm just going to make a one-dimensional matrix.
01:32I'm going to say we're putting numbers in the matrix.
01:34I'm just going to put like, you know, six hashes or pound signs or hashtags in the modern era.
01:41So a one-dimensional array could be represented as a two-dimensional matrix if we just reformat it a little
01:48bit.
01:48Notice how I'm just, you know, placing, you know, the last part of that first array on a second line.
01:54That's what's happening in the computer.
01:56Even if you're working with a two-dimensional array in your computer,
02:00it's still just a one-dimensional array under the hood,
02:02which means it's incredibly fast to access one particular index.
02:07Not necessarily to scooch things, remove things, and add things.
02:10But if I wanted to go to index three in a one-dimensional array,
02:14if you know time complexities already, that's really fast.
02:17That's constant time.
02:18We'll do time complexities in another video.
02:20But if I wanted to access, you know, a certain row in a certain column,
02:25intuitively you think, well, I got to like scan down and scan to the right.
02:28So maybe it's slower, but it's not because it's still just going to be math to find exactly the right
02:33offset
02:34in your two-dimensional matrix because it's really a one-dimensional array.
02:38All of the items in this array, I didn't say this in previous videos,
02:43all the items in this array are contiguously allocated.
02:46So all we really have to do is compute an offset from some starting memory location.
02:50So it's incredibly fast to read a cell in this matrix and to modify a cell in this matrix.
02:57You'll see in a second, well, you'll see in several minutes why that's one useful feature of an adjacency matrix.
03:04Okay, so adjacency matrix.
03:07Suppose you're presented with this diagram you see right here.
03:10This is a graph.
03:11It's got direction on all the edges.
03:13I really hope I didn't forget any particular edge.
03:15I think I've got arrows on all of them.
03:18We've got nodes and edges, and I just need to figure out how can I put that into a matrix
03:21so my computer, my program understands the graph and it has a representation of the graph.
03:28So with directed graphs, the start row, sorry, the start node and the end node actually matter a lot.
03:35In my other videos where we talked about undirected graphs,
03:37we could just easily swap the row and the column in this matrix and it didn't really make a difference
03:42because the whole matrix was going to end up being a mirror anyway.
03:45But that's not going to happen this time.
03:47So what I'm going to say for the way that I like to do things is the starting node is
03:52the row
03:53and the ending node is the column.
03:55So this is also an unweighted diagram, an unweighted graph, so we don't really need to store floats
04:02or infinities or anything like we did in the other video.
04:05We can just say that no connection means no connection is a zero and yes connection is a one.
04:11Of course you could still do that with floats if you want to, but whatever.
04:15You could have a matrix of booleans if you really wanted to, like true and false and true and false.
04:19But you know, for this diagram we're going to say zero and one.
04:22So I'm going to start with node number one and node number one therefore is going to be the source
04:28node
04:28and I'm going to see where does it go out to, what edges are outbound from the number one.
04:33So the start node is the one, that means the row is one that I'm working with
04:37and the destination nodes or the end nodes or the sync nodes, those will be the columns.
04:42So I'm not really going to look at how six is coming into one
04:46because I'm only interested right now in what one starts in terms of an edge.
04:53You know, what edges come out of one.
04:55So one, forget about the six and the two, those are incoming edges.
04:59I'm just going to look at the outgoing edges.
05:01So one goes out to three and four and five.
05:05So by default in our diagrams, at least at this point, we're going to say that self connections are not
05:11implied.
05:13Meaning by default, if I don't see an actual edge on the diagram going from one back into one,
05:19then I'm going to say one is not connected to itself.
05:22So I'm going to put a zero to say there's no connection.
05:27One going to the two, that's not happening because two is actually going into one.
05:33So I'm going to put another zero then there.
05:36One going to three, that is happening.
05:38So I'm going to put a one.
05:39So one does have an outbound connection or an edge to three.
05:42So I'm going to put a one in that row and column.
05:45One going to four, yes.
05:47So I'm going to put a one.
05:48One going to five, yes.
05:51So I'm going to put a one there.
05:53One going to six, no.
05:57So I'm going to put a zero there.
05:58I should have put, you know, edges that go back and forth to make this more interesting.
06:03But you can probably imagine.
06:05Well, I'll add that maybe later in this video.
06:08So one going to seven, nope.
06:11So I'm going to put a zero.
06:13So that's the first row.
06:14We represented all of the outbound edges from one to some other node.
06:19And we used a zero to say it doesn't exist and a one to say it does exist.
06:23So then we just move on to the two.
06:25So if I'm focusing on the two node, then I'm on the two row and its outgoing connections are going
06:31to be represented in the columns.
06:33So does two go to one?
06:35Yes.
06:35I'm going to put a one there.
06:36Does two go to itself?
06:39Self connections are not implied at this point.
06:41And then, hang on a second.
06:45Does two go to three?
06:47Nope.
06:48Because three goes into two and not the other way around.
06:51We'll add those other edges in a second.
06:54Does two go to four?
06:55Nope.
06:57Does two go to five?
07:00Nope.
07:01Does two go to six?
07:04I don't see that.
07:06So I'm going to say nope.
07:06Nope.
07:07And then does two go to seven?
07:09Yes.
07:10I'm going to put a one.
07:11So now we're done with the two.
07:13This is a directed graph by the way.
07:15So like I said about my previous videos, we will not see a mirror.
07:20At least we won't necessarily see a mirror.
07:21We might accidentally make a mirror depending on what the graph is, but we're not going to see a mirror.
07:26So we have to do this whole graph with no shortcuts.
07:29So the three, does it go out to the one?
07:32That's a no.
07:33Does it go out to the two?
07:36Where the heck is the three?
07:37Oh yeah, it goes out to the two.
07:41No implied self-connections.
07:43Three goes to the four?
07:45Nope.
07:47Three goes to the five?
07:49Yes.
07:51Three goes to the six?
07:54Nope.
07:56Nope.
07:56Three goes to the seven?
07:58Nope.
07:59Okay.
07:59So now we're done with the three.
08:02And then we'll say now does four go to the one?
08:05I'm looking at the four.
08:06Where the heck is the four?
08:06I'm losing the four.
08:07Oh, four doesn't go anywhere except for the seven.
08:09So I can actually just put like zeros in this whole thing, just to save a little time.
08:16Hmm.
08:19Oh God.
08:21Okay.
08:22There we go.
08:23But the four does go to the seven.
08:24So I'm going to put a one right there.
08:25Okay.
08:26So, uh, the five, um, it has outbound connections.
08:31I'm going to, I'm going to be cheap here.
08:32I'm going to be cheesy.
08:33The five goes to six and seven.
08:35So I'm just going to put zeros everywhere else.
08:37So, whoops.
08:40In fact, I probably could have just copied that whole row of zeros.
08:45And then just overwrote the last two, but I guess.
08:48So the five goes to the six.
08:50That's a yes.
08:51The five goes to the seven.
08:52That's a yes also.
08:54And then we're ready for the six.
08:55The six has three outbound connections.
08:58One, three, and seven.
09:00So I'm just going to, you know what?
09:02I'm just going to copy a whole row.
09:03I wish I had a whole row of zeros.
09:05And I'm going to maybe change that to a zero real fast.
09:09And then I'm going to say, all right, where does, where does six actually connect to?
09:12Let's change those zeros to ones.
09:14Six connects to the one and the three and the seven.
09:22Okay.
09:22So one goes to one, three goes to one, and seven goes to one.
09:29Okay.
09:30Then the seven has no outbound connections.
09:33So this is indeed a row of zeros.
09:36Maybe I could have done that one first.
09:37It would have been fun.
09:38Oh, well.
09:39Notice one more time that there's no mirror.
09:41So if we like, you know, if you trace your eyes along this identity line right here,
09:46and you were expecting to see a mirror, you would be sadly disappointed.
09:50Because what would actually happen is not a mirror.
09:54Let me do the highlighter here.
09:56And we'll say we have like an identity line that goes down the middle.
10:00And then I'll just try to highlight some stuff.
10:03Let's see the three, four, five, six over here on row one and those columns.
10:08Let's go now to column one and notice how it's like not the same three, four, five, six.
10:16So that's not a mirror because those numbers don't match.
10:20So there's no mirror in directed graphs in terms of the matrix.
10:24Anyway, let's see.
10:27I'm going to get rid of these little pound signs, these hashtags.
10:32The next question is, let's do a self connect.
10:35How do we add an edge?
10:36Like if I wanted to add an edge from a, you know, one to seven, for example, actually, let
10:43me duplicate this first.
10:44And then we'll work on it.
10:45If I just wanted to add a brand new edge going from one to seven, then I just have to
10:52make sure that I look at the row one and then look at the seven column and then just change
10:57that value to a one to say, did I do that?
11:01Yeah.
11:02To say that the edge now exists, right?
11:04So that's pretty easy to add a brand new edge.
11:06Let's look at self connects.
11:08Now, just in case, if I wanted to say that four connects to itself, I have to do an arrow,
11:14by the way.
11:14Did I do an arrow on the last one?
11:17Yeah.
11:18Okay.
11:19Four, we're saying now it connects to four.
11:21So before we assumed that there were no self connections by default.
11:25So all the nodes had no self connections, but the four, we just added a self connection.
11:29So that means right here, that zero is going to change to a one.
11:33Pretty easy and fast to add an edge.
11:36And by the way, how fast was it to just access a cell and modify a value?
11:40It's constant time.
11:42Again, big O is going to happen in other videos, but this is lightning fast for adding
11:47and removing edges.
11:49Okay.
11:49So then the other thing is, let me see, can I do, oh, I got to get rid of that.
11:56How do we remove an edge?
11:57Oh, bro.
11:59Bro.
12:01What's happening here?
12:02Can I just select that?
12:04Oh, how do we remove an edge?
12:07Uh, we talked about this in other videos, uh, for our adjacency matrix, but it's pretty
12:11easy.
12:11We just say, all right, suppose I just want to kill this edge going from three to two.
12:15So now there's no connection, no edge going from three to two.
12:19Um, well, I just have to go find the appropriate part of the matrix and that's it.
12:24So row three, cause three was the start node or the source node, row three, and then two
12:29is the destination node.
12:30So I'm just going to like overwrite that with a zero.
12:33And now we have effectively removed an edge.
12:35Remember the computer doesn't actually see this diagram that you're looking at on the
12:40left.
12:40The computer just has the matrix.
12:42The computer doesn't really even need to know that the, that the three is on top visually.
12:46It just needs to know what the three is actually connected to.
12:49At least most applications of graphs, there are some where it's more visual.
12:54And so there needs to be like some coordinates, but just the easiest and most simple way right
12:58here with an adjacency matrix doesn't need that.
13:01Okay.
13:02So then the next thing I want to do is, um, I want to add edges that kind of like
13:08point
13:08towards, you know, two nodes that sort of point towards each other.
13:12Like, you know, opposing, this is going to work.
13:15Yeah.
13:16Opposing, uh, edges.
13:19That's not a technical term.
13:20So suppose for the sake of argument that you're looking at the three and you say, well,
13:23the three can go outbound to the two, but can the two go outbound to the three?
13:28Yeah, totally.
13:29I'm going to draw an edge to represent that.
13:31That's the case.
13:33Okay.
13:33So I now have two edges, each going in a different direction between the three
13:37and the two.
13:37And by the way, in your mind, you might be thinking, Hey, isn't that what, what undirected
13:42graphs are doing?
13:42Yeah.
13:42Basically you have just an edge that goes in both directions.
13:45Here we have to draw two separate edges.
13:48Then we just have to update the matrix to match.
13:51So I added an edge going from three to two.
13:53So I'm going to go row three and then column two.
13:56And, um, oh, sorry, sorry.
13:59Row three was the source originally, which worked from three to two.
14:02That's why, that's why there's a one there.
14:04But now I just added an edge from two to three.
14:06So we look at row two and then column three.
14:09And then I update that, uh, to match.
14:12So that zero became a one and it did become a little bit more like a mirror.
14:16If we went ahead and added these like, you know, opposing edges on every single pair of
14:21nodes, uh, then the matrix would start to look like a mirror.
14:26Anyways, what else can I talk about?
14:28We're at about 16 minutes and I've lost my mouse cursor.
14:32What the heck?
14:33Oh, there we go.
14:34I need, I need accessibility controls.
14:37You know, it's true.
14:38Actually, I really need glasses.
14:39I've needed glasses for a couple of years, maybe like five years.
14:43And for some reason, I just can't get myself to go.
14:46So what's happening now is when people show me memes on their phones, my face goes, it goes
14:51backwards like this.
14:52It's like a, it's like a repellent for my face.
14:55If you show me a meme, I'm like, not, not fun to live that way.
15:01So I got to get glasses.
15:02Should I get a chain?
15:03I want a gold chain that's like studded and like blinged out.
15:06And then like, I have the glasses here only when I need to read.
15:08And then it hangs the rest of the time and it maybe it plays music or something.
15:12I don't know.
15:14I don't think I'm going to go that far.
15:16So when we did undirected, unweighted, I'm just trying to make sure that I didn't forget
15:19anything.
15:20There's no cheesy broccoli in this video directed and unweighted.
15:24Yeah, I guess that was it.
15:26Okay.
15:26So we're at the end of this particular video.
15:28I'm going to do one more before we shift topics.
15:31The next one is going to be how to represent a directed and weighted graph inside the machine.
15:38Using an adjacency matrix.
15:40Okay.
15:41Thank you for watching this video.
15:42I hope you learned a little bit of stuff and had a little bit of fun.
15:45I'll see you soon.
15:47I'm going to go have a burrito.
15:50No, I'm not.
15:50I'm just going to keep recording.
15:53Hey everybody.
15:54Thanks for watching this video again from the bottom of my heart.
15:57I really appreciate it.
15:58I do hope you did learn something and have some fun.
16:00If you could do me a please, a small little favor.
16:03Could you please subscribe and follow this channel or these videos or whatever it is you
16:09do on the current social media website that you're looking at right now.
16:12It would really mean the world to me and it'll help make more videos and grow this community.
16:17So we'll be able to do more videos, longer videos, better videos, or just I'll be able to keep making
16:22videos in general.
16:23So please do me a kindness and subscribe.
16:27You know sometimes I'm sleeping in the middle of the night and I just wake up because I know somebody
16:31subscribed or followed.
16:32It just wakes me up and I get filled with joy.
16:34That's exactly what happens every single time.
16:37So you could do it as a nice favor to me or you could you could troll me if you
16:40want to just wake me up in the middle of the night.
16:41Just subscribe and then I'll just wake up.
16:44I promise that's what will happen.
16:47Also if you look at the middle of the screen right now you should see a QR code which you
16:51can scan in order to go to the website which I think is also named somewhere at the bottom of
16:55this video.
16:56And it'll take you to my main website where you can just kind of like see all the videos I
17:00published and the services and tutorials and things that I offer and all that good stuff.
17:07And if you have a suggestion for clarifications or errata or just future videos that you want to see please
17:14leave a comment.
17:15Or if you just want to say hey what's up what's going on you know just send me a comment
17:19whatever I also wake up for those in the middle of the night.
17:21I get I wake up in a cold sweat and I'm like this it would really it really mean the
17:27world to me I would really appreciate it.
17:28So again thank you so much for watching this video and enjoy the cool music as I fade into the
17:36darkness which is coming for us all.
17:39happy now.
18:06So thank you so much.
