Advanced data structures. Part One: Directional Acyclic Graph

Hello! Next week, classes will begin in the new group of the Algorithms for Developers course. In this regard, we are sharing with you the translation of a very small, but rather interesting material.

---

I wanted to start this series of articles with a data structure that we all as developers are familiar with, but it is possible that we don’t even know how it works.



“Directional acyclic graph? I have never heard of this. Do not think that you know everything about me! ”You can say, but it is this graph that makes version control possible. Yes, Git is an acyclic graph. In this article, I will share with you knowledge of Directed Acyclic Graphs (DAGs), and then show you how to write your own.

What is a DAG?

So what does that even mean? A DAG is a unidirectional graph where no element can be considered a child. Many of us are familiar with linked lists, trees, and graphs. DAG is very similar to the first and second in the implementation of the third.





It looks like a tree, but not quite



In its most minimal form, DAG has 4 components:

1. Nodes They store data.
2. Directional Edges : Arrows that point in one direction (what makes this data structure unlike the others).
3. One “great” ancestor node without parents . (Fun fact: most ancestor trees are actually directed acyclic graphs, not trees, because sometimes "cousins ​​marry each other")
4. Leaves Or nodes without child nodes.

Let's write our directed acyclic graph



Now let's write the code. First, create a constructor with two properties and name it DAG.

function DAG() { this.nodes = []; this.vertices = {}; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Create a method to add nodes. See what I did here?

 DAG.prototype.add = function(node) { if (!node) { return; } if (this.vertices[node]) { return this.vertices[node]; } const vertex = { node: node, incoming: {}, incomingNodes: [], hasOutgoing: false, value: null }; this.vertices[node] = vertex; this.nodes.push(node); return vertex; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

How it works? The vertex



object is the place where all magic happens. We add a node, an object with incoming nodes, and an array with all their names, a variable of type Boolean that signals whether the node points to something or not, and its value. We will move on to this later.



Now let's add some edges and connect the nodes together. Before we can do this, we must create a helper function that checks whether we visited this node or not. Let's call her visit



.

 function visit(vertex, fn, visited, path) { const name = vertex.name, vertices = vertex.incoming, names = vertex.incomingNames, len = names.length, i; if (!visited) { visited = {}; } if (!path) { path = []; } if (visited.hasOwnProperty(name)) { return; } path.push(name); visited[name] = true; for (i = 0; i < len; i++) { visit(vertices[names[i]], fn, visited, path); } fn(vertex, path); path.pop(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The following happens:

 DAG.prototype.addEdge = function(fromName, toName) { if (!fromName || !toName || fromName === toName) { return; } const from = this.add(fromName) const to = this.add(toName); if (to.incoming.hasOwnProperty(fromName)) { return; } function checkCycle(vertex, path) { if (vertex.name === toName) { throw new Error(“Theres a cycle foo!!!!!“)); } } visit(from, checkCycle); from.hasOutgoing = true; to.incoming[fromName] = from; to.incomingNames.push(fromName); };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

It's time to pay tribute

While I was studying materials for writing this article, I read some wonderful messages from amazingly smart people, and as a result, most of the information was received from them. I got some of the theoretical information from this well-structured post on DAG and version control. The code presented here is inspired by emberjs sources and their authors. And I learned a lot from other articles and posts about DAG in the blogs of many great people.



Thanks for reading!