# A DAG Example in Javascript

One thing I've learned is to really understand something you have to do it. More times going over something = certainty. So if you forget the deets of something you read two weeks ago, thats totally understandable. Use it or loose it. Anyway I digress.

This is a series of data strucutures, working up to Merkle Binary Tree, Patricia Merkle Tree, Merkle DAG etc. Starting with the simplest first. Checkout the git repo.

## Definitions

DAG
Directionally Acyclic Graph
Merkle tree
A tree made from hashing paired data (the leaves), then pairing and hashing the results until a single hash remains, the merkle root. In Bitcoin, the leaves are almost always transactions from a single block.

## The DAG

``````class Graph {

constructor () {
this.nodes = {};
}

getNode (value) {
return this.nodes[value];
}

this.nodes[node] = this.nodes[node] || {
edges: {}
};
}

removeNode (node) {
delete this.nodes[node];
}

contains (node) {
return this.nodes.hasOwnProperty(node);
}

this.nodes[node1].edges[node2] = this.nodes[node2];
this.checkCyclic(node1, node2);
}

removeEdge (node1, node2) {
delete this.nodes[node1].edges[node2];
}

hasEdge (node1, node2) {
return this.nodes[node1].edges.hasOwnProperty(node2);
}

checkCyclic (parent, target) {
const cyclic = (node) => {
Object.keys(node.edges).forEach(edge => {
if (edge === parent) {
this.removeEdge(parent, target);
throw new Error('Graph is cyclic');
}
cyclic(this.getNode(edge));
});
}
cyclic(this.getNode(parent));
}

}

module.exports = Graph;
``````

## DAG and Merkle Tree

A Merkle DAG is a Merkle directed acyclic graph. That is a data structure similar to a Merkle tree but not so strict: such DAG does not need to be balanced and its non-leaf nodes are allowed to contain data.