walkOrder method

List<Node<T>> walkOrder(List<T> roots, { required GraphWalkNodeProvider<T> nodeProvider, required GraphWalkNodeOutputsProvider<T> outputsProvider, bool expandSideBranches = false, int? maxDepth, })

Returns the walk order of nodes.

Implementation

List<Node<T>> walkOrder(
  List<T> roots, {
  required GraphWalkNodeProvider<T> nodeProvider,
  required GraphWalkNodeOutputsProvider<T> outputsProvider,
  bool expandSideBranches = false,
  int? maxDepth,
}) {
  maxDepth ??= defaultMaxDepth;

  final walkOrder = <Node<T>>{};

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

  var rootNodes = roots.map((e) {
    var rootStep = GraphValueStep.root(this, e);
    return nodeProvider(rootStep, e) ??
        (throw ArgumentError("Root not present in graph: $e"));
  }).toList();

  if (sortByInputDependency) {
    rootNodes = rootNodes.sortedByInputDependency();
  }

  queue.addAll(rootNodes.toGraphRootStep(this));

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

    var processCount = processed.increment(node);

    if (processCount <= maxExpansion && step.depth <= maxDepth) {
      if (processRoots || step.isNotRoot) {
        walkOrder.add(node);
      }

      if (stopMatcher.matchesNode(node)) {
        break;
      }

      List<Node<T>>? sideBranches;
      if (expandSideBranches) {
        sideBranches = _computeSideBranch(node, processed);
        if (sortByInputDependency) {
          sideBranches = sideBranches.sortedByInputDependency();
        }
      }

      var outputs = outputsProvider(step, node);
      if (sortByInputDependency) {
        outputs = outputs?.sortedByInputDependency();
      }

      var nextStepsSideBranch =
          sideBranches?.toGraphNodeStep(step, sideBranch: true);
      var nextStepsOutputs = outputs?.toGraphNodeStep(step);

      queue.addAllToScanQueue2(nextStepsSideBranch, nextStepsOutputs, bfs);
    }
  }

  return walkOrder.toList();
}