🔍 Code Extractor

function is_cyclic

Maturity: 48

Detects whether a directed graph contains a cycle using depth-first search with path tracking.

File:
/tf/active/vicechatdev/patches/util.py
Lines:
1369 - 1384
Complexity:
moderate

Purpose

This function implements cycle detection in directed graphs using a recursive depth-first search algorithm. It maintains a path set to track the current traversal path and checks if any vertex is revisited during the same path, which indicates a cycle. The algorithm is useful for dependency resolution, detecting circular references, topological sorting validation, and ensuring acyclic properties in directed graph structures.

Source Code

def is_cyclic(graph):
    """
    Return True if the directed graph g has a cycle. The directed graph
    should be represented as a dictionary mapping of edges for each node.
    """
    path = set()

    def visit(vertex):
        path.add(vertex)
        for neighbour in graph.get(vertex, ()):
            if neighbour in path or visit(neighbour):
                return True
        path.remove(vertex)
        return False

    return any(visit(v) for v in graph)

Parameters

Name Type Default Kind
graph - - positional_or_keyword

Parameter Details

graph: A dictionary representing a directed graph where keys are vertex identifiers and values are iterables (lists, tuples, sets) containing the neighbors/successors of that vertex. Empty iterables or missing keys indicate vertices with no outgoing edges. Example: {'A': ['B', 'C'], 'B': ['C'], 'C': []}

Return Value

Returns a boolean value: True if the directed graph contains at least one cycle (a path that leads back to a vertex already in the current traversal path), False if the graph is acyclic (contains no cycles).

Usage Example

# Example 1: Graph with a cycle
graph_with_cycle = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']  # Creates cycle: A -> B -> C -> A
}
result = is_cyclic(graph_with_cycle)
print(result)  # Output: True

# Example 2: Acyclic graph (DAG)
acyclic_graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
result = is_cyclic(acyclic_graph)
print(result)  # Output: False

# Example 3: Self-loop
self_loop_graph = {
    'A': ['A']  # Self-loop is a cycle
}
result = is_cyclic(self_loop_graph)
print(result)  # Output: True

# Example 4: Disconnected graph
disconnected_graph = {
    'A': ['B'],
    'B': [],
    'C': ['D'],
    'D': ['C']  # Cycle in second component
}
result = is_cyclic(disconnected_graph)
print(result)  # Output: True

Best Practices

  • Ensure the graph parameter is a dictionary with vertex keys mapping to iterable collections of neighbors
  • The function modifies the 'path' set during execution but restores it (backtracking), making it safe for reuse
  • Works with any hashable vertex identifiers (strings, integers, tuples, etc.)
  • For large graphs, consider the recursion depth limit; Python's default is typically 1000
  • The algorithm visits each vertex and edge at most once, giving O(V + E) time complexity
  • Missing vertices in the dictionary are treated as having no outgoing edges (handled by graph.get(vertex, ()))
  • The function checks all connected components, not just vertices reachable from a single starting point
  • For very deep graphs, you may need to increase recursion limit with sys.setrecursionlimit() or implement an iterative version

Tags

graph-algorithms cycle-detection directed-graph depth-first-search dfs graph-theory dependency-resolution topological-sort circular-reference acyclic dag

Similar Components

AI-powered semantic similarity - components with related functionality:

  • function sort_topologically 50.1% similar

    Performs stackless topological sorting on a directed acyclic graph (DAG), organizing nodes into levels based on their dependencies.

    From: /tf/active/vicechatdev/patches/util.py

  • function one_to_one 49.8% similar

    Validates whether a directed graph represents a one-to-one mapping by checking if each node maps to exactly one unique edge and vice versa.

    From: /tf/active/vicechatdev/patches/util.py

  • function get_dbo_establishmentcycles_with_references_establishment_dbo_establishment 41.3% similar

    Queries a Neo4j graph database to retrieve dbo_Establishment nodes that are connected to a specific dbo_EstablishmentCycles node through a REFERENCES_ESTABLISHMENT relationship.

    From: /tf/active/vicechatdev/neo4j_schema/neo4j_python_snippets.py

  • function get_all_dbo_establishmentcycles 40.3% similar

    Retrieves all nodes of type dbo_EstablishmentCycles from a Neo4j graph database with a configurable limit on the number of results returned.

    From: /tf/active/vicechatdev/neo4j_schema/neo4j_python_snippets.py

  • function get_document_approvals 40.0% similar

    Retrieves all approval cycles associated with a specific document, with optional filtering for active cycles only.

    From: /tf/active/vicechatdev/CDocs/controllers/approval_controller_bis.py
← Back to Browse