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

Converting A String To Int In Groovy

Answer : Use the toInteger() method to convert a String to an Integer , e.g. int value = "99".toInteger() An alternative, which avoids using a deprecated method (see below) is int value = "66" as Integer If you need to check whether the String can be converted before performing the conversion, use String number = "66" if (number.isInteger()) { int value = number as Integer } Deprecation Update In recent versions of Groovy one of the toInteger() methods has been deprecated. The following is taken from org.codehaus.groovy.runtime.StringGroovyMethods in Groovy 2.4.4 /** * Parse a CharSequence into an Integer * * @param self a CharSequence * @return an Integer * @since 1.8.2 */ public static Integer toInteger(CharSequence self) { return Integer.valueOf(self.toString().trim()); } /** * @deprecated Use the CharSequence version * @see #toInteger(CharSequence) */ @Deprecated public static Integer toInteger(String self) { return toInteg
Read more

"Cannot Create Cache Directory /home//.composer/cache/repo/https---packagist.org/, Or Directory Is Not Writable. Proceeding Without Cache"

Answer : if anyone pass through here, this is shorter solution: sudo chown -R $USER $HOME/.composer it seems to me the group information is missing in your command sudo chown -R <user> /home/<user>/.composer/cache/repo/https---packagist.org Shoud be sudo chown -R <user>:<group> /home/<user>/.composer/cache/repo/https---packagist.org But to avoid other permission issues, I would rather advise: sudo chown -R <user>:<group> /home/<user>/.composer/cache (you'll need access to other folders in there) and sudo chown <user>:<group> /home/<user>/.composer To make sure your user has permissions enough on the global composer folder. Mind the missing recursion so the user don't own keys created by root. If you need to find out the group: groups <user>
Read more

Android How Can I Convert A String To A Editable

Answer : As you probably found out, Editable is an interface so you cannot call new Editable() . However an Editable is nothing more than a String with Spannables, so use SpannableStringBuilder: Editable editable = new SpannableStringBuilder("Pass a string here"); If you only want to change the Spannables, never the text itself, you can use a basic SpannableString. Use Editable.Factory.getInstance().newEditable(str) From the android documentation: Returns a new SpannedStringBuilder from the specified CharSequence. You can override this to provide a different kind of Spanned.
Read more