Graph iteration from bottom to top algorithm?
Given this dependency graph: What's a "good" approach to iterate through it from bottom to top?
My expected results for each "cycle" are:
Iteration step "1": Project B, Project D, Project Z, Project O
Iteration step "2": Project C, Project W, Project V, Project Q
Iteration step "3": Project A, Project M
Iteration step "4": Start X // End
Brainstorming
// PSEUDO CODE: Find and return "next projects fixes" to perform.
// -> All projects with no or already fixed dependencies.
FUNC FindNextDependciesToFix ( NODE StartNode, BYREF LIST<NODE> RefNextProjectsToFix )
{
... // Algorithm ?
}
Reason wh开发者_Python百科y "Depth-first search" does not work:
DO
{
FindNextDependciesToFix (StartX, FixNextList);
CallASYNCAndWaitForEndOfFix (FixNextList);
// <- Wait till end of project fix (async...)
} WHILE ( FixNextList.IsEmpty() );
Algorithm
I really don't want to reinvent the wheel: So is there already an algorithm which solve this problem or does anyone have a "clever" approach?
You probably want topological sort to go through the graph of dependencies. You can do this with DFS (depth-first search) and BFS (breath-first search) as well -- both mentioned in pseudocode on the wikipedia link. Both are linear in input size.
Do a topological sort which gives nodes in order of depth. Then if you want to find the boundaries between different depths, use a dynamic programming algorithm. This solution is linear in the size of the graph, O(|V| + |E|).
精彩评论