Description

Throughout our exploration of graphs, we’ve focused mostly on representing graphs, and how to search through them. We also learned about edges, the elements that connect the nodes in a graph. In this episode, we look at the different classifications of edges and how, in the context of a graph, edges can be more than just “directed” or “undirected”.

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Spinning Around In Cycles With Directed Acyclic Graphs from her basecs blog series.

Transcript

[00:00:01] SY: Welcome to the Base.cs Podcast where we explore the basics of computer science concepts. I’m your host Saron, Founder of CodeNewbie.

[00:00:09] VJ: And I’m Vaidehi Joshi, Author and Developer.

[00:00:12] SY: And she is the brilliant mind behind the Base.cs Blog Series. Today, we’re talking about…

[00:00:16] VJ: Edge classification.

[00:00:18] SY: This season of the Base.cs Podcast is brought to you by Educative. Educative has a ton of online coding courses, including how to become a machine-learning engineer and a practical guide to Kubernetes. The comprehensive and interactive text-based courses give you in demand tech skills. And since it’s text-based, there’s no scrubbing back and forth video to find the content you need. So learn better and faster with Educative and get a 20% site-wide discount by going to educative.io/basecs.

[00:00:55] Okay. So this topic is very interesting because I didn’t think that edges needed to be classified. So we’re going to be talking about different types of edges. Is that right?

[00:01:05] VJ: That’s right. And I mean we’ve been talking about graphs and edges for a while now and like we haven’t really tried to classify them since I don’t even know how many seasons ago when we first learned about graphs.

[00:01:18] SY: That’s true.

[00:01:18] VJ: But I think it’s important for us to talk about some special ways of classifying edges that we haven’t talked about yet because we’re about to enter some more advanced data structures. And once we enter into like learning about these more advanced data structures, it’s important to have names to talk about the structures.

[00:01:38] SY: Okay. So why do we care about the kinds of edges? What does that tell us about these graphs? Why does that influence what we do with these fancier algorithms?

[00:01:50] VJ: So on a very basic level, knowing what kinds of edges a graph has helps us classify the graph and we’ve seen this to the edges that we’ve learned already, so specifically directed and undirected edges. Directed edge is one where there’s only like one way to go from one node to another. So if two nodes have a directed edge between them, then you can only go from one node to the other, depending on how it’s directed, like what’s the flow. An undirected edge doesn’t have that constraint. You can basically go from one node to the other and back again. So there’s a bi-directional flow. And the reason that we classify edges is we can help identify a graph based on its edges. So with a graph that has directed edges, we can say we have a directed graph, versus a graph that has undirected edges, we can say we have an undirected graph. And like just based on that description alone, you can kind of visualize how the nodes work together. So that’s like at a very basic level. But then there are other kinds of graphs that we haven’t even learned yet that are based on some specific types of edges existing. And so in order for us to learn about those types of graphs, we have to know what those types of edges are.

[00:03:12] SY: Okay. So let’s dig in. What are those types of edges?

[00:03:15] VJ: We’ve talked about directed and undirected edges, but there are actually two main categories of edges that we haven’t even touched yet, but we’ve interestingly sort of been using them this whole time, specifically you’ll remember we did like depth-first search through a graph and breadth-first search. And all the time we were talking about like, “Oh, I have to take a path down the graph and traverse through it and sometimes I have to backtrack and sometimes I need to go deep into it depending on what the algorithm is.” So. when we are talking about taking paths down a graph, we are talking about something called tree edges. So that’s one category of edges and then there are also non-tree edges and we’ve also been working with those as well and we’re going to learn some new ones today. But those are the two main categories that I sort of want to surface even though when we kind of describe them, I think you’re going to be like, “We already have been using these.”

[00:04:20] SY: Yeah. Okay. So let’s dig into a tree edge. How might I identify a tree edge?

[00:04:25] VJ: A Tree edge is basically any edge that is part of the path that we take when we are implementing a graph traversal algorithm.

[00:04:37] SY: Okay.

[00:04:38] VJ: Another way of thinking about it is that it’s an edge that allows us to visit a new vertex when we traverse through our structure. We learned about depth-first search. We started at one node. We went to another node. And from that node, we went to another node. As we traverse through that structure, each edge that we sort of pass through, that’s a tree edge, which is pretty simple actually if you think about it. It’s like any edge you walked on.

[00:05:04] SY: Okay. So does that mean there are edges that we can’t traverse?

[00:05:09] VJ: Well, it’s not so much that you can’t traverse them, it’s that they aren’t part of the path that you’re taking in that moment. I think when we think about tree edges, we really are thinking about the path that we take as we traverse through a graph. So now when we were like doing examples, when we’re talking about like depth-first search or breadth-first search, we’ve often said like, “Oh, I’ll go from Node A to Node B, and then from Node B to Node F, and Node F to Node G,” or whatever. So we’re creating like a line, like a little path through like a maze in our graph. So that path that we take those are the tree edges and it doesn’t mean that there aren’t other paths to take later. It’s just that the edges that we walk in our algorithm as we traverse it, those are the ones that were sort of traversing in that moment. Those are the ones that actually if you rearrange them, they sort of form like a chain or a line of the path you’re taking and you can basically think about it as we are restructuring the nodes and the edges to form a kind of tree but it’s sort of just like a little chain.

[00:06:18] SY: Okay. So it’s not that an edge is innately a tree edge or not. It’s just like any edge can technically be a tree edge if it’s on the path that we’re taking.

[00:06:28] VJ: Exactly. Yeah. Yeah.

[00:06:30] SY: Okay.

[00:06:31] VJ: The non-tree edges are interesting because it doesn’t mean you can’t traverse them. It just means like given the path we’re taking now, there could be other edges but they’re not the ones we’re walking on. So those are non-tree edges.

[00:06:43] SY: Right. Okay, cool. So now let’s dig into the non-tree edges because I feel like you can have almost more non tree edges than tree edges, right, especially if your graph is big enough because if you’re only taking one path and everything else is a non-tree edge.

[00:06:58] VJ: Exactly. Yeah. And in fact, there are three different variations of non-tree edges. The first one is a forward edge. So forward edge is one where you basically can move forward through the graph where, say, we start at a node X and node X can connect to either Y or Z. 

[00:07:20] SY: Okay.

[00:07:20] VJ: So let’s say that we go from X to Y, on forward edge would be one that goes from X to Z because it does allow us to move forward but it’s just not the path we’re taking. So it’s a potential path that we could take through the graph later in the future and it will help move us forward through the structure. But if we’re taking a different path, then that means the forward edge is not part of the tree that we’re walking, the path that we’re walking. So it’s a forward edge. It’s a non-tree edge.

[00:07:48] SY: Interesting. Okay. So if it’s a non-tree edge, then how would we move forward if it’s not on our path?

[00:08:00] VJ: Well, we might come back up. For example, if we’re doing depth-first search, we might pop off the nodes we visit, come back up, all the way up to our starting node, and then we’ll want to find a new path and in that situation, now the forward edge is actually about to be on the path we take and now it’s actually a tree edge. It’s just sort of like…

[00:08:19] SY: Oh, so I can switch between edges.

[00:08:21] VJ: Yeah. Yeah. It’s just like potential ways to move forward even though it’s not the one you’re taking right now.

[00:08:26] SY: So a forward edge, can you only have a forward edge if you have a directed edge? Are those the same thing or are they different or how do those relate?

[00:08:40] VJ: This is a good question. So you can only have forward edges when you have a directed graph because directed graphs have like a directional flow in their edges, right? Each of their edges is like, “I can only move from node X to Y. I can’t move back from Y to X.” So that means I can only move forward. That’s the only way for me to go. So like that is the only way to have a forward edge. If you can move both ways, then you’re not really moving just forward, you’re moving potentially backwards or you’re just moving some direction through the graph. There actually even isn’t a sense of forward because there is no direction in the edge, right?

[00:09:22] SY: Right. Okay. So a forward edge can only apply if that edge is also directed. You can’t have an undirected forward edge. That wouldn’t make any sense.

[00:09:31] VJ: Exactly.

[00:09:32] SY: Okay. Good. Good. Good. Good. Okay. Next we have what?

[00:09:35] SY: Next we have backward edges. Makes sense, right? Because we have forward edges, now we have backward edges. And a backward edge basically connects us back up to one of the ancestors in a path. So what that means is if you had a node that connected to a child and that child connected to another child and that child connected all the way back up to the original node, now you have a way of getting from one node back up to one of its ancestors, and that’s a backward edge. You can basically connect a node in a graph back up to one of its ancestors.

[00:10:20] SY: So same deal with the forward edge though, right? Like you can’t have a backward edge that is also undirected?

[00:10:26] VJ: No, you actually can. In an undirected graph, you can have back edges because you can have an edge that takes you back up the chain in a graph because there’s bi-directional flow. So there’s nothing saying you can only move one direction. You can move back up. Especially if you have like a chain of nodes and then one of the nodes connects back up to generations, that’s still a backward edge, right? Because you’re going back up in the chain of ancestors. If there’s an edge connecting a child back up to its great, great grandparent, you have a backward edge. You’re able to connect back up to an ancestral node from one of its children.

[00:11:05] SY: Okay. So if I have a graph where A has child B has child C has child E, but then E has an edge going back all the way up to A. Is that a backward edge?

[00:11:19] VJ: That is a backward edge you basically kind of have like this interesting circle cycle loop thing that can happen in a directed or undirected graph and it can take you all the way back up to one of the places you’ve came from.

[00:11:35] SY: And it’s interesting because we’re talking about graphs not trees so I can start from anywhere on my graph, right? Like I said, it was A to B to C to E, but I could start right in the middle and say C to D to E to A to B connecting back up to C, right?

[00:11:51] VJ: Yeah.

[00:11:51] SY: Right? Like I can kind of start wherever. And depending on where I start, different edges can be backward edges.

[00:11:57] VJ: Yeah. And depending on what your graph looks like, like if they’re directed or undirected, you could end up taking a different path entirely.

[00:12:04] SY: Yeah. Cool. All right. And you said there are three variations. So we did forward, backward edge. What is the third one?

[00:12:11] VJ: The third one is a little funny. It’s called the cross edge and what that means is we have this graph and I keep saying like, “Oh, we’re like traversing through it.” Graphs aren’t trees. They’re like looser versions of trees. They don’t have to have a root node and things can sort of just be connected to each other willy-nilly but often you can sort of rearrange them so that they’re sort of like subtrees within them. And what that means is like if you had a path through the graph and then another path sort of intersected with it where you could take two very different paths and then sometimes they merge together, like you basically have like a convergence of paths. So that’s sort of like subtrees. If you imagine that a chain of nodes in a graph is a tree, you can sort of have two parallel chains. In other words, two parallel paths that may sometimes intersect with each other.

[00:13:07] SY: Okay. So for cross edge, maybe we can do an example of cross edge. What does a cross edge actually look like?

[00:13:14] VJ: Let’s like do like a graph that has maybe four nodes in it or five nodes. I’ve got five nodes in it. It has the Node V that points to the Node Y that points to the Node X. So it’s just sort of like a line right now, a little chain, but then let’s spice things up and say that there’s also a Node W and W also is connected to the Node Y, which we’ll remember V is connected to Y and W is connected to Y. And this is a directed graph, by the way. And W also has its own child, Z, and that’s not connected to anything. That’s just a leaf on its own.

[00:13:58] SY: So basically V and W made a baby, Y, but then W has got its own baby on the side.

[00:14:05] VJ: Yeah. And then I guess Y also has its own baby, X.

[00:14:08] SY: Y also has its own baby, X. Okay. Lots of babies. Cool.

[00:14:11] VJ: So in this example, we sort of have two paths you could take. You could go from W to Z and then you could go from W to Y to X.

[00:14:21] SY: Yeah.

[00:14:22] VJ: But then, actually, if we think about it, it’s not two paths. There’s three paths because you could also go from W to Y to X, which is that intersection. It’s sort of like you have this one chain V, Y, X. You have another chain., W, Z, and then you have an edge connecting them and that’s your cross edge. It’s the edge between W and Y. And the reason that it’s a cross edge is because it’s connecting two subtrees of this entire graph together and these two subtrees don’t share an ancestor, right? Because we’re talking about graphs not trees.

[00:14:57] SY: Right.

[00:14:58] VJ: So there’s no main mama node that’s like owning all these sub trees, but they’re sort of like two sub trees on their own and they’re connected. So they’re kind of like sibling subtrees.

[00:15:10] SY: Okay. I get that. So W, Z are doing their own thing. V, Y, X are doing their own thing, but they’re connected, these two little sub trees are connected via W also being the parent of Y. So that W, Y is a cross edge.

[00:15:26] VJ: Exactly. And cross edges, also, they only exist in directed graphs and it’s interesting because undirected graphs can only have two of these edges that we’ve talked about. They can only have tree edges or they can have backward edges. And if you think about it in an undirected graph, you are always going to be either going one direction or the other. So you’re either going to be going through the graph by taking a path or you’re going back up because it’s undirected. There’s no such thing really as a forward edge and there’s no such thing as a cross edge because you can always go to both directions.

[00:16:12] SY: Okay. So we talked about some restrictions with undirected graphs. Do we have any restrictions for directed graphs of what type of edges they can have?

[00:16:20] VJ: So in a directed graph, you can have tree edges, you can have backward edges, forward edges, and cross edges. So basically the answer is you can find all four of them.

[00:16:31] SY: You can do whatever you want. Okay. Great.

[00:16:34] VJ: There’s one thing we haven’t talked about yet with backward edges that I want to point out because the new thing we’ve really talked about in this episode is that you can have different types of edges, but we’ve seen forward edges and cross edges before. Backward edges are sort of a little new. And the interesting thing about backward edges is that not only can a backward edge connect to somewhere up in the tree, it doesn’t have to just connect back up to an ancestor, it can also connect back up to itself, which is interesting because if an edge takes you back to somewhere where you came from in a graph, then an edge can take you back to where you are right now.

[00:17:18] SY: Why do I need to go back to where I am? I’m already there.

[00:17:22] VJ: Well, it’s interesting because backward edges are, they are used to sort of create a self-loop.

[00:17:30] SY: Okay.

[00:17:30] VJ: So they allow us to not just connect a node back to its ancestor, they also like let you connect a node back to itself, which can be useful if you want to say like the only place to go from here is here, like you can’t go anywhere else or I want to return back to this place. It’s a little vague right now because our nodes don’t do anything interesting, but graphs can sometimes be used to represent things like state machines. We can use graphs to represent the flow of behavior. And sometimes the way that things flow is that you want to go somewhere but you end up exactly where you are for some reason. And a backward Edge, that is one that connects a node back to itself, creates a self-loop and that’s how you can describe it and there are some graphs that have backward edges inside of them and they allow you to sort of like create a circle as we sort of alluded to in this episode and that will be really interesting to play with down the road.

[00:18:31] SY: So it’s not like getting stuck in the loop where you want to escape, it’s like this is a good loop.

[00:18:37] VJ: Well, I don’t know if I can bring myself to say that a loop is ever good, but yeah. But it’s a thing you can do.

[00:18:46] SY: Okay. And that’s the end of today’s show. If you liked what you heard, please leave us a review and make sure to check out Vaidehi’s blog post. Link to that is in your show notes. I also want to give a huge shout-out to Educative, the text-based online coding course platform. My producer and I got a chance to give it a try. I took “become a front-end engineer”. And Levi, what did you take?

[00:19:09] LS: I took “Learn Python from scratch”.

[00:19:12] SY: And what do you think?

[00:19:13] LS: I thought it was really great. So I’ve been learning Python a little bit and this sort of like…

[00:19:19] SY: Because I’m making you.

[00:19:20] LS: Because you’re making me. True. You’re not making me learn Python specifically.

[00:19:23] SY: That’s true.

[00:19:24] LS: But it is what I chose. So I was a little bit familiar, but I found that these courses, they’re laid out in a really intuitive way, there’s like the sections that lead seamlessly one into the other, the Python one goes from data types and variables, to conditional statements, functions, loops, and then each section has quiz, to make sure that you’re not just blasting through and like the information is going one way and not the other.

[00:19:53] SY: I love the quizzes.

[00:19:55] LS: Yeah. It really called me out on my BS.

[00:19:56] SY: Yes.

[00:19:58] LS: I was like, “Yeah, yeah, I get it. I get it. I get it.” And then I took the quiz and they’re like, “You don’t get it.” And I was like, Aha!”

[00:20:05] SY: You got me.

[00:20:05] LS: You got me. And then throughout all of these different sorts of sections, you can code within the service itself. So you don’t need an external coding thing. I should know what that’s called. Do you know what that’s called?

[00:20:21] SY: I’m not going to tell you. I’m not going to give you -- it’s an IDE.

[00:20:23] LS: No. Yes. That’s it, an IDE. Did you know I’m a producer for a coding podcast?

[00:20:30] SY: A technical podcast.

[00:20:31] LS: Yeah.

[00:20:31] SY: Two actually, two technical podcasts.

[00:20:33] LS: That’s true.

[00:20:34] SY: So if you are interested in learning how to code, make sure to check out Educative and you can actually get 20% off by going to educative.io/basecs. That’s B-A-S-E-C-S. Check it out. This episode was edited and mix by Levi Sharpe.

[00:20:52] VJ: Bye everyone.

[00:20:53] SY: Thanks for listening. See you next week.