resolveShortestPathToRoot method
Resolves the shortest path to root from this node. Since inputs is populated in BFS, the 1st input is one of the closest to the root.
Implementation
List<Node<T>> resolveShortestPathToRoot() {
// A buffer on paths being computed until the root:
final computingPathsBuffer = [
[this]
];
final computingPathsIdxRet = <int>[0];
var expandCursor = 0;
var graphWalker = GraphWalker<T>();
var shortestPath = graphWalker.walkByNodes<List<Node<T>>>(
[this],
outputsProvider: (step, node) {
var inputs = node._inputs;
return inputs.isEmpty ? [] : [inputs.first];
},
process: (step) {
var node = step.node;
var computingPaths = _getComputingPaths<T>(
computingPathsBuffer, node, expandCursor, computingPathsIdxRet);
if (computingPaths == null) return null;
var computingPathsIdx = computingPathsIdxRet[0];
if (node.isRoot) {
// [computingPaths] of [node] completed.
// Return one of the shortest path (1st):
return GraphWalkingInstruction.result(computingPaths.first);
}
// In a BFS the 1st input will be one of the closest to root,
// don't need to expand with all the inputs:
var closerToRoot = node._inputs.first;
var inputs = [closerToRoot];
expandCursor = _expandComputingPaths<T>(computingPathsBuffer,
computingPaths, computingPathsIdx, inputs, expandCursor);
return null;
},
);
if (shortestPath == null) {
throw StateError("No path to root from: $value");
}
return shortestPath;
}