This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "Pseudocoding the addNode() Method" Lesson
[00:00:00]
>> Bianca Gandolfo: So let's pseudocode adding a node. What might a node look like, or a vertex?
>> off screen female: It's another row and column into our matrix.
>> Bianca Gandolfo: Mm-hm.
>> off screen male: It's one or the other-
>> off screen female: It's just a value. It's both, right?
>> off screen male: Well no, because the values are the edges, right?
[00:00:16]
>> off screen female: It's both of them.
>> off screen male: But one or the other, right? The combination of the two is an edge, right?
>> off screen male: The pairing of a column and a row is an edge, right?
>> Bianca Gandolfo: The pairing of a column and a row is an edge, yes. So here, 1 and 2, here's our edge.
[00:00:41]
>> off screen male: But just 1 or just 2 is a node?
>> off screen female: It's between the two.
>> Bianca Gandolfo: So you're asking, how do we represent this?
>> off screen female: Mm-hm.
>> Bianca Gandolfo: Yeah, we're gonna get there in a second.
>> off screen male: Okay, sorry.
>> Bianca Gandolfo: Actually, we can go there now. You wanna go there now?
[00:00:56] So that's the big question with the adjacency matrix is so, depending on the data that you're representing, how are we gonna store this and what value does it hold? I usually recommend that we use a hashing algorithm or a hash table to store these and link it up to a index, right?
[00:01:18] So we want whatever our value is. Or whatever it is, right, some object maybe, to hash. Actually, it's probably gonna be a string on the object. We want it to hash into some index that's between maybe some range, maybe we have an expected range the size of our graph.
[00:01:39] So then, this here is only representing the relationships, but perhaps for storing the actual value in an auxiliary data structure like a hash table, which we'll talk about tomorrow. But essentially a hash table is just an object, like a-
>> off screen female: Like a reference to what is where.
>> Bianca Gandolfo: Yeah, so for example, we have an object with the key 1 and the value would be whatever our value is, whatever this node actually is representing.
[00:02:14] If it's a city name, it might be St. Paul, Minnesota, or whatever. But we're not gonna store it in an index, right? And our adjacency matrix expects, because they're arrays, expects a numeric index that's a positive integer. So yeah, don't worry, I'm not going to ask you to do that.
[00:02:48]
>> Bianca Gandolfo: Okay, so we're just gonna assume all of our nodes have a value that's an integer that's less than ten. Just to make our life simple.
>> Bianca Gandolfo: So, what did we say, how do we add it?
>> off screen male: This is where I was confused. Like, do you add it to both, does it become a column and a row?
[00:03:15]
>> Bianca Gandolfo: Yeah.
>> off screen female: How do you decide where to put it?
>> off screen male: Before that, why do we initialize in the constructor and add up on that?
>> Bianca Gandolfo: Why do we initialize the constructor and what?
>> off screen male: To add inward, we initialize a value in the constructor?
>> Bianca Gandolfo: Yeah, so you're saying to add a note that we should initialize the constructor?
[00:03:46]
>> off screen male: As initializing matrix, we intitialize a value in the constructor.
>> Bianca Gandolfo: Mm-hm, yeah, so you're saying instead of adding the column and a row, when we add a node, maybe we just initialize a matrix that's predefined and we'll just pop it in there.
>> off screen male: Is there one value or two value?
[00:04:08] At the beginning, we initialize and then add the node on that one?
>> Bianca Gandolfo: So the question is when we initialize our graph, are we initializing a value with it? Yeah, yeah, probably, right? You'll probably initialize it with at least one value.
>> Bianca Gandolfo: I can buy that. It makes sense to me.
[00:04:35]
>> Bianca Gandolfo: Cool, so we have a question here. The question is, how do we add the node?
>> Bianca Gandolfo: What were our two things that we were gonna say? Do we add,
>> Bianca Gandolfo: To an already existing matrix or do we add a column every time, column row every time.
>> Bianca Gandolfo: What do you think is gonna be the easiest?
[00:05:21] And again, let's just assume,
>> Bianca Gandolfo: Assume node is a positive integer between 1 and 10, or 0 and 10.
>> off screen male: So I mean, if the value was already represented as a column row, we wouldn't add it again, right. Cuz that would mean that we would increase the,
>> off screen male: Well, in the ones we saw already, there weren't repeating nodes so I would think we would not add another one if we try to add, right?
[00:06:12]
>> Bianca Gandolfo: So you're saying that-
>> off screen male: Like if we already had zero, one, two, three, four as both rows and columns, and then we went to add two.
>> Bianca Gandolfo: Yeah, so you're saying maybe we initialize the entire matrix at the beginning. That seems like it's easier than starting out with maybe a matrix that's one by one.
[00:06:36]
>> off screen male: Right, I mean, I guess if we weren't expecting to have all the values we could just do a check. I don't know. I guess it sort of depends on what the purpose of the matrix is.
>> Bianca Gandolfo: Yeah, exactly, so the thing about this matrix is that, since we know our values are gonna be between 0 and 10, we can also use these numbers, not only to represent the value, but to also represent the order in which they are added.
[00:07:07] So depending on what you're doing, right? So if it's the order in which they're added, so the first element, whatever value it may have, right, we can save the value somewhere else with the same key.
>> Bianca Gandolfo: We can keep adding columns and rows every time. However, what was the other case that I just lost from my head?
[00:07:34] The second case? Amnesia. The first case was these numbers represent the order in which we add a node. Second case is these actually represent the value.
>> Bianca Gandolfo: Does that make sense? So for the case where we are using these numbers to represent the value that we're adding, right, so what if the first thing we add is 5?
[00:08:06] And that's an index, right? If you look at our adjacency matrix, these are arrays. So 5 is gonna be here. And we need to have an array of 1, 2, 3, 4, 5, well, 5 by 5. [LAUGH] I can count. Initialized at that point. So again, it comes down to what specific thing are you doing.
[00:08:36]
>> Bianca Gandolfo: Cool, what else, what else do I wanna put in your brain about this?
>> Bianca Gandolfo: So is it the value?
>> Bianca Gandolfo: Is it the order?
>> Bianca Gandolfo: So much power, so many options, so many questions to answer.