computeRoutes method

DistanceVectorRoutingTable<T> computeRoutes(Map<T, Map<T, num>> network, T sourceNode, { Map<T, NeighborAdvertisement<T>>? initialAdvertisements, })

Computes complete routing table using distance-vector algorithm

network - Network topology as adjacency list sourceNode - Source node for routing table computation initialAdvertisements - Optional initial neighbor advertisements

Returns complete routing table with optimal paths

Throws ArgumentError if source node doesn't exist in network

Implementation

DistanceVectorRoutingTable<T> computeRoutes(
  Map<T, Map<T, num>> network,
  T sourceNode, {
  Map<T, NeighborAdvertisement<T>>? initialAdvertisements,
}) {
  // Input validation
  if (!network.containsKey(sourceNode)) {
    throw ArgumentError('Source node $sourceNode not found in network');
  }

  // Initialize routing table with direct connections
  final routes = <T, DistanceVectorRouteEntry<T>>{};
  final neighborAds = <T, NeighborAdvertisement<T>>{};
  final now = DateTime.now();

  // Add source node to itself
  routes[sourceNode] = DistanceVectorRouteEntry<T>(
    destination: sourceNode,
    nextHop: null,
    cost: 0,
    lastUpdate: now,
    isDirectlyConnected: true,
    advertisingNeighbor: sourceNode,
    hopCount: 0,
    attributes: {'timeout': routeTimeout},
  );

  // Add directly connected neighbors
  final directNeighbors = network[sourceNode]!;
  for (final neighbor in directNeighbors.keys) {
    final cost = directNeighbors[neighbor]!;
    final route = DistanceVectorRouteEntry<T>(
      destination: neighbor,
      nextHop: neighbor,
      cost: cost,
      lastUpdate: now,
      isDirectlyConnected: true,
      advertisingNeighbor: neighbor,
      hopCount: 1,
      attributes: {'timeout': routeTimeout},
    );

    routes[neighbor] = route;

    // Create initial neighbor advertisement with their known destinations
    // In distance-vector routing, neighbors advertise their reachable destinations
    final neighborDestinations = <T, num>{neighbor: 0};

    // Add only nodes that this neighbor can actually reach
    for (final node in network.keys) {
      if (node != sourceNode && node != neighbor) {
        // Only include nodes that are directly connected to this neighbor
        if (network[neighbor]!.containsKey(node)) {
          neighborDestinations[node] = network[neighbor]![node]!;
        }
        // Don't include disconnected nodes
      }
    }

    neighborAds[neighbor] = NeighborAdvertisement<T>(
      neighbor: neighbor,
      distanceVector: neighborDestinations,
      timestamp: now,
      sequenceNumber: 1,
      metadata: {'maxAge': routeTimeout},
    );
  }

  // Add initial advertisements if provided
  if (initialAdvertisements != null) {
    neighborAds.addAll(initialAdvertisements);
  }

  // Distance-vector routing computation using Bellman-Ford
  // For simplicity, we'll use a direct shortest path computation
  // that simulates what distance-vector routing should achieve

  // Initialize all nodes with maximum cost
  final distances = <T, num>{};
  final previous = <T, T?>{};
  for (final node in network.keys) {
    distances[node] = _maxCost;
    previous[node] = null;
  }
  distances[sourceNode] = 0;

  // Bellman-Ford algorithm
  for (int iteration = 0; iteration < network.length - 1; iteration++) {
    bool hasChanges = false;

    for (final source in network.keys) {
      for (final target in network[source]!.keys) {
        final sourceCost = distances[source]!;
        final linkCost = network[source]![target]!;
        final totalCost = sourceCost + linkCost;

        if (totalCost < distances[target]!) {
          distances[target] = totalCost;
          previous[target] = source;
          hasChanges = true;
        }
      }
    }

    if (!hasChanges) break;
  }

  // Build routes from computed distances
  for (final node in network.keys) {
    if (node == sourceNode) {
      // Self-route already exists
      continue;
    }

    if (distances[node]! < _maxCost) {
      // Build path to this node
      final path = <T>[node];
      T? current = node;

      while (previous[current] != null) {
        current = previous[current] as T;
        if (current != null) {
          path.insert(0, current);
        }
      }

      final nextHop = path.length > 1 ? path[1] : null;
      final isDirectlyConnected = path.length == 2;

      routes[node] = DistanceVectorRouteEntry<T>(
        destination: node,
        nextHop: nextHop,
        cost: distances[node]!,
        lastUpdate: now,
        isDirectlyConnected: isDirectlyConnected,
        advertisingNeighbor: nextHop ?? node,
        hopCount: path.length - 1,
        attributes: {'timeout': routeTimeout},
      );
    }
  }

  // Apply split horizon and poison reverse if enabled
  if (enableSplitHorizon) {
    _applySplitHorizon(routes, neighborAds);
  }
  if (enablePoisonReverse) {
    _applyPoisonReverse(routes, neighborAds);
  }

  return DistanceVectorRoutingTable<T>(
    sourceNode: sourceNode,
    routes: Map.unmodifiable(routes),
    neighborAdvertisements: Map.unmodifiable(neighborAds),
    lastUpdate: now,
    totalRoutes: routes.length,
    totalNeighbors: neighborAds.length,
  );
}