shortestPathBfs method

List<String>? shortestPathBfs(String startId, String endId, { String? edgeType, })

Finds the shortest directed path from startId to endId using BFS.

Returns a list of node ids from start to end, or null if unreachable. When edgeType is provided only edges of that type are traversed.

Implementation

List<String>? shortestPathBfs(
  String startId,
  String endId, {
  String? edgeType,
}) {
  requireNonEmpty(startId, 'startId');
  requireNonEmpty(endId, 'endId');

  if (!_nodes.containsKey(startId) || !_nodes.containsKey(endId)) {
    return null;
  }
  if (startId == endId) {
    return <String>[startId];
  }

  final Queue<String> queue = Queue<String>()..add(startId);
  final Map<String, String?> previous = <String, String?>{startId: null};

  while (queue.isNotEmpty) {
    final String current = queue.removeFirst();
    for (final TaeraeEdge edge in outgoing(current, type: edgeType)) {
      final String nextNodeId = edge.to;
      if (previous.containsKey(nextNodeId)) {
        continue;
      }

      previous[nextNodeId] = current;
      if (nextNodeId == endId) {
        return _reconstructPath(previous, endId);
      }

      queue.add(nextNodeId);
    }
  }

  return null;
}