Can Someone Explain In Simple Terms To Me What A Directed Acyclic Graph Is?


Answer :

graph = structure consisting of nodes, that are connected to each other with edges

directed = the connections between the nodes (edges) have a direction: A -> B is not the same as B -> A

acyclic = "non-circular" = moving from node to node by following the edges, you will never encounter the same node for the second time.

A good example of a directed acyclic graph is a tree. Note, however, that not all directed acyclic graphs are trees.


dots with lines pointing to other dots


I see lot of answers indicating the meaning of DAG (Directed Acyclic Graph) but no answers on its applications. Here is a very simple one -

Pre-requisite graph - During an engineering course every student faces a task of choosing subjects that follows requirements such as pre-requisites. Now its clear that you cannot take a class on Artificial Intelligence[B] without a pre requisite course on Algorithms[A]. Hence B depends on A or in better terms A has an edge directed to B. So in order to reach Node B you have to visit Node A. It will soon be clear that after adding all the subjects with its pre-requisites into a graph, it will turn out to be a Directed Acyclic Graph.

If there was a cycle then you would never complete a course :p

A software system in the university that allows students to register for courses can model subjects as nodes to be sure that the student has taken a pre-requisite course before registering for the current course.

My professor gave this analogy and it has best helped me understand DAG rather than using some complicated concept!

Another real time example -> Real Time example of how DAG's can be used in version system


Comments

Post a Comment

Popular posts from this blog

Are Regular VACUUM ANALYZE Still Recommended Under 9.1?

Answer : VACUUM is only needed on updated or deleted rows in non-temporary tables. Obviously you're doing lots of INSERTs but it's not obvious from the description that you're also doing lots of UPDATEs or DELETEs. These operations can be tracked with the pg_stat_all_tables view, specifically the n_tup_upd and n_tup_del columns. Also, even more to the point, there is a n_dead_tup column that tells, per table, how much rows need to be vacuumed. (see Monitoring statistics in the doc for functions and views related to statistics gathering). A possible strategy in your case would be to suppress the scheduled VACUUM, keeping an eye on this view and checking on which tables the n_dead_tup is going up significantly. Then apply the aggressive VACUUM to these tables only. This will be a win if there are large tables whose rows never get deleted nor updated and the aggressive VACUUM is really necessary only on smaller tables. But keep running the ANALYZE for the optimiz
Read more

Can Feynman Diagrams Be Used To Represent Any Perturbation Theory?

Answer : Diagram machinery works also for perturbation theory in classical statistical mechanics and classical field theories. Generally, various kinds of diagrams constitute a pictorial way of talking about tensor products and their contractions while hiding the multi-linear algebra from the layman. In the simplest case, vertices (or blobs) represent vectors, matrices, tensors; vertices have ingoing and/or outgoing ports; ingoing ports denote (contravariant) ro indices; outgoing ports denote (covariant) co indices; directed arcs between blobs give a pair of equal indices summed over; different base spaces ⇔ \Leftrightarrow ⇔ different arc types; symmetric tensors ⇔ \Leftrightarrow ⇔ undirected diagrams; no labels are needed for internal lines. In many cases, the directed arcs are decorated (as thin, thick, broken,wavy, curly lines), each decoration indicating the presence of a so-called propagator, a function of its label to use as a weight in the sum, which may beco
Read more