Chinese Postman Problem - Standard Exact Algorithm

cpp.py

class StandardCPP(CPPSolver):
    """
    Standard Chinese Postman Algorithm for complete graphs.

    Time Complexity: O(n³) for matching, O(n²) for circuit
    Space Complexity: O(n²)

    This is an EXACT algorithm that always finds the optimal solution.
    """

    def solve(self) -> tuple[list[tuple[int, int]], float]:
        """
        Solve CPP using the standard algorithm.

        Returns:
            Tuple of (edge_path, total_cost)
        """
        # Check if graph is already Eulerian (all vertices have even degree)
        odd_vertices = []
        for v in self.nodes:
            if self.get_vertex_degree() % 2 == 1:
                odd_vertices.append(v)

        if len(odd_vertices) == 0:
            print("  Graph is already Eulerian!")
            # Build simple edge list for Eulerian circuit
            adj_simple = defaultdict(list)
            for node_i in self.nodes:
                for node_j in self.nodes:
                    if node_i != node_j:
                        adj_simple[node_i].append(node_j)

            circuit = self._find_eulerian_circuit_simple(adj_simple)
            cost = self.calculate_path_cost(circuit)
            return circuit, cost

        print(f"  Found {len(odd_vertices)} odd-degree vertices")

        # Find minimum weight perfect matching of odd vertices
        matching_edges = self._minimum_weight_matching(odd_vertices)
        print(f"  Added {len(matching_edges)} matching edges")

        # Create multigraph by adding matched edges
        augmented_adj = self._augment_graph(matching_edges)

        # Find Eulerian circuit in augmented graph
        circuit = self._find_eulerian_circuit(augmented_adj)
        cost = self.calculate_path_cost(circuit)

        return circuit, cost

    def _minimum_weight_matching(self, vertices: list[int]) -> list[tuple[int, int]]:
        """
        Find minimum weight perfect matching using dynamic programming.
        For complete graphs, we can use a simpler approach.
        """
        if len(vertices) == 0:
            return []

        # For complete Euclidean graphs, greedy matching is optimal
        matching = []
        unmatched = set(vertices)

        while len(unmatched) > 1:
            # Pick arbitrary vertex
            u = unmatched.pop()

            # Find closest unmatched vertex
            best_v = None
            best_dist = float("inf")

            for v in unmatched:
                dist = self.dist_matrix.get(
                    (u, v), self.dist_matrix.get((v, u), float("inf"))
                )
                if dist < best_dist:
                    best_dist = dist
                    best_v = v

            if best_v is not None:
                matching.append((u, best_v))
                unmatched.remove(best_v)

        return matching

    def _augment_graph(
        self, matching_edges: list[tuple[int, int]]
    ) -> dict[int, list[tuple[int, int]]]:
        """Create multigraph by adding matched edges."""
        # Use list of (neighbor, edge_id) to handle multiple edges
        augmented = defaultdict(list)
        edge_id = 0

        # Add original edges
        for i, node_i in enumerate(self.nodes):
            for j in range(i + 1, self.n):
                node_j = self.nodes[j]
                augmented[node_i].append((node_j, edge_id))
                augmented[node_j].append((node_i, edge_id))
                edge_id += 1

        # Add matching edges (duplicates)
        for u, v in matching_edges:
            augmented[u].append((v, edge_id))
            augmented[v].append((u, edge_id))
            edge_id += 1

        return dict(augmented)

    def _find_eulerian_circuit(
        self, adj_list: dict[int, list[tuple[int, int]]]
    ) -> list[tuple[int, int]]:
        """Find Eulerian circuit using Hierholzer's algorithm."""
        if not adj_list:
            return []

        # Start from first node
        curr_path = [self.nodes[0]]
        circuit = []
        edges_used = set()

        while curr_path:
            curr = curr_path[-1]

            # Find unused edge from current vertex
            found_edge = False
            if curr in adj_list:
                for neighbor, edge_id in list(adj_list[curr]):
                    if edge_id not in edges_used:
                        curr_path.append(neighbor)
                        edges_used.add(edge_id)

                        # Remove edge from both directions
                        adj_list[curr].remove((neighbor, edge_id))
                        adj_list[neighbor].remove((curr, edge_id))

                        found_edge = True
                        break

            if not found_edge:
                # Backtrack
                if len(curr_path) > 1:
                    v = curr_path.pop()
                    u = curr_path[-1] if curr_path else 0
                    circuit.append((u, v))
                else:
                    curr_path.pop()

        return circuit

    def _find_eulerian_circuit_simple(
        self, adj: dict[int, list[int]]
    ) -> list[tuple[int, int]]:
        """Simple Eulerian circuit for when graph is already Eulerian."""
        if not adj:
            return []

        stack = [self.nodes[0]]
        circuit = []

        while stack:
            curr = stack[-1]
            if curr in adj and adj[curr]:
                next_v = adj[curr].pop()
                # Remove reverse edge for undirected graph
                if next_v in adj and curr in adj[next_v]:
                    adj[next_v].remove(curr)
                stack.append(next_v)
            else:
                if len(stack) > 1:
                    v = stack.pop()
                    circuit.append((stack[-1], v))
                else:
                    stack.pop()

        return circuit