chinesePostman<T> function

num? chinesePostman<T>(Map<T, Map<T, num>> graph)

Chinese Postman Problem (Route Inspection) for undirected graphs.

This implementation is generic and works for any node type T.

• Finds the minimum cost closed walk that visits every edge at least once.
• Returns the total cost of the optimal route, or null if the graph is not connected.

Time Complexity: O(N^3), where N is the number of nodes (due to matching).

Example:

final graph = {
  0: {1: 1, 2: 1},
  1: {0: 1, 2: 1},
  2: {0: 1, 1: 1},
};
final cost = chinesePostman(graph);
print(cost); // Minimum cost to traverse all edges

Implementation

num? chinesePostman<T>(Map<T, Map<T, num>> graph) {
  // Check if graph is connected
  void dfs(T u, Set<T> visited) {
    visited.add(u);
    for (var v in graph[u]!.keys) {
      if (!visited.contains(v)) dfs(v, visited);
    }
  }

  final visited = <T>{};
  dfs(graph.keys.first, visited);
  if (visited.length != graph.length) return null;
  // Find nodes with odd degree
  final odd = <T>[];
  for (var u in graph.keys) {
    if ((graph[u]!.length) % 2 == 1) odd.add(u);
  }
  // If all degrees are even, just sum all edge weights
  num total = 0;
  for (var u in graph.keys) {
    for (var v in graph[u]!.keys) {
      total += graph[u]![v]!;
    }
  }
  total ~/= 2; // Each edge counted twice
  if (odd.isEmpty) return total;
  // Otherwise, pair up odd degree nodes (minimum weight perfect matching)
  // Brute-force for small graphs
  num minExtra = double.infinity;
  void match(List<T> left, num cost) {
    if (left.isEmpty) {
      if (cost < minExtra) minExtra = cost;
      return;
    }
    for (int i = 1; i < left.length; i++) {
      final u = left[0], v = left[i];
      // Use Dijkstra for shortest path
      final dists = _dijkstra(graph, u);
      match([...left.sublist(1, i), ...left.sublist(i + 1)], cost + dists[v]!);
    }
  }

  match(odd, 0);
  return total + minExtra;
}