Reachability and DAG Reduction Example:
The reachability relationship in any directed acyclic graph can be formalized as a partial order ≤ on the vertices of the DAG. In this partial order, two vertices u and v are ordered as u ≤ v exactly when there exists a directed path from u to v in the DAG; that is, when v is reachable from u. However, different DAGs may give rise to the same reachability relation and the same partial order. For example, the DAG with two edges a → b and b → c has the same reachability relation as the graph with three edges a → b, b → c, and a → c. Both of these DAGS produce the same partial order, in which the vertices are ordered as a ≤ b ≤ c.
A Hasse diagram representing the partial order of set inclusion among the subsets of a three-element set. If G is a DAG, its transitive closure is the graph with the most edges that represents the same reachability relation. It has an edge u → v whenever u can reach v. That is, it has an edge for every related pair u ≤ v of distinct elements in the reachability relation of G, and may therefore be thought of as a direct translation of the reachability relation ≤ into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set (S, ≤), the graph that has a vertex for each member of S and an edge for each pair of elements related by u ≤ v is auto-matically a transitively closed DAG, and has (S, ≤) as its reach-ability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG.
The transitive reduction of a DAG G is the graph with the fewest edges that represents the same reachability relation as G. It is a subgraph of G, formed by discarding the edges u → v for which G also contains a longer path connecting the same two vertices. Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.
If a DAG G has a reachability relation described by the partial order ≤, then the transitive reduction of G is a subgraph of G that has an edge u → v for every pair in the covering relation of ≤. Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler graph drawings. A Hasse diagram of a partial order is a drawing of the transitive reduction in which the orientation of each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.
In other words, transitions can be simplified to adjacent states, minimizing skipped states from one state to a state beyond the next layer state. Essentially, all states are still “reachable”, direct state-to-state’s are somewhat redundant. The processing, or latency of a state, not withstanding. Transitive reductions, or simplifications, are useful in visualizing and the partial orders they represent. This might apply to any software-like flow?
The task graph reduced-view provides an opportunity to examine potential simplifications in a structured, machine-like fashion. A VisualSim Power_Manager can implement a reduced Power state diagram with external RegEx functions, assuming the task graph represents the power states, for example.
Web: https://en.wikipedia.org/wiki/Directed_acyclic_graph