Graph Theory: Eulerian Path & Circuit Detection with Path Finding Algorithm

eulerian_path_checker.py

from collections import defaultdict, deque

def is_eulerian_possible(nodes, undirected_edges):
    """
    Check if an undirected graph has an Eulerian path or circuit.
    
    Args:
        nodes: List of node names
        undirected_edges: List of tuples representing edges
    
    Returns:
        tuple: (has_eulerian_path, has_eulerian_circuit, path_type)
    """
    print("=== Building graph and computing degrees ===")
    
    # Build adjacency list representation
    graph = defaultdict(list)
    degree = {node: 0 for node in nodes}
    
    # Add edges and update degrees
    for u, v in undirected_edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1
        print(f"Added edge ({u}, {v}). Now degree[{u}] = {degree[u]}, degree[{v}] = {degree[v]}")
    
    print("\n=== Degree summary ===")
    odd_degree_vertices = []
    for node in nodes:
        print(f"Vertex {node}: degree = {degree[node]}")
        if degree[node] % 2 == 1:
            odd_degree_vertices.append(node)
    
    print(f"Odd-degree vertices ({len(odd_degree_vertices)}): {odd_degree_vertices}")
    
    # Check connectivity (necessary condition)
    if not is_connected(graph, nodes):
        print("Graph is not connected. No Eulerian path or circuit possible.")
        return False, False, "disconnected"
    
    # Determine Eulerian properties
    num_odd = len(odd_degree_vertices)
    
    if num_odd == 0:
        print("✓ All vertices have even degree. Eulerian circuit exists!")
        return True, True, "circuit"
    elif num_odd == 2:
        print(f"✓ Exactly 2 vertices have odd degree ({odd_degree_vertices[0]}, {odd_degree_vertices[1]}). Eulerian path exists!")
        return True, False, "path"
    else:
        print(f"✗ {num_odd} vertices have odd degree. No Eulerian trail or circuit possible.")
        return False, False, "none"

def is_connected(graph, nodes):
    """Check if the graph is connected using BFS."""
    if not nodes:
        return True
    
    visited = set()
    queue = deque([nodes[0]])
    visited.add(nodes[0])
    
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return len(visited) == len(nodes)

def find_eulerian_path(graph, nodes, start_node=None):
    """
    Find an Eulerian path using Hierholzer's algorithm.
    """
    # Create a copy of the graph to modify
    graph_copy = defaultdict(list)
    for node in graph:
        graph_copy[node] = graph[node].copy()
    
    # Determine starting node
    odd_vertices = [node for node in nodes if len(graph[node]) % 2 == 1]
    
    if len(odd_vertices) == 2:
        start = start_node if start_node in odd_vertices else odd_vertices[0]
    elif len(odd_vertices) == 0:
        start = start_node if start_node else nodes[0]
    else:
        return None  # No Eulerian path exists
    
    # Hierholzer's algorithm
    stack = [start]
    path = []
    
    while stack:
        current = stack[-1]
        if graph_copy[current]:
            next_node = graph_copy[current].pop()
            graph_copy[next_node].remove(current)
            stack.append(next_node)
        else:
            path.append(stack.pop())
    
    # Calculate total number of edges
    total_edges = sum(len(edges) for edges in graph.values()) // 2
    expected_path_length = total_edges + 1
    
    return path[::-1] if len(path) == expected_path_length else None

# Test the original example
if __name__ == "__main__":
    # Your original graph
    nodes = ['a', 'b', 'c', 'd']
    edges = [('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]
    
    print("=== Original Graph Analysis ===")
    path_exists, circuit_exists, path_type = is_eulerian_possible(nodes, edges)
    
    print(f"\nResult: {path_type}")
    if path_exists:
        print("Finding Eulerian path...")
        # Build graph for path finding
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        eulerian_path = find_eulerian_path(graph, nodes)
        if eulerian_path:
            print(f"Eulerian path: {' -> '.join(eulerian_path)}")
    
    print("\n" + "="*50)
    
    # Test with a graph that has Eulerian path
    print("=== Example with Eulerian Path ===")
    nodes2 = ['a', 'b', 'c', 'd']
    edges2 = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('b', 'd')]  # Only a and c have odd degree
    
    path_exists2, circuit_exists2, path_type2 = is_eulerian_possible(nodes2, edges2)
    if path_exists2:
        graph2 = defaultdict(list)
        for u, v in edges2:
            graph2[u].append(v)
            graph2[v].append(u)
        
        eulerian_path2 = find_eulerian_path(graph2, nodes2)
        if eulerian_path2:
            print(f"Eulerian path: {' -> '.join(eulerian_path2)}")
    
    print("\n" + "="*50)
    
    # Test with a graph that has Eulerian circuit
    print("=== Example with Eulerian Circuit ===")
    nodes3 = ['a', 'b', 'c', 'd']
    edges3 = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'a'), ('a', 'c')]  # All vertices have even degree
    
    path_exists3, circuit_exists3, path_type3 = is_eulerian_possible(nodes3, edges3)
    if path_exists3:
        graph3 = defaultdict(list)
        for u, v in edges3:
            graph3[u].append(v)
            graph3[v].append(u)
        
        eulerian_path3 = find_eulerian_path(graph3, nodes3)
        if eulerian_path3:
            print(f"Eulerian circuit: {' -> '.join(eulerian_path3)}")