Paths With Shared Structure
A third type of application of directed acyclic graphs arises in representing a set of sequences as paths in a graph. For example, the directed acyclic word graph is a data structure in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of strings, such as English words. Any set of sequences can be represented as paths in a tree, by forming a tree node for every prefix of a sequence and making the parent of one of these nodes represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a trie. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree node.
The same idea of using a DAG to represent a family of paths occurs in the binary decision diagram, a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any truth assignment to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of tries, binary decision diagrams can be viewed as compressed forms of decision trees that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.
In many randomized algorithms in computational geometry, the algorithm maintains a history DAG representing features of some geometric construction that have been replaced by later finer-scale features; point location queries may be answered, as for the above two data structures, by following paths in this DAG.
Read more about this topic: Directed Acyclic Graph
Famous quotes containing the words paths, shared and/or structure:
“If this be love, to clothe me with dark thoughts,
Haunting untrodden paths to wail apart;
My pleasures horror, music tragic notes,
Tears in mine eyes and sorrow at my heart.
If this be love, to live a living death,
Then do I love and draw this weary breath.”
—Samuel Daniel (1562–1619)
“When our kids are young, many of us rush out to buy a cute little baby book to record the meaningful events of our young child’s life...But I’ve often thought there should be a second book, one with room to record the moral milestones of our child’s lives. There might be space to record dates she first shared or showed compassion or befriended a new student or thought of sending Grandma a get-well card or told the truth despite its cost.”
—Fred G. Gosman (20th century)
“The structure was designed by an old sea captain who believed that the world would end in a flood. He built a home in the traditional shape of the Ark, inverted, with the roof forming the hull of the proposed vessel. The builder expected that the deluge would cause the house to topple and then reverse itself, floating away on its roof until it should land on some new Ararat.”
—For the State of New Jersey, U.S. public relief program (1935-1943)