Directed Graphs

[00:00:00]
>> Bianca Gandolfo: Let's talk about different types of graphs. So we've been dealing with undirected graphs which means that you can go from E to A, A to E no problem. But there are such thing as a directed graph, so a directed graph is what it sounds like. It has a direction associated with an edge.

[00:00:24]
So we've been talking a lot about adding values to the vertices. We didn't talk much about adding data on the edges which we can totally do, right? So we can give a direction. So in this graph here, we can only travel from E to A, right? And A, we can't travel back to E because it's directed the wrong way.

[00:00:47]
And so this is like maps out to real life things like one way roads and etc., anything that has a direction. And then we have the concept of weighted or unweighted edges. So back to this map example, that would be, maybe the distance from E to A is seven miles.

[00:01:13]
And that's a really long one-way street, that sounds terrible. And then we have unweighted which we have been dealing with. Self loops, we talked a little bit about self loops or the loop points to itself, where the edge points to its own self. The node's edge points to itself.

[00:01:38]
Then we have sparse and dense types of graphs. So most graphs are sparse, which means that there are more vertices than edges. Dense means that there's a lot of edges, yeah, and then there's cyclic and acyclic. So are there cycles, are there no cycles? So can you go in a circle or not?

[00:02:04]
Those are some properties of graphs. And based on these properties, it changes how you deal with a problem, yeah? And I wanted to just like, bring up the adjacency matrix and the adjacency list, and talk about these properties, and how they're gonna change the way that this data structure looks.

[00:02:26]
Does that sound good? So for a directed graph, how would that change this adjacency matrix? What do you think, Michael?
>> Speaker 2: A direct it.
>> Bianca Gandolfo: Yeah, so it has a direction. We have adjacency matrix from earlier.
>> Speaker 2: [INAUDIBLE] more logic, cuz you have to know the constraints in which way we go, just thinking out loud.

[00:02:55]
>> Bianca Gandolfo: Yeah, how could you represent that? So in this case, when we represent an edge, so 2 is connected to 1, so we have a 1 here and we have a 1 here. How could we just say only 1 is connected to 2?
>> Speaker 2: I think you would have to add more metadata on that.

[00:03:15]
>> Bianca Gandolfo: Actually you don't, all you have to do is only put one 1. So if we wanna say that two is connected to 1, but 1 is not connected to 2, we would remove the edge from 1. So this would just be a 0. So we would never be able to travel from 1 to 2, but 2, we could still travel back to 1 with this edge.

[00:03:44]
Does everyone see that? Awesome.
>> Bianca Gandolfo: What about adjacency list? How about Joe?
>> Speaker 3: I'm not quite sure.
>> Bianca Gandolfo: Not sure? That's fair. How do we represent an edge in an adjacency list before this? Do you remember?
>> Bianca Gandolfo: No? That's okay. What about Michael number two, do you remember?

[00:04:11]
>> Speaker 4: Yeah, it's listed as the 2 under the 1 property.
>> Bianca Gandolfo: Yeah.
>> Speaker 4: So you would remove that and leave it and the 2 property.
>> Bianca Gandolfo: Yeah, so here, this says 1 is connected 2. This says 2 is connected to 1, right? So that is not directed, I mean you can have interdirected graph to be clear.

[00:04:37]
You can have like a two way street. But in this case, we will only have one direction, you would remove one. Cool, what about weighted?
>> Bianca Gandolfo: How will we represent a weighted edge and an adjacency matrix? Eric, do you have a thought?
>> Speaker 5: Say the distance between one and two, it doesn't make sense, I'm not sure.

[00:05:08]
>> Bianca Gandolfo: Okay, that's fine.
>> Speaker 5: May be in the matrix you could use numbers more higher than one.
>> Bianca Gandolfo: Yeah.
>> Speaker 5: So that it starts at seven. You could a seven, it's [CROSSTALK]
>> Bianca Gandolfo: Sure, and then to mark it as empty, you can put a null in there or something.

[00:05:23]
Something to differentiate so you don't have weird edge cases. So what if the distance is zero and then you think you don't have an edge, for sure. Yeah, so Sony do you know or Sony, do you know how we might be able to represent a weighted edge in our agency list?

[00:05:47]
>> Speaker 6: Or we can save them as an object with key and weight attached to them.
>> Bianca Gandolfo: Yeah, exactly. All right, so now, let's talk about how we might represent self loops in the adjacency matrix.
>> Speaker 7: Instead of having a 0 at the 1, 1 position, you would have a 1, or if it ended up being weighted somehow, then you'd use whatever value that was.

[00:06:17]
>> Bianca Gandolfo: Yeah, fancy, a weighted self loop, I like it, very cool. All right, Karim, self loop and the adjacency list, do you have a thought you like?
>> Speaker 8: I guess you'd stick the number on the left in the array on the right.
>> Bianca Gandolfo: Yeah, you said add itself to its own adjacency list, yep.

[00:06:40]
Sparse and dense isn't really something that we represent. It's just sort of a characteristic, right? So like a dense adjacency matrix will have like a lot of ones, right? And a dense adjacency list would have a lot of references here. And then cyclic or acyclic, that's something that you would have to detect through traversing.

[00:07:10]
>> Speaker 2: If it's acyclic, is it pretty much a three?
>> Bianca Gandolfo: Yeah, so a three is a,
>> Bianca Gandolfo: It doesn't have cycles.
>> Bianca Gandolfo: Yeah, there's something else, actually. There's a saying that I'm blanking on. But it's similar, so there's like directed acyclic graphs sorta like a really particular type of graph that you find in data structure algorithms classes.

[00:07:42]
But a directed acyclic graph isn't always a three.
>> Speaker 2: [INAUDIBLE] direction.
>> Bianca Gandolfo: What's that?
>> Speaker 2: Cuz of the direction?
>> Bianca Gandolfo: Because of the direction? I think it's because, what is the reason?
>> Speaker 6: A child has a unique parent of that one, right?
>> Bianca Gandolfo: Yeah.
>> Speaker 6: Yeah.
>> Bianca Gandolfo: Yeah.