Spinning Around In Cycles With Directed Acyclic Graphs
Tags: programming, computerscience, tech, datastructures
Published: 2017-10-02 18:50:50

---
title: "Spinning Around In Cycles With Directed Acyclic Graphs"
published: true
tags: programming,computer-science,tech,data-structures
canonical_url: https://medium.com/basecs/spinning-around-in-cycles-with-directed-acyclic-graphs-a233496d4688
description: "At first, I thought that this strange cyclic process of stumbling upon the same concepts again and again was unique to computer science. But these days, I am of a different opinion: the process of learning and relearning an idea is fundamental to understanding it at a deeper level."
cover_image: https://thepracticaldev.s3.amazonaws.com/i/ztiae4o7cf31sva8n7ki.png
---

Throughout the course of this series, I’ve written quite a bit about rediscovering things in computer science that I had heard or read about before, but didn’t really have enough context to understand.

At first, I thought that this strange cyclic process of stumbling upon the same concepts again and again was unique to computer science. But these days, I am of a different opinion: the process of learning and relearning an idea is fundamental to understanding it at a deeper level. This idea has a name: [the hermeneutic circle](https://en.wikipedia.org/wiki/Hermeneutic_circle). At it’s core, the hermeneutic circle is grounded in the idea that we must return to ideas again and again, and understand parts of them at a time in order to fully comprehend the whole (and vice versa).

This is cyclical process is exactly what I experienced while learning about different types of graphs, including directed graphs, cyclic graphs, and everything in between. I had heard about these types of graphs before and was slightly familiar with all of them, but didn’t fundamentally understand when they would be used, or why they kept coming up again and again, in everything that I read.

As it turns out, learning is hard! And it takes time, as well as a good amount of repetition. So, let’s return to graphs and learn about a specific subset of them that are fundamental to many solutions in computer science.

### Edges, edges, everywhere

Throughout our exploration of graphs, we’ve focused mostly on[representing graphs](https://dev.to/vaidehijoshi/from-theory-to-practice-representing-graphs), and [how to search](https://dev.to/vaidehijoshi/going-broad-in-a-graph-bfs-traversal) through them. Last week, we looked at **_depth-first search (DFS)_**, a graph traversal algorithm that [recursively determines](https://dev.to/vaidehijoshi/deep-dive-through-a-graph-dfs-traversal) whether or not a path exists between two given nodes. However, it’s worth cycling back to depth-first search again for a few reasons.

![](https://cdn-images-1.medium.com/max/1024/1*wFHq_9nahZkd_W33Ze3A1Q.jpeg)<figcaption>The DFS algorithm is helpful in identifying cycles, determining edges, and ordering vertices.</figcaption>

Depth-first search is useful in helping us learn more about a given graph, and can be particularly handy at ordering and sorting nodes in a graph. We can use the DFS algorithm to identify cycles within a graph, to determine what kinds of edges a graph has, and to order the vertices within in a linear fashion.

We’ll work our way through each of these three tricks today, and see how using depth-first search can help us better understand what kind of graph we’re dealing with in the process of searching _through_ it!

Early on in this series, we [learned about edges](https://dev.to/vaidehijoshi/a-gentle-introduction-to-graph-theory), the elements that connect the nodes in a graph. We also learned that edges can be _directed_, with a flow from one node to another, or _undirected_, with a bidirectional flow between both vertices. But, keeping with the theme of this post, let’s return back to what we _think_ we already know.

If we cycle back to edges, we’ll see that, in the context of a graph, edges can be more than just “directed” or “undirected”. Two directed edges can be very different from one another, depending on where in the graph they happen to occur! Let’s take a look at some of the other ways that we can classify edges in a graph.

![](https://cdn-images-1.medium.com/max/1024/1*l8JVWt_eoZzcAUjgJECeDw.jpeg)<figcaption>Edge classification in a graph, partÂ 1</figcaption>

There are two main categories of edges in a graph data structure: a **tree edge** and a **non-tree edge**. We’ll recall that in both [the BFS algorithm](https://dev.to/vaidehijoshi/going-broad-in-a-graph-bfs-traversal) as well as in [the DFS algorithm](https://dev.to/vaidehijoshi/deep-dive-through-a-graph-dfs-traversal), the _parent pointers_, which lead back to the starting node, can be rearranged to form a tree.

Any edge that is part of a path taken in a graph traversal algorithm is known as a **_tree edge_** , since it is an edge that allows us to visit a new vertex each time as we traverse through the graph, and can be restructured to form a “tree”.

So, what about the non-tree edges? Well, there are three different variations of those, and we’ve actually already encountered all of them, even if we didn’t necessarily know what they were called at the time.

The first of the three is called a **_forward edge_** , as it allows us to move “forward” through the graph, and could potentially be part of another path down the tree. By contrast, there is also the **_backward edge_** , which connects a node in a graph “back up” to one of its ancestors (its parent or grandparent node, for example, or even back to itself!). Finally, there is the **_cross edge_** , which “crosses over” and connects one subtree in a graph to another. In other words, a cross edge connects to sibling nodes that don’t necessarily share an ancestor in a tree path, but connects them anyways.

These definitions make a whole lot more sense when we can see them applied to _actual_ nodes in a graph, so let’s look at an example.

![](https://cdn-images-1.medium.com/max/1024/1*X01zera2nJmsk2Z_6Y4wtA.jpeg)<figcaption>Edge classification in a graph, partÂ 2</figcaption>

In the illustration shown here, we can see that the tree edges, highlighted in blue, are the ones that we walk through as part of our traversal down our path in the graph; in this case, our walk is u-v-y-x. The edges connecting these vertices in our path are our _tree edges_. However, we could have also walked “forward” in a different path, and walked from u to x; thus, the edge (u, x) is a _forward edge_.

We’ll notice that, when we get to node x, the only vertex to navigate to next is v. The edge connecting these two nodes in the tree, (x, v), is a _backward edge_, since it connects the node x back to one of its ancestors in the path: node v. We’ll also notice that, in another part of the graphâ€Š–â€Šin a different subtree, ratherâ€Š–â€Šnode z has a backward edge that is actually connecting _back to itself_. This is also known as a **_self-loop_** , or a backward edge that connects a node back to itself, or an edge that “references” the node that it came from: (z, z). (We’ll come back to self-loops later on, but this is our very first taste of them!)

The edge that connects node w and y, which we can also call (w, y), is a _cross edge_ as it connects the subtree. Cross edges are a little easier to see when we rearrange our tree edges to actually _form_ a tree, so let’s redraw that same graph to make our cross edge more obvious. In the image below, we’ll see two potential “trees” that could be formed by starting at two different nodes in the graph: node u or node w, respectively.

![](https://cdn-images-1.medium.com/max/1024/1*2fi-xG12CyAQ8Ih4CzP76Q.jpeg)<figcaption>A graph, reimagined as connected (sub)trees</figcaption>

The edge (w, y) connects the two subtrees of this entire graph together, even though there is no single “root node” or ancestor that the subtrees actually share. Remember that a graph is a very “loose” version of a tree, and [doesn’t follow the same rules](https://dev.to/vaidehijoshi/a-gentle-introduction-to-graph-theory) that a tree would.

> Since a graph doesn’t have one single root node, it doesn’t form a single tree. Rather, a graph could contain many small subtrees within it, each of which would become obvious as we walked through the paths of the graph. A graph is less of an individual tree data structure, and more of an interconnected forest, with small subtrees within it.

There is one important thing to note about all of these different kinds of edges: they don’t always exist! It all depends on what type of graph we’re dealing with. In a _directed_ graph, tree edges, cross edges, backward edges, and forward edges are all possible. However, for an _undirected_ graph, it’s a different story altogether.

![](https://cdn-images-1.medium.com/max/1024/1*Xr7NbsTsh5bQFVG9kvKvUw.jpeg)<figcaption>An undirected graph can only ever have tree edges or backward edges, partÂ 1</figcaption>

In an undirected graph, there are no forward edges or cross edges. Every single edge must be either a tree edge or a back edge.

> An easy way to remember the rules of edge classification is this: an undirected graph can only have tree edges and back edges, but a directed graph could contain all four edge types.

Okay, but what’s the story behind this rule? Well, it’s a lot easier to see if we actually try it out on an example, so we’ll do exactly that.

![](https://cdn-images-1.medium.com/max/1024/1*TbPs52d3masVAkbp6uTPpQ.jpeg)<figcaption>An undirected graph can only ever have tree edges or backward edges, partÂ 2</figcaption>

In the graph shown here, we have four vertices, and four edges. Let’s say that the edge (a, d) is a “forward” edge; in other words, it’s an edge that allows us to move from node a to node d.

Imagine that we walk through this graph, from node a to b, and then from b to c. When we get to node c, there is nowhere else for us to go, so we must backtrack up to node b.

Now, in order for us to properly run the depth-first search algorithm, we need to check if there are any other vertices that we can “visit” from node b. As it turns out, there is one! We’ll visit node d. We’re once again in a similar situation, and we have to check if there is another node that we can visit from d. As it turns out, since this is an undirected graph, there is one place we can visit: node a. At this moment, it becomes impossible for the edge (a, d) to be a “forward” edge. Since the rules of DFS dictate that we _must_ visit node a from d since we must explore the graph on the _deepest_ level, we must visit it; we cannot backtrack back _up_ to node a and then visit d from there!

An undirected graph can never allow for a forward edge like (a, d) since, in order for a forward edge to exist, we would need to completely finish visiting all the nodes reachable from our starting node a before traversing through the edge. In an undirected graph, this is literally impossible to do! So, the edge between these two nodes really ought to be written like this: {a, d}, since we can traverse in either direction on this edge, depending on which node we start with.

Even though we won’t look at an example of it here, we could disprove cross edges similar to forward edges, since they also cannot exist in an undirected graph.

### Round and round

Another great strength of the depth-first search algorithm is its ability to identify cycles in a graph. Before we get too far into how to do that, let’s familiarize ourselves with some important terms that we’ll end up using along the way.

A **_cycle_** , in the context of a graph, occurs when some number of vertices are connected to one another in a closed chain of edges. A graph that contains at least one cycle is known as a **_cyclic graph_**. Conversely, a graph that contains zero cycles is known as an **_acyclic graph_**.

![](https://cdn-images-1.medium.com/max/1024/1*GnMghFkLYP6LGbbGsPYLww.jpeg)<figcaption>Cyclic vs. acyclicÂ graphs</figcaption>

In the previous section, we saw our first instance of a **_self-loop_** , a type of backward edge. Self-loops can only ever occur in a _directed_ graph, since a self-loop is a type of _directed_ edge.

![](https://cdn-images-1.medium.com/max/1024/1*yH6b4iPJI1RTDtWJSbpXLw.jpeg)<figcaption>A directed cyclic graph, with a self-loop</figcaption>

Both directed and undirected graphs can have cycles in them, but it’s worth noting that a self-loop can only ever occur in a **_directed cyclic graph_** , which is a directed graph that contains at least one cycle in it.

> As it turns out, the reason that the depth-first search algorithm is particularly good at detecting cycles is because of the fact that it is efficient at finding backward edges.

By definition, any graph that has a backward edge will contain a cycle. In the graph drawn below, we can see that node e connects back to an ancestor in the path, node a. Because of a backward edge exists in this directed graph, we know that this graph also contains a cycleâ€Š–â€Šit is a _directed cyclic graph_.

![](https://cdn-images-1.medium.com/max/1024/1*QvIWlS6sc9fKOexXFqH_fQ.jpeg)<figcaption>Cycle detection and backwardÂ edges</figcaption>

Okay, but how does DFS actually detect cycles, exactly? And why is this algorithm in particular so efficient at determining whether or not a cycle exists within a graph? Well, it all goes back to the recursive nature of the depth-first search algorithm. We’ll recall that DFS uses a stack data structure [under the hood](https://dev.to/vaidehijoshi/deep-dive-through-a-graph-dfs-traversal). This makes is slightly easier to know whether a backward edge exists in the path as we walk through the graph.

![](https://cdn-images-1.medium.com/max/1024/1*JXgI4Jg2pqcGcaB51-X5_Q.jpeg)<figcaption>We can use DFS to detect cycles in aÂ graph.</figcaption>

For example, in the example graph from earlier, when we traverse from u to v to y to x, we add each of these elements to the stack of nodes that we’ve visited. We can take one additional step to make it easy to classify edges: we can mark the node u as currently beingProcessed with a simple boolean flag when we start searching down its “deepest” path. Once we flag node u as being the node that we’re searching through, if any node that we add to the stack that references _back up_ to u, we know that we have found a cycle. Indeed, this same logic applies to other internal cycles in the graph, and not just cycles connecting back up to the starting node.

> If any node added to the stack has a reference to a node that is already _within_ the stack, we can be sure that we have a cycle in this graph.

But waitâ€Š–â€Šthere’s more! Well, okayâ€Š–â€Šthere is just _one_ more. The final type of graph that we need to define is a directed graph _without_ cycles.

Most implementations of depth-first search will check to see if any cycles exist, and a large part of that is based on the DFS algorithm checking to see whether or not a graph is a **_directed acyclic graph_** , also known as a **_DAG_**. A directed acyclic graph is, as its name would suggested, directed, but without any cycles. The golden rule of DAGs is that, if we start at any node in the graph, no sequence of edges will allow us to loop back to the starting node. Thus, by definition, a directed acyclic graph can never contain a self-loop.

![](https://cdn-images-1.medium.com/max/1024/1*btUG3yUhEPfj5_ESgE4I9w.jpeg)<figcaption>Directed acyclic graphsÂ (DAGs)</figcaption>

DAGs are somewhat infamous in computer science because they’re pretty much _everywhere_ in sofware. For example, a directed acyclic graph is the backbone of applications that handle [scheduling for systems](https://en.wikipedia.org/wiki/Directed_acyclic_graph#Scheduling) of tasks or handling jobsâ€Š–â€Šespecially those that need to be processed in a particular order. At a higher level, DAGs are used to represent [state machines](https://en.wikipedia.org/wiki/Finite-state_machine), which are often used to keep track of objects that have a mutable state in web and mobile applications.

My personal favorite example, however, is the use of DAGs to represent [dependency graphs](https://en.wikipedia.org/wiki/Dependency_graph). If you’ve ever had to resolve dependencies in a [Gemfile](http://bundler.io/gemfile.html), or handle updating packages or navigate dependency issues using package managers like [npm](https://www.npmjs.com) or [yarn](https://yarnpkg.com/en/), then you were interacting with a DAG, on a very abstracted level! The dependency graph is also a great example of how DAGs can be complicated and massive and size, and why it can be useful to sort through and order the nodes within such a graph.

So, let’s learn how to do that!

### Topological sorting

Since we now know how vast and complicated a directed acyclic graph can actually be, being able to sort through and order vertices and make sense of the data _within_ a DAG can be super helpful. Thankfully, there is an algorithm that does exactly that!

![](https://cdn-images-1.medium.com/max/1024/1*DpkPJ0uEDaXtf2t-TLHZYA.jpeg)<figcaption>Topological sort: a defintion</figcaption>

The **_topological sort algorithm_** allows us to sort through the vertices of graph in a specific order, based on the interconnectedness of the edges that connect the vertices. If two vertices, x and y exist in a graph, and a directed edge (x, y) exists between them, then topological sort will order the vertices in the way that we would encounter them in a path: x, followed by y.

If we consider the ordering of topological sort, we’ll notice that the sorting itself is **_non-numerical_**. In other words, the order of the vertices is based on the _edges_ that connect them, and not any numeric value.

![](https://cdn-images-1.medium.com/max/1024/1*UOM0uS-9-LRVsoyZ8mFDIA.jpeg)<figcaption>Topological sort and its resulting topological order</figcaption>

The most important thing to keep in mind when it comes to topological sort is the fact that we can only ever visit a vertex after all the vertices leading up to it have _already_ been visited.

For example, in the graph shown here, we have five nodes: v, w, x, y, and z. In order to run topological sort on this directed graph, we need to be sure that, as we order and visit our vertices, the node y cannot be visited until both x and w have been visited.

Just from looking at this graph, we can see that there are two possible routes that we could take: v-w-x-y-z or v-x-w-y-z. In both of these two paths, we would still be visiting node y after both x and w. Thus, both of them are valid, and each of them return valid **_topological orders_** , which is the ordered set of vertices that is the returned result of running topological sort.

In this graph, we don’t have a cycle. But what if we did? The simplest version of such a graph would have two nodes, each of which reference one another, forming a cycle. Here’s an example of what that graph might look like:

![](https://cdn-images-1.medium.com/max/1024/1*YLZkuCdhFxZ6a0VhTz13RQ.jpeg)<figcaption>Topological sort can only ever be applied to DAGs, or acyclicÂ graphs.</figcaption>

In this example, vertex a depends on b, which in turn, depends back on a. The issue here is that we can’t apply the rule of visiting the vertices that “lead up” to the one we’re starting with, because they both lead up to one another.

> A topological sort can only ever be applied to directed acyclic graphs, or DAGs. It is impossible to run a topological sort on a directed graph with a cycle, since it is unclear where the sort itself should start.

There are a few different ways to actually implement topological sort. However, for today, we don’t even need to learn any new ones, because we already _know_ one intuitively! I’m talking, of course, about _depth-first search_.

So, let’s take a look at topological sort in actionâ€Š–â€Šusing DFS to help us!

![](https://cdn-images-1.medium.com/max/1024/1*jXJpM4d0a3Ma5CB36tRKwQ.jpeg)<figcaption>Topological sort inÂ action!</figcaption>

We’ll work with the same graph as earlier; the important thing about running DFS to find a topological order is using the _reverse_ _of the DFS finishing order_ to assemble our vertices.

We’ll start by running DFS on our starting “parent” node, which has to be v, as it is the only node without an edge leading up to it. We can choose either w or x to traverse downâ€Š–â€Šit doesn’t really matter which. In this example, we’ll choose w, and continue down to y, then z.

When we reach z, we’ve hit a dead end! So, we’ll need to backtrack up to y. But, before we backtrack up, we’ll assign a number (which we’ll use to order our vertices in a moment) to node z. In this case, we’ll assign it a value of 4 since it is going to be ordered lastâ€Š–â€Šremember, we want the _reverse_ of DFS’s finishing order.

Next, we’ll backtrack up to y; since there’s nowhere to go from there, we’ll repeat the same step of assigning a number, 3, and then again backtracking up to w. We’ll continue to do this until we get to a node with an _unvisited_ edge. Each time we do this, we’ll order the vertex as necessary.

Finally, we end up back at our starting node, v. When we do backtrack up to the “parent” node, we’ll see that there is one edge that we haven’t visited: the only one left is x. So, we’ll visit it, assign it a number (in this case, 1) and finish up with our search through the node v. Finally, if we follow the number 0-1-2-3-4, we’ll end up with the order v-x-w-y-z.

And there we have it! Our vertices are all sorted so that any node that is dependent on a node that _precedes_ it will only be visited if it’s parent(s) in the pathâ€Š–â€Šits dependenciesâ€Š–â€Šare visited first. Now, our example graph was pretty small, but we can imagine how npm or yarn might do this for a much larger graph of dependencies.

So, the next time you feel intimidated by updating your dependencies, just remember: it’s just a directed acyclic graph! You got this.

### Resources

There are a few different approaches to topological sort, but I find that understanding it from the context of depth-first search and cycles in a graph to be the easiest. Thankfully, there are some good resources out there that break down how topological sort works in other contexts, not to mention all the extensive resources on directed acyclic graphs! Here are some of my favorites if you want to keep learning.

1. [Graph Topological Sort Using Depth-First Search](https://www.youtube.com/watch?v=n_yl2a6n7nM&t), Sesh Venugopal
2. [Depth-First Search (DFS), Topological Sort](https://www.youtube.com/watch?v=AfSk24UTFS8&t=201s), MIT OpenCourseWare
3. [Topological Sortingâ€Š–â€ŠGraph Theory](https://www.youtube.com/watch?v=jonc-AGbPQo&t), NerdFirstTV
4. [Graph Traversals](http://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/lec24-12sp.html), Andrew Myers, Cornell University Department of Computer Science
5. [Depth-first Search](https://www3.cs.stonybrook.edu/~algorith/video-lectures/2007/lecture12.pdf), Professor Steven Skiena
6. [Topological Sort](http://www.cs.utoronto.ca/~tabrown/csc263/2014W/week9.pdf), Professor Trevor Brown

* * *