walk<R> method

R? walk<R>(Iterable<T> from, { required GraphWalkNodeProvider<T> nodeProvider, required GraphWalkOutputsProvider<T> outputsProvider, required GraphWalkNodeProcessor<T, R> process, int? maxDepth, })

A generic walk algorithm.

Implementation

R? walk<R>(
  Iterable<T> from, {
  required GraphWalkNodeProvider<T> nodeProvider,
  required GraphWalkOutputsProvider<T> outputsProvider,
  required GraphWalkNodeProcessor<T, R> process,
  int? maxDepth,
}) {
  maxDepth ??= defaultMaxDepth;

  final processed = _processedNodes;
  final queue = ListQueue<GraphNodeStep<T>>();

  for (var rootValue in from) {
    var rootStepValue = GraphValueStep.root(this, rootValue);

    final rootNode = nodeProvider(rootStepValue, rootValue) ??
        (throw StateError("Can't find root node: $rootValue"));

    var rootStep = GraphNodeStep.root(this, rootNode);
    queue.add(rootStep);
  }

  while (queue.isNotEmpty) {
    final step = queue.removeFirst();
    final node = step.node;
    final nodeValue = step.nodeValue;

    var processCount = processed.increment(node);

    if (processCount <= maxExpansion && step.depth <= maxDepth) {
      if (processRoots || step.isNotRoot) {
        var ret = process(step);

        if (ret != null) {
          if (ret is GraphWalkingInstructionResult) {
            return ret.result as R?;
          } else if (ret is GraphWalkingInstructionOperation) {
            switch (ret.operation) {
              case GraphWalkingOperation.stop:
                return null;
              case GraphWalkingOperation.next:
                continue;
            }
          } else if (ret is GraphWalkingInstructionSetExpansionCounter) {
            processed[node] = ret.count;
          } else if (ret is GraphWalkingInstructionSetNodesExpansionCounter) {
            processed.addCounter(ret.counter);
          } else {
            return _resolveWalkProcessReturn<T, R>(node, ret);
          }
        }
      }

      if (stopMatcher.matchesNode(node)) {
        return _resolveWalkProcessReturn<T, R>(node, true);
      }

      var outputs = outputsProvider(step, nodeValue);
      if (outputs != null) {
        var outputsNodes = outputs.map((v) {
          var nodeStepValue = GraphValueStep.subNode(step, v);
          return nodeProvider(nodeStepValue, v)!;
        });

        queue.addAllToScanQueue(outputsNodes.toGraphNodeStep(step), bfs);
      }
    }
  }

  return _resolveWalkProcessReturn<T, R>(null, false);
}