Difference between revisions of "DAG Longest Path"

From visone manual
Jump to navigation Jump to search
 
Line 2: Line 2:
 
A source in DAG is a node which has only outgoing links.
 
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 vertex which results in a DAG.
+
If the graph has cycles, each strongly connected component is aggregated to one node which results in a DAG.
Each vertex gets the longest directed path from any strongly connected component which has not incoming edges from any other strongly connected component.
+
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.