Documentation - v1.0.0
    Preparing search index...

    Function incident

    • Extracts the maximal R→B reachability subgraph from a directed graph.

      This function implements the R→B Reachability Subgraph algorithm, which finds the largest subgraph where every directed path starts in the red vertex set (sources) and ends in the blue vertex set (targets). The resulting subgraph satisfies:

      • Every vertex lies on at least one directed path from sources to targets
      • Source vertices have in-degree 0 (no incoming edges)
      • Target vertices have out-degree 0 (no outgoing edges)
      1. Forward Traversal: DFS from all source vertices to find vertices reachable from sources
      2. Backward Traversal: DFS from all target vertices in reversed graph to find vertices that can reach targets
      3. Intersection: Compute vertices that are both reachable from sources AND can reach targets
      4. Induced Subgraph: Create subgraph containing only intersection vertices and their connecting edges
      5. Boundary Enforcement: Remove edges violating boundary constraints (in-edges to sources, out-edges from targets)
      • Time: O(V + E) where V is vertices and E is edges
      • Space: O(V) for visited sets and intermediate storage
      • Returns empty graph if no path exists between any source and target
      • Handles cycles correctly (vertices in cycles are included if on source→target paths)
      • When a vertex is both source and target, boundary constraints may remove all edges
      • Empty source or target arrays result in empty output graph
      • Non-existent node IDs are safely ignored

      Parameters

      • graph: Graph

        The input directed graph to extract subgraph from

      • sources: `node_${string}`[]

        Array of node IDs representing source vertices (red set R)

      • targets: `node_${string}`[]

        Array of node IDs representing target vertices (blue set B)

      Returns Graph

      A new graph containing the maximal R→B reachability subgraph with:

      • Only vertices lying on source→target paths
      • No in-edges to source vertices
      • No out-edges from target vertices
      • Empty graph if no valid paths exist
      // Simple linear path: A → B → C
      const result = incident(graph, ['node_A'], ['node_C']);
      // Returns subgraph with nodes [A, B, C] and edges [A→B, B→C]

      // Multiple sources and targets: A,B → ... → D,E
      const result = incident(graph, ['node_A', 'node_B'], ['node_D', 'node_E']);
      // Returns all vertices and edges on paths from {A,B} to {D,E}

      // Disconnected components
      const result = incident(graph, ['node_A'], ['node_Z']);
      // Returns empty graph if no path exists from A to Z

      Graph Reachability

    Settings

    Member Visibility

    On This Page

    Algorithm PhasesTime ComplexityEdge Cases