Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
I recently found a framework named ecto.
In this framework, a basic component named "plasm", which is the ecto Directed Acyclic Graph.In ecto, plasm can be operated by ecto scheduler.
I am wondering what's the advantage of this mechanism, and in what other situations can we exploit the concept of DAG?
Nice Question.
EDIT :
Good Resources :
The answer is that it doesn't have much of anything to do with programming. It has to do with problem solving.
Just like linked-lists are data structures used for certain classes of problems, graphs are useful for representing certain relationships. Linked lists, trees, graphs, and other abstract structures only have a connection to programming in that you can implement them in code. They exist at a higher level of abstraction. It's not about programming, it's about applying data structures in the solution of problems.
If still you want some relationship with programming then please consider following points:
Other people have applied DAG to data, but I think it is at least as applicable (if not more so) to code. Mahbubur R Aaman mentions this, so really this is more of an addendum to his answer than a complete answer on its own.
It occurs to me than any imperative computer program that is free of infinite loops (thanks @AndresF.) is a Directed Acyclic Graph (DAG). Meaning that the possible paths of execution of the code are directed (first this, then that), and acyclic (not forming infinite loops). They are a graph because the path through any significant code is rarely as simple as a list or a tree.
I worked in XSLT for maybe 4 years. I had a terrible time trying to explain why it was not a good general purpose programming language, but DAG is the reason. Specifically, XSLT is a data driven language. You define functions (yes, in the functional-programming sense) but you don't necessarily call these functions from your code. Rather, XSLT sets up a combination of selection of, and iteration through, the nodes of an input XML document. This lets the structure of the input data determine which functions are called and in what order.
This was very interesting and very cool until your program encountered a data condition that you didn't test for at 2:30 AM and you had to wake up and fix it. When you let the data define the DAG, then the definition of the DAG becomes all the possible input conditions - which for any non-trivial business application are beyond incalculable; they are unimaginable.
At first I thought that functional programming may not be a DAG because execution order is sometimes not clear to, or even thought about by the programmer. But a functional program does define dependencies. In fact, the declarative nature of functional programming could be thought of as defining only dependencies (a^2 = b^2 + c^2) without specifying execution order (it does not matter whether 'b' or 'c' is squared first, so long as they are both squared before being added together).
But while Functional programming may be deliberately vague about order of operations at a detailed level, it is exquisitely clear about dependencies. These are the very features that make it so amenable to concurrency. In any case, there is still a graph of paths through the code, and that graph is still directed (dependencies must be evaluated before dependent tasks), so I think DAG applies there as well.
Nice question - thanks for posting!
while (true) { print("hi"); } ? Maybe you want to exclude non-terminating programs?
Apr 16, 2013 at 16:55
Currently DAG is underrated in programming. Historically many things related to development were made with trees and hierarchies because moving something in a box is convenient for our brain to make complex things easier to manage. But if you look at events and how they depend on other events and states then you will get DAG because anything in our life and in the program can depend on anything in the past but not in the future, so you would get perfectly "acyclic" relations to be applicable to DAG concept. Although this rarely used explicitly in development, having this in mind would help to understand things better
I am wondering what's the advantage of Plasm in Ecto...
DAG can be used to model a collection of tasks in a sequence with the constraint that certain tasks must be done before the others. Ecto is a processing framework and it uses DAG to model processing graphs so that the graphs do ordered synchronous execution. Plasm in Ecto is the DAG and Scheduler operates on it.
in what other situations can we exploit the concept of DAG?
As a real world example, our software is similar to an IDE where the end user can define a series of operations to be performed on an image (machine vision inspection). These inspections can have dependencies on other inspections or may have inspections dependent upon them. Since this is all configurable by the end user, we cannot make optimizations for parallel processing at design time. By representing these inspections and dependencies as a DAG, we can optimize the parallelism of the overall inspection for maximum performance at run time.
Just for another example, the memory management rules in Cocoa apps are made so that all strong references form a directed acyclic graph, which is done to guarantee the absence of leaks.
Adding another answer as have not seen a reference to build systems like make which uses DAG to find out dependencies for building.
More details here
make