DAG Longest Path: Difference between revisions

From visone manual
Jump to navigation Jump to search
(Created page with "The input must be a directed acyclic graph (DAG). A source in DAG is a node which has only outgoing links. Each node gets the length of the longest directed path from any source ...")
 
No edit summary
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
The input must be a directed acyclic graph (DAG).
Each node gets the length of the longest directed path from any source in the directed acyclic graph (DAG).
A source in DAG is a node which has only outgoing links.
A source in DAG is a node which has only outgoing links.
Each node gets the length of the longest directed path from any source in the DAG.
 
If the graph has cycles, each strongly connected component is aggregated to one node which results in a DAG.
In this case, each vertex gets the longest directed path from any strongly connected component whose nodes do not have any incoming edge to a node of another strongly connected component.

Latest revision as of 08:16, 7 August 2015

Each node gets the length of the longest directed path from any source in the directed acyclic graph (DAG). A source in DAG is a node which has only outgoing links.

If the graph has cycles, each strongly connected component is aggregated to one node which results in a DAG. In this case, each vertex gets the longest directed path from any strongly connected component whose nodes do not have any incoming edge to a node of another strongly connected component.