Graph Solution

[00:00:00]
>> Bianca Gandolfo: So let's talk about our graph really quick. So let's just say the constant adjacency list equals new graph, right?
>> Bianca Gandolfo: Cool. So when we create a new graph, we need to instantiate some data on it, right. We have may be a value, right. Maybe that value is one and then some way to represent relationships.

[00:00:38]
Yeah.
>> Bianca Gandolfo: So let's take a look. So we have all the notes and we can actually just kind of do this for now. So we have our adjacency list and that's gonna be our empty graph. So right now if we cancelled out log this, it's just gonna be some empty graph, right?

[00:01:08]
Now we're gonna need to be able to add nodes to our graph, right. And that's what I was talking about when I was saying we need to have something with a value, right? Something like this. So how might we do that? So we can say adjList.addNode here. We're gonna pass on a node.

[00:01:36]
Well, let's our, let's call it node one and it has a value of one. Reasonable, cool. So now, at this point, we're just having an empty object. At this point we wanna have an empty object, that contains our rate our node somehow. Fair, so one way we could do this is we could have a key of the value.

[00:02:16]
So we could do something like node1.value
>> Bianca Gandolfo: And have that be the key in our object.
>> Bianca Gandolfo: And map that to our empty list of edges, right?
>> Bianca Gandolfo: That seem reasonable? So we could do something like that. But then we need to also make sure that we keep a reference of all of the nodes and how am I gonna do that?

[00:02:51]
Let me think. How do I wanna do that in this case? So.
>> Bianca Gandolfo: Yeah, I think I'll just make another thing similarly.
>> Bianca Gandolfo: Actually no, we'll leave like this, this was fine. We'll have a node.value, we could can store the node here in line.
>> Bianca Gandolfo: Right, node. Node is node.

[00:03:27]
And then we have edges can be something like this. It's the only way to do it. Cool, so if we wanted to do that. How,
>> Bianca Gandolfo: Might we define this?
>> Bianca Gandolfo: All right, so we have this this is gonna refer, actually we say this.adjList and then we want to add the value.

[00:04:03]
So the adjList is an object. So we say node.value, right, because we wanna set this up. And then we're going to instantiate some object like this. So we have the node, node, node, and then the edges, right? Something like this, so that is adding, essentially we're just taking an object.

[00:04:32]
We're giving it a key and we're giving it a value.
>> Bianca Gandolfo: Seem fair? What happens if there's a node that has the same value?
>> Bianca Gandolfo: Yeah, what if I add node again and it has the same value but it's actually a different node?
>> Bianca Gandolfo: Could be problematic, we'd overwrite it.

[00:04:57]
So, just note, just note. All right, what's the next thing we need to do, addEdge, all right. And then we want to take v1, v2 these are vertices or we could call this node one, node two, it's all kind of the same. But we've been talking about node series.

[00:05:22]
We'll call them nodes and typo. Let's add our second node, right. So this is gonna be node two with value two adjacency add node two. So now,
>> Bianca Gandolfo: We have something that kind of looks like, this.
>> Bianca Gandolfo: Are you guys following so far. Any questions about what, what the heck I'm doing.

[00:05:59]
>> Bianca Gandolfo: Does everyone know what I'm doing? Yeah, everyone? Okay, so I'm just gonna say node here. And then we have these edges, right? Again, this could also be a linked list, but we're gonna simplify this.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: So now, we're gonna say adjList.addEdge.
>> Bianca Gandolfo: Node one and node two, again we define this here.

[00:06:42]
They're just objects nothing special.
>> Bianca Gandolfo: Okay, now we wanna connect them.
>> Bianca Gandolfo: Excuse me. Then we're going to need to go to our adjacency list. Find the first node, right? And then we need to go to the, so we find the first node. Then, we need to go to the edges, all right.

[00:07:17]
And then, we need to push, because this is an array, node two.
>> Bianca Gandolfo: And then, we need to do the same thing, but opposite.
>> Bianca Gandolfo: How you feel about that? Seems reasonable.
>> Bianca Gandolfo: All right, what's the next thing? We wanna remove a node. Also, another thing when you're interviewing to think about, and to ask your interviewers, what do they want you to return here?

[00:08:03]
If you add an edge, do they want you to return the last the second node, anything at all? Like, success or not success or whatever? You could think about that and ask. So we're gonna do adjacency list. So we're gonna get the node.value. All right, you could just straight up delete it.

[00:08:30]
>> Bianca Gandolfo: But, what?
>> Speaker 2: Those camera references, you have to delete the references to that.
>> Bianca Gandolfo: Yap, yap. Then, we need to loop through our adjacency list and remove it from the edges. Okay, let's do this. So, the we need to do something like. What's that?
>> Speaker 2: Would it be a foreign?

[00:09:00]
>> Bianca Gandolfo: Yeah.
>> Speaker 3: Do object.keys.
>> Bianca Gandolfo: What's that?
>> Speaker 3: You can do object.keys and loop all the keys and so.
>> Bianca Gandolfo: Yeah, like that let's do that. Little Object.keys is this. I'm sure there's a fancy way to do it now with ES6.
>> Bianca Gandolfo: So what this does is this creates an object, it turns this object into an array of the key values.

[00:09:29]
>> Bianca Gandolfo: Okay, so then we'll do keys.foreach, and then for each key, we are going to take in our adjList, and then we need to look up the key, right, so this is really. These are really are nodes, this is the current node, okay. So what this returns, so for the very first one we're getting an object like this, right?

[00:10:13]
So we need to get into those edges.
>> Bianca Gandolfo: Right, and then we had to do something like indexOf. Does this look familiar? We had to find it and then so indexOf the current node.
>> Bianca Gandolfo: Sorry we need to do of the node were searching for. So we’re looking, okay.

[00:10:43]
Does this node exist here? So we say if this is greater than negative one, so this returns negative one if it finds nothing. We need to delete it or this is really testing. I think it would be, let's do something like this.
>> Bianca Gandolfo: To the edges. So this would be edges.splice.

[00:11:39]
>> Bianca Gandolfo: Okay, so this is the indexOf the edge. So then we wanna splice, what is this? I think it's gonna be index, 1. Can someone double-check that for me?
>> Speaker 4: Yeah.
>> Bianca Gandolfo: Is that what it is.
>> Speaker 4: [COUGH] The index of the item you wanna get rid of, comma, how many items to get rid of.

[00:12:09]
>> Bianca Gandolfo: Okay, cool, thank you very much. And in that scenario, I would just straight up ask my interviewer and be like, I don't know which one this is exactly, I think it's this, it's not a big deal. Or maybe that's why I didn't get the job, okay
>> Speaker 5: If you don't shoot splice from beginning the array to the index.

[00:12:42]
You hold that part and then you concatenate with the rest of the array
>> Bianca Gandolfo: Yeah, probably.
>> Speaker 5: Or just the one index.
>> Bianca Gandolfo: Probably, whatever. Remove.
>> Speaker 5: Yeah, yeah
>> Bianca Gandolfo: Remove it, relined it up, yeah. Good point. How we feeling about graph as the day of structure.
>> Speaker 5: Complicated.

[00:13:05]
>> Bianca Gandolfo: Yeah.
>> Speaker 5: But it's.
>> Bianca Gandolfo: It's a little bit more than a tree, but really I mean in area tree, isn't, I wouldn't say is less complicated than a graph.
>> Speaker 6: Do graphs have any hierarchy like parent child relationship?
>> Bianca Gandolfo: No.
>> Speaker 6: On an equal footing.
>> Bianca Gandolfo: Yeah, I mean we definitely don't refer to them as parent child.

[00:13:35]
There also isn't a root node, right? A tree has root node whereas a graph is kind of like anything. So, yeah, it's not really hierarchical, it's kinda like mini to mini versus just leveling.
>> Speaker 2: However, the tree is a graph, it's just a type of graph. It's a graph with no cycles, that has a direction, yeah.