#!/usr/bin/env python3
"""
EDEN GRAPH MASTERY
Fills the graph gap - BFS, DFS, path finding, cycle detection
"""
import time
from collections import deque, defaultdict

class EdenGraph:
    """Graph with common algorithms"""
    
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
        if not self.directed:
            self.graph[v].append(u)
    
    def bfs(self, start):
        """Breadth-first search"""
        visited = set([start])
        queue = deque([start])
        order = []
        
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return order
    
    def dfs(self, start, visited=None):
        """Depth-first search"""
        if visited is None:
            visited = set()
        
        visited.add(start)
        order = [start]
        
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                order.extend(self.dfs(neighbor, visited))
        
        return order
    
    def has_path(self, start, end):
        """Check if path exists between two nodes"""
        if start == end:
            return True
        
        visited = set([start])
        queue = deque([start])
        
        while queue:
            node = queue.popleft()
            for neighbor in self.graph[node]:
                if neighbor == end:
                    return True
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return False
    
    def shortest_path(self, start, end):
        """BFS shortest path"""
        if start == end:
            return [start]
        
        visited = {start: None}
        queue = deque([start])
        
        while queue:
            node = queue.popleft()
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited[neighbor] = node
                    if neighbor == end:
                        # Reconstruct path
                        path = []
                        current = end
                        while current is not None:
                            path.append(current)
                            current = visited[current]
                        return path[::-1]
                    queue.append(neighbor)
        
        return None
    
    def has_cycle(self):
        """Detect cycle in graph"""
        visited = set()
        rec_stack = set()
        
        def dfs_cycle(node):
            visited.add(node)
            rec_stack.add(node)
            
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    if dfs_cycle(neighbor):
                        return True
                elif neighbor in rec_stack:
                    return True
            
            rec_stack.remove(node)
            return False
        
        for node in list(self.graph.keys()):
            if node not in visited:
                if dfs_cycle(node):
                    return True
        
        return False
    
    def connected_components(self):
        """Find all connected components"""
        visited = set()
        components = []
        
        for node in list(self.graph.keys()):
            if node not in visited:
                component = self.dfs(node, visited)
                components.append(component)
        
        return components


# Test
if __name__ == "__main__":
    print("🕸️ EDEN GRAPH MASTERY")
    print("="*50)
    
    # Build graph
    g = EdenGraph()
    edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
    for u, v in edges:
        g.add_edge(u, v)
    
    print(f"Graph edges: {edges}")
    
    # BFS
    start = time.perf_counter()
    bfs_order = g.bfs(0)
    latency = (time.perf_counter() - start) * 1000
    print(f"✅ BFS from 0: {bfs_order}")
    print(f"⚡ Latency: {latency:.5f} ms")
    
    # DFS
    print(f"✅ DFS from 0: {g.dfs(0)}")
    
    # Path finding
    print(f"✅ has_path(0, 4): {g.has_path(0, 4)}")
    print(f"✅ has_path(0, 9): {g.has_path(0, 9)}")
    print(f"✅ shortest_path(0, 4): {g.shortest_path(0, 4)}")
    
    # Cycle detection (directed)
    dg = EdenGraph(directed=True)
    dg.add_edge(0, 1)
    dg.add_edge(1, 2)
    dg.add_edge(2, 0)  # Creates cycle
    print(f"✅ Directed graph has_cycle: {dg.has_cycle()}")
    
    # No cycle
    dg2 = EdenGraph(directed=True)
    dg2.add_edge(0, 1)
    dg2.add_edge(1, 2)
    print(f"✅ Acyclic graph has_cycle: {dg2.has_cycle()}")