Log in
Enquire now
Directed acyclic graph

Directed acyclic graph

A graph data structure that uses topological ordering, meaning that the graph flows in only one direction, and it never goes in circles.

OverviewStructured DataIssuesContributors

Contents

Is a
Industry
Industry

Other attributes

Wikidata ID
Q1195339

A Directed Acyclic Graph (DAG) is a type of graph in which it's impossible to come back to the same node by traversing the edges.

In graph theory, a graph is a structure consisting of nodes that are connected by edges. You can think of the nodes as points and the edges as lines drawn from point to point.

'Directed' means that the edges of the graph only move in one direction, where future edges are dependent on previous ones. For example, if you were to graph the process of cooking and eating a meal consisting of rice and chicken, the tasks involved would need to be topologically ordered (or topologically sorted). Before you can eat the meal, you must prepare the food, so the edge would necessarily be directed from preparation forward to eating. But before you can prepare the food, you must buy the ingredients, so again the edge must go from the earlier event to the later event. Supposing that the rice was bought in a separate event from the chicken, there would be two separate edges for the grocery shopping events that are not connected to each other, but which converge at the event of preparing the food.

'Acyclic' means that it is impossible to start at one point of the graph and come back to it by following the edges. Whereas a cycle comes back around to it's original starting point like a circle, an acyclic graph continues moving in a linear direction and never does circle back to the starting point. To continue with the earlier example of chicken and rice dinner, you can't move on the graph from buying the rice to preparing the food to buying the chicken, as that would require moving backwards across the graph. It's impossible to prepare the chicken if you haven't yet purchased it.

DAGs are probabilistic graphical representations of Bayesian networks that aim to model conditional dependence (e.g. eating the meal depends on preparing it first).

Several cryptocurrencies use DAGs rather than blockchain data structures in order to process and validate transactions. With blockchains, all of the nodes in a network build on the same single blockchain with each block referencing the one that came before it. A possible downside to this structure is that it puts a limit on the network's transaction throughput, as there are only so many transactions that can fit in a single block and only so many blocks that can be validated in a given time. In a DAG network, transactions are directly linked to each other rather than grouped into blocks, and transactions can be processed simultaneously with others. The result is a lessened bottleneck on transaction throughput.

Timeline

No Timeline data yet.

Companies in this industry

Further Resources

Title
Author
Link
Type
Date

A Gentle Introduction To Graph Theory - basecs - Medium

Vaidehi Joshi

https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8

Web

Bitcoin Q&A: Directed acyclic graphs (DAGs) and IOTA

https://www.youtube.com/watch?v=lfgMnbb5JeM&vl=en

February 26, 2018

Can someone explain in simple terms to me what a Directed acyclic graph is?

Forum discussion, multiple authors

https://stackoverflow.com/questions/2283757/can-someone-explain-in-simple-terms-to-me-what-a-directed-acyclic-graph-is

Web

Directed Acyclic Graph (DAG) Overview & Use Cases | Hazelcast

https://hazelcast.com/glossary/directed-acyclic-graph/

Web

Everything You Need to Know About Directed Acyclic Graphs (DAGS) - Coin Bureau

https://www.coinbureau.com/education/directed-acyclic-graphs-dags/

Web

References

Find more entities like Directed acyclic graph

Use the Golden Query Tool to find similar entities by any field in the Knowledge Graph, including industry, location, and more.
Open Query Tool
Access by API
Golden Query Tool
Golden logo

Company

  • Home
  • Press & Media
  • Blog
  • Careers
  • WE'RE HIRING

Products

  • Knowledge Graph
  • Query Tool
  • Data Requests
  • Knowledge Storage
  • API
  • Pricing
  • Enterprise
  • ChatGPT Plugin

Legal

  • Terms of Service
  • Enterprise Terms of Service
  • Privacy Policy

Help

  • Help center
  • API Documentation
  • Contact Us
By using this site, you agree to our Terms of Service.