Skip to content
TheChatArchiveThe Chat Archive
GLMGLM-5 / Pony Alpha· unknownHugging Face Frontier Reasoning Traces

Write a function to detect a cycle in a directed graph

  1. User

    Write a function to detect a cycle in a directed graph

  2. GLM Assistant

    1. Understand the Goal: The user wants a function to detect a cycle in a directed graph.

    1. Identify the Core Concepts:

      • Directed Graph: A set of vertices (nodes) and edges where edges have a direction (u -> v is different from v -> u).
      • Cycle: A path that starts and ends at the same vertex (e.g., A -> B -> C -> A).
      • Algorithms: How do we find cycles?
        • Depth First Search (DFS): The most common and intuitive approach. If we encounter a node that is currently "in progress" (being visited in the current recursion stack), we found a back edge, which means a cycle.
        • Topological Sort (Kahn's Algorithm): If we can't topologically sort the whole graph (i.e., some nodes remain unprocessed because their in-degree never becomes zero), there's a cycle. This works for DAGs (Directed Acyclic Graphs).
        • Union-Find (Disjoint Set Union): Generally works well for undirected graphs. For directed graphs, it's trickier and less standard unless the graph is treated in a specific way, so usually DFS or Kahn's is preferred.
    2. Select the Best Approach:

      • DFS (Recursive): Very clean implementation. Uses a visited set and an in_stack (or recursion_stack) set.
      • DFS (Iterative): Doable, but usually requires manual stack management and state tracking (visiting vs visited).
      • Kahn's Algorithm: Good if you also need a topological sort, but strictly for detection, DFS is often slightly more memory efficient for sparse graphs or easier to code recursively.

      Decision: I will provide the DFS approach as the primary solution because it's the standard interview answer. I'll also mention or provide the Kahn's Algorithm approach as an alternative because it avoids recursion depth issues.

    3. Drafting the DFS Solution:

      • Input: Graph representation. Usually an adjacency list (dictionary/hash map mapping node to list of neighbors).
      • State Tracking:
        • visited: Keeps track of nodes completely processed.
        • recursion_stack (or visiting): Keeps track of nodes in the current DFS path.
      • Logic:
        1. Start DFS from every unvisited node (to handle disconnected components).
        2. Mark current node as visited and add to recursion_stack.
        3. For each neighbor:
          • If neighbor in recursion_stack: CYCLE FOUND.
          • If neighbor not in visited: Recurse.
        4. Remove node from recursion_stack before returning.
      • Time Complexity: O(V+E)O(V + E) where VV is vertices and EE is edges.
      • Space Complexity: O(V)O(V) for sets and recursion stack.
    4. Drafting the Code (Python):

      def has_cycle(graph):
          visited = set()
          recursion_stack = set()
      
          def dfs(node):
              visited.add(node)
              recursion_stack.add(node)
      
              for neighbor in graph.get(node, []):
                  if neighbor in recursion_stack:
                      return True # Cycle detected
                  if neighbor not in visited:
                      if dfs(neighbor):
                          return True
      
              recursion_stack.remove(node)
              return False
      
          # Need to iterate over all nodes in case of disconnected graph
          for node in graph:
              if node not in visited:
                  if dfs(node):
                      return True
          return False
      
    5. Refining the Explanation:

      • The code alone isn't enough. I need to explain why it works.
      • Mention the concept of "colors" (White/Gray/Black) often used in algorithms (White=unvisited, Gray=visiting, Black=visited). My approach uses two sets (visited is Black, recursion_stack is Gray).
      • Handle the edge case where the graph dictionary might not contain a node key if it has no outgoing edges.
    6. Drafting the Kahn's Algorithm (BFS) Solution (Optional but good for completeness):

      • Count in-degrees of all vertices.
      • Push all vertices with 0 in-degree into a queue.
      • Process queue: pop node, reduce in-degree of neighbors.
      • If neighbor in-degree becomes 0, push to queue.
      • Count processed nodes. If count < total nodes, cycle exists.
    7. Structuring the Final Output:

      • Introduction: Briefly explain the concept (back edges).
      • Approach 1: DFS (Recursive): The standard approach.
        • Code snippet.
        • Explanation of visited vs recursion_stack.
        • Complexity analysis.
      • Approach 2: Kahn's Algorithm (Topological Sort): The iterative approach.
        • Code snippet.
        • Explanation.
        • Complexity analysis.
      • Comparison: When to use which (Recursion limit vs iteration).
    8. Review and Self-Correction:

      • Check: Does the DFS code handle a graph where a node key exists but points to nothing? Yes, graph.get(node, []) handles it, or simply iterating keys.
      • Check: Does it handle disconnected components? Yes, the outer loop for node in graph ensures all components are visited.
      • Refinement: Make sure the input format is clear (dictionary).
    9. Final Polish: (Produce the actual response based on these steps.) Here are two common approaches to solving this problem: Depth First Search (DFS) and Kahn's Algorithm (Topological Sort).

    Approach 1: Depth First Search (DFS)

    This is the most standard approach. We use a recursion stack to keep track of the path currently being traversed.

    The Logic:

    1. We maintain two sets (or arrays):
      • visited: Tracks nodes that have been processed completely.
      • recursion_stack: Tracks nodes currently in the current DFS path.
    2. For every unvisited node, we start a DFS.
    3. We mark the node as visited and add it to the recursion_stack.
    4. We visit all neighbors. If a neighbor is found in the recursion_stack, a cycle exists (this is called a "Back Edge").
    5. Before backtracking (returning from the function), we remove the node from the recursion_stack.

    Python Implementation:

    def has_cycle_dfs(graph):
        """
        Detects a cycle in a directed graph using DFS.
        
        Args:
            graph (dict): Adjacency list {node: [neighbors]}
            
        Returns:
            bool: True if cycle exists, False otherwise.
        """
        visited = set()
        recursion_stack = set()
    
        def dfs(node):
            visited.add(node)
            recursion_stack.add(node)
    
            # Visit neighbors
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True
                # If the neighbor is in the recursion stack, we found a back edge
                elif neighbor in recursion_stack:
                    return True
    
            # Backtrack: remove node from current path
            recursion_stack.remove(node)
            return False
    
        # Check all nodes (handles disconnected graphs)
        for node in graph:
            if node not in visited:
                if dfs(node):
                    return True
    
        return False
    
    # Example Usage:
    graph_with_cycle = {
        'A': ['B'],
        'B': ['C'],
        'C': ['A'] # Cycle: A -> B -> C -> A
    }
    
    graph_without_cycle = {
        'A': ['B'],
        'B': ['C'],
        'C': []
    }
    
    print(f"Has Cycle (DFS): {has_cycle_dfs(graph_with_cycle)}")      # True
    print(f"Has Cycle (DFS): {has_cycle_dfs(graph_without_cycle)}")   # False
    

    Approach 2: Kahn's Algorithm (Topological Sort)

    This approach is useful if you want to avoid recursion or need a topological ordering of the graph. It works by counting incoming edges (in-degree).

    The Logic:

    1. Compute the in-degree (number of incoming edges) for every node.
    2. Add all nodes with in-degree == 0 to a queue.
    3. While the queue is not empty:
      • Remove a node (let's call it u).
      • Decrement the in-degree of u's neighbors.
      • If a neighbor's in-degree becomes 0, add it to the queue.
      • Count the number of nodes processed.
    4. If the count of processed nodes equals the total number of nodes, the graph is a Directed Acyclic Graph (DAG). If the count is less, there is a cycle.

    Python Implementation:

    from collections import deque, defaultdict
    
    def has_cycle_kahns(graph):
        """
        Detects a cycle using Kahn's Algorithm (Topological Sort).
        """
        # 1. Calculate in-degrees
        in_degree = defaultdict(int)
        all_nodes = set(graph.keys())
        
        # Ensure nodes with no outgoing edges are in the set
        for neighbors in graph.values():
            for node in neighbors:
                all_nodes.add(node)
                in_degree[node] += 1
                
        # Initialize queue with nodes having 0 in-degree
        queue = deque([node for node in all_nodes if in_degree[node] == 0])
        count = 0
    
        while queue:
            u = queue.popleft()
            count += 1
    
            for neighbor in graph.get(u, []):
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
    
        # If count != total nodes, cycle exists
        return count != len(all_nodes)
    
    # Example Usage:
    print(f"Has Cycle (Kahn's): {has_cycle_kahns(graph_with_cycle)}")    # True
    print(f"Has Cycle (Kahn's): {has_cycle_kahns(graph_without_cycle)}") # False
    

    Comparison

    FeatureDFS ApproachKahn's Algorithm
    MethodRecursive (usually)Iterative (Queue-based)
    ComplexityO(V+E)O(V + E)O(V+E)O(V + E)
    Best Use CaseSimple implementation, usually faster constant factor.Useful if you need to detect cycles and perform a topological sort simultaneously.
    DrawbackRecursion depth can hit limits on massive graphs.Requires calculating in-degrees for all nodes first.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.