resolveAllPathsToRoot method

List<List<Node<T>>> resolveAllPathsToRoot({ int maxExpansion = 3, })

Resolves all the paths to the root from this node.

The algorithm tries to remove meaningless nodes, such as branches that only exist due to indirect self-references.

Implementation

List<List<Node<T>>> resolveAllPathsToRoot({int maxExpansion = 3}) {
  var rootPaths = <List<Node<T>>>[];

  // A buffer on paths being computed until the root:
  final computingPathsBuffer = [
    [this]
  ];

  final computingPathsIdxRet = <int>[0];
  var expandCursor = 0;

  var graphWalker = GraphWalker<T>(maxExpansion: maxExpansion, bfs: true);

  graphWalker.walkByNodes<List<Node<T>>>(
    [this],
    outputsProvider: (step, node) => node._inputs,
    process: (step) {
      var node = step.node;

      var computingPaths = _getComputingPaths<T>(
          computingPathsBuffer, node, expandCursor, computingPathsIdxRet);

      if (computingPaths == null) return null;

      var computingPathsIdx = computingPathsIdxRet[0];
      var computingPathsEndIdx = computingPathsIdx + computingPaths.length;

      if (node.isRoot) {
        // [computingPaths] of [node] completed,
        // remove it from [computingPathsBuffer].
        computingPathsBuffer.removeRange(
            computingPathsIdx, computingPathsEndIdx);

        rootPaths.addAll(computingPaths);
        expandCursor = computingPathsIdx;

        // Allow independent branches to be computed:
        // Reset counter to 0:
        return GraphWalkingInstruction.setExpansionCounter(0);
      }

      final processed = step.processed;

      final newNode = processed[node] == 1;

      // Skip target nodes (leafs with `target == true`)
      // already processed (avoids self-reference):
      if (node.isTarget && !newNode) {
        return null;
      }

      var inputs = node._inputs;

      if (!newNode) {
        var unprocessed =
            inputs.where((e) => !processed.containsKey(e)).toList();

        // Not all inputs are unprocessed:
        if (unprocessed.length < inputs.length) {
          // Allow inputs that are not targets (leaves with `matches`)
          // or that are [unprocessed].
          var allowedIts =
              inputs.where((e) => !e.isTarget || unprocessed.contains(e));

          // Ensure that inputs processed more than 3 times are skipped,
          // to avoid infinite loops or meaningless branches already seen:
          allowedIts =
              allowedIts.where((e) => (processed[e] ?? 0) <= maxExpansion);

          var allowed = allowedIts.toList();

          // Only expand with allowed inputs:
          inputs = allowed;
        }
      }

      expandCursor = _expandComputingPaths(computingPathsBuffer,
          computingPaths, computingPathsIdx, inputs, expandCursor);

      return null;
    },
  );

  return rootPaths;
}