resolveShortestPathToRoot method

List<Node<T>> resolveShortestPathToRoot()

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;
}