1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

from collections import defaultdict
from enum import Enum
from dataclasses import dataclass
from typing import Optional
 
class Color(Enum):
    WHITE = 0
    GRAY = 1
    BLACK = 2
 
 
@dataclass
class VertexInfo:
    """Complete DFS information for a vertex."""
    color: Color = Color.WHITE
    discovery_time: int = 0
    finish_time: int = 0
    parent: int = -1  # Parent in DFS tree
 
 
class DFSWithTimestamps:
    """
    Full DFS implementation with color marking and timestamps.
    Captures complete traversal information.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj: dict[int, list[int]] = defaultdict(list)
        self.info = [VertexInfo() for _ in range(vertices)]
        self.time = 0
        
        # Edge classification results
        self.tree_edges: list[tuple[int, int]] = []
        self.back_edges: list[tuple[int, int]] = []
        self.forward_edges: list[tuple[int, int]] = []
        self.cross_edges: list[tuple[int, int]] = []
    
    def add_edge(self, u: int, v: int) -> None:
        """Add directed edge from u to v."""
        self.adj[u].append(v)
    
    def run_dfs(self) -> None:
        """
        Execute DFS on entire graph, recording all information.
        
        After calling this method, you can access:
        - self.info[v].discovery_time, finish_time, parent
        - self.tree_edges, back_edges, forward_edges, cross_edges
        """
        self.time = 0
        
        # Reset all vertices
        for v in range(self.V):
            self.info[v] = VertexInfo()
        
        # Clear edge classifications
        self.tree_edges.clear()
        self.back_edges.clear()
        self.forward_edges.clear()
        self.cross_edges.clear()
        
        # Run DFS from each unvisited vertex
        for v in range(self.V):
            if self.info[v].color == Color.WHITE:
                self._dfs_visit(v)
    
    def _dfs_visit(self, u: int) -> None:
        """
        DFS visit with full timestamp recording and edge classification.
        """
        # Discover vertex u
        self.time += 1
        self.info[u].discovery_time = self.time
        self.info[u].color = Color.GRAY
        
        # Explore all neighbors
        for v in self.adj[u]:
            self._classify_edge(u, v)
            
            if self.info[v].color == Color.WHITE:
                # Tree edge: leads to undiscovered vertex
                self.info[v].parent = u
                self._dfs_visit(v)
        
        # Finish vertex u
        self.info[u].color = Color.BLACK
        self.time += 1
        self.info[u].finish_time = self.time
    
    def _classify_edge(self, u: int, v: int) -> None:
        """
        Classify edge (u, v) based on colors and timestamps.
        
        Called when exploring edge from u to v.
        At this point, u is GRAY (we're processing it).
        """
        v_info = self.info[v]
        
        if v_info.color == Color.WHITE:
            self.tree_edges.append((u, v))
        elif v_info.color == Color.GRAY:
            # v is being processed, so v is ancestor of u
            self.back_edges.append((u, v))
        else:  # BLACK
            u_info = self.info[u]
            if u_info.discovery_time < v_info.discovery_time:
                # v was discovered after u started but finished before u
                # So v is a descendant of u in DFS tree
                self.forward_edges.append((u, v))
            else:
                # v was completely processed before u was discovered
                # Different subtree
                self.cross_edges.append((u, v))
    
    def print_results(self) -> None:
        """Print complete DFS analysis."""
        print("\nVertex Information:")
        print("-" * 50)
        for v in range(self.V):
            info = self.info[v]
            print(f"Vertex {v}: d={info.discovery_time}, "
                  f"f={info.finish_time}, parent={info.parent}")
        
        print("\nEdge Classification:")
        print(f"  Tree edges:    {self.tree_edges}")
        print(f"  Back edges:    {self.back_edges}")
        print(f"  Forward edges: {self.forward_edges}")
        print(f"  Cross edges:   {self.cross_edges}")
        
        if self.back_edges:
            print("\n⚠️  Graph contains cycles (back edges exist)")
        else:
            print("\n✓ Graph is acyclic (DAG)")
    
    def is_ancestor(self, u: int, v: int) -> bool:
        """
        Check if u is an ancestor of v in DFS tree.
        Uses the parenthesis theorem.
        """
        u_info, v_info = self.info[u], self.info[v]
        return (u_info.discovery_time <= v_info.discovery_time and
                v_info.finish_time <= u_info.finish_time)
    
    def get_topological_order(self) -> Optional[list[int]]:
        """
        Get topological ordering if graph is acyclic.
        Vertices sorted by decreasing finish time.
        """
        if self.back_edges:
            return None  # Has cycles
        
        vertices = list(range(self.V))
        vertices.sort(key=lambda v: -self.info[v].finish_time)
        return vertices
 
 
# Example usage
if __name__ == "__main__":
    g = DFSWithTimestamps(6)
    
    # Create a graph with various edge types
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 3)  # Cross or forward depending on order
    g.add_edge(3, 4)
    g.add_edge(4, 5)
    g.add_edge(5, 3)  # Back edge - creates cycle
    
    g.run_dfs()
    g.print_results()
    
    # Check ancestry relationships
    print(f"\nIs 0 ancestor of 4? {g.is_ancestor(0, 4)}")
    print(f"Is 4 ancestor of 0? {g.is_ancestor(4, 0)}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

class AncestryOracle:
    """
    Preprocesses a graph for O(1) ancestry queries.
    """
    
    def __init__(self, vertices: int, edges: list[tuple[int, int]]):
        self.V = vertices
        self.adj: dict[int, list[int]] = {i: [] for i in range(vertices)}
        for u, v in edges:
            self.adj[u].append(v)
        
        self.discovery = [0] * vertices
        self.finish = [0] * vertices
        self.time = 0
        
        self._run_dfs()
    
    def _run_dfs(self) -> None:
        """Precompute all timestamps."""
        visited = [False] * self.V
        for v in range(self.V):
            if not visited[v]:
                self._dfs(v, visited)
    
    def _dfs(self, u: int, visited: list[bool]) -> None:
        visited[u] = True
        self.time += 1
        self.discovery[u] = self.time
        
        for v in self.adj[u]:
            if not visited[v]:
                self._dfs(v, visited)
        
        self.time += 1
        self.finish[u] = self.time
    
    def is_ancestor(self, u: int, v: int) -> bool:
        """
        O(1) check: Is u an ancestor of v in DFS tree?
        """
        return (self.discovery[u] <= self.discovery[v] and
                self.finish[v] <= self.finish[u])
    
    def is_descendant(self, u: int, v: int) -> bool:
        """Is u a descendant of v?"""
        return self.is_ancestor(v, u)
    
    def are_related(self, u: int, v: int) -> bool:
        """Is either an ancestor of the other?"""
        return self.is_ancestor(u, v) or self.is_ancestor(v, u)
    
    def subtree_size(self, u: int) -> int:
        """
        Number of vertices in subtree rooted at u.
        Uses the observation that descendants have
        discovery times in interval [d[u], f[u]].
        """
        count = 0
        for v in range(self.V):
            if (self.discovery[u] <= self.discovery[v] <= self.finish[u]):
                count += 1
        return count
    
    def get_interval(self, v: int) -> tuple[int, int]:
        """Get the [discovery, finish] interval for vertex v."""
        return (self.discovery[v], self.finish[v])
 
 
# Example: Building a tree-like structure
#      0
#     /|\
#    1 2 3
#    |   |
#    4   5
 
oracle = AncestryOracle(6, [
    (0, 1), (0, 2), (0, 3),
    (1, 4), (3, 5)
])
 
print("Intervals (discovery, finish):")
for v in range(6):
    print(f"  Vertex {v}: {oracle.get_interval(v)}")
 
print(f"\nIs 0 ancestor of 4? {oracle.is_ancestor(0, 4)}")  # True
print(f"Is 0 ancestor of 5? {oracle.is_ancestor(0, 5)}")  # True  
print(f"Is 1 ancestor of 5? {oracle.is_ancestor(1, 5)}")  # False (different subtree)
print(f"Is 4 ancestor of 1? {oracle.is_ancestor(4, 1)}")  # False (reverse)
print(f"Are 4 and 5 related? {oracle.are_related(4, 5)}")  # False (cousins)
print(f"Subtree size of 0: {oracle.subtree_size(0)}")  # 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

class EdgeApplications:
    """
    Demonstrates practical applications of DFS edge classification.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj: dict[int, list[int]] = {i: [] for i in range(vertices)}
    
    def add_edge(self, u: int, v: int):
        self.adj[u].append(v)
    
    def topological_sort(self) -> list[int] | None:
        """
        Return topological order if DAG, None if has cycles.
        Uses the fact that in a DAG, processing vertices by
        decreasing finish time gives valid topological order.
        """
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * self.V
        result = []
        
        def dfs(u: int) -> bool:
            color[u] = GRAY
            for v in self.adj[u]:
                if color[v] == GRAY:
                    return False  # Back edge - cycle!
                if color[v] == WHITE:
                    if not dfs(v):
                        return False
            color[u] = BLACK
            result.append(u)  # Add on FINISH (will reverse later)
            return True
        
        for v in range(self.V):
            if color[v] == WHITE:
                if not dfs(v):
                    return None  # Has cycle
        
        return result[::-1]  # Reverse to get decreasing finish order
    
    def find_all_cycles(self) -> list[list[int]]:
        """
        Find all simple cycles by tracking back edges and reconstructing.
        Note: This can be expensive for graphs with many cycles.
        """
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * self.V
        parent = [-1] * self.V
        cycles = []
        
        def dfs(u: int, path: list[int]):
            color[u] = GRAY
            path.append(u)
            
            for v in self.adj[u]:
                if color[v] == GRAY:
                    # Back edge! Extract cycle from path
                    idx = path.index(v)
                    cycle = path[idx:] + [v]
                    cycles.append(cycle)
                elif color[v] == WHITE:
                    parent[v] = u
                    dfs(v, path)
            
            path.pop()
            color[u] = BLACK
        
        for start in range(self.V):
            if color[start] == WHITE:
                dfs(start, [])
        
        return cycles
    
    def reachability_analysis(self) -> dict:
        """
        Analyze reachability patterns using edge classification.
        Returns statistics about the graph structure.
        """
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * self.V
        discovery = [0] * self.V
        finish = [0] * self.V
        time = 0
        
        stats = {
            'tree_edges': 0,
            'back_edges': 0,
            'forward_edges': 0,
            'cross_edges': 0,
            'root_vertices': 0,  # DFS tree roots
        }
        
        def dfs(u: int):
            nonlocal time
            time += 1
            discovery[u] = time
            color[u] = GRAY
            
            for v in self.adj[u]:
                if color[v] == WHITE:
                    stats['tree_edges'] += 1
                    dfs(v)
                elif color[v] == GRAY:
                    stats['back_edges'] += 1
                else:  # BLACK
                    if discovery[u] < discovery[v]:
                        stats['forward_edges'] += 1
                    else:
                        stats['cross_edges'] += 1
            
            color[u] = BLACK
            time += 1
            finish[u] = time
        
        for v in range(self.V):
            if color[v] == WHITE:
                stats['root_vertices'] += 1
                dfs(v)
        
        # Derive additional insights
        stats['is_dag'] = stats['back_edges'] == 0
        stats['is_tree'] = (stats['tree_edges'] == self.V - stats['root_vertices'] 
                           and stats['back_edges'] == 0 
                           and stats['forward_edges'] == 0
                           and stats['cross_edges'] == 0)
        stats['is_connected'] = stats['root_vertices'] == 1
        
        return stats
 
 
# Example usage
g = EdgeApplications(6)
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5)]
for u, v in edges:
    g.add_edge(u, v)
 
print("Topological sort:", g.topological_sort())
print("Reachability analysis:", g.reachability_analysis())
 
# Add a cycle
g.add_edge(5, 3)
print("\nAfter adding cycle 5→3:")
print("Topological sort:", g.topological_sort())
print("Cycles found:", g.find_all_cycles())
print("Reachability analysis:", g.reachability_analysis())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

from enum import Enum
from dataclasses import dataclass
 
class Color(Enum):
    WHITE = 0
    GRAY = 1
    BLACK = 2
 
class EventType(Enum):
    DISCOVER = 0  # Start processing vertex
    FINISH = 1    # Done processing vertex
 
 
@dataclass
class StackEvent:
    """Event to process from the stack."""
    event_type: EventType
    vertex: int
 
 
class IterativeDFSColors:
    """
    Iterative DFS with full three-color state tracking.
    Avoids recursion stack overflow for deep graphs.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj: dict[int, list[int]] = {i: [] for i in range(vertices)}
        self.color = [Color.WHITE] * vertices
        self.discovery = [0] * vertices
        self.finish = [0] * vertices
        self.parent = [-1] * vertices
        self.time = 0
        self.has_cycle = False
    
    def add_edge(self, u: int, v: int):
        self.adj[u].append(v)
    
    def run_dfs(self) -> None:
        """
        Execute complete DFS with iterative implementation.
        """
        self.time = 0
        self.color = [Color.WHITE] * self.V
        self.has_cycle = False
        
        for source in range(self.V):
            if self.color[source] == Color.WHITE:
                self._dfs_from(source)
    
    def _dfs_from(self, source: int) -> None:
        """
        DFS from single source using explicit stack.
        
        Key insight: Push FINISH event before DISCOVER event,
        so DISCOVER is processed first (stack is LIFO).
        When we pop DISCOVER, we push neighbor explorations.
        When we pop FINISH, we complete the vertex.
        """
        stack = [StackEvent(EventType.DISCOVER, source)]
        
        while stack:
            event = stack.pop()
            vertex = event.vertex
            
            if event.event_type == EventType.DISCOVER:
                if self.color[vertex] != Color.WHITE:
                    # Already discovered through another path
                    continue
                
                # Discover vertex (WHITE → GRAY)
                self.time += 1
                self.discovery[vertex] = self.time
                self.color[vertex] = Color.GRAY
                
                # Push FINISH event (will execute after all descendants)
                stack.append(StackEvent(EventType.FINISH, vertex))
                
                # Push neighbor explorations (in reverse for natural order)
                for neighbor in reversed(self.adj[vertex]):
                    if self.color[neighbor] == Color.WHITE:
                        self.parent[neighbor] = vertex
                        stack.append(StackEvent(EventType.DISCOVER, neighbor))
                    elif self.color[neighbor] == Color.GRAY:
                        # Back edge detected - cycle!
                        self.has_cycle = True
            
            else:  # FINISH event
                # Finish vertex (GRAY → BLACK)
                if self.color[vertex] == Color.GRAY:  # Guard against duplicates
                    self.time += 1
                    self.finish[vertex] = self.time
                    self.color[vertex] = Color.BLACK
    
    def print_state(self) -> None:
        print("\nDFS Results (Iterative):")
        print("-" * 40)
        for v in range(self.V):
            print(f"Vertex {v}: d={self.discovery[v]:2d}, "
                  f"f={self.finish[v]:2d}, parent={self.parent[v]}")
        print(f"\nHas cycle: {self.has_cycle}")
 
 
class IterativeDFSIterator:
    """
    Alternative: Iterator-based approach.
    More memory efficient as we don't duplicate events.
    """
    
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj: dict[int, list[int]] = {i: [] for i in range(vertices)}
    
    def add_edge(self, u: int, v: int):
        self.adj[u].append(v)
    
    def has_cycle(self) -> bool:
        """
        Check for cycle using iterator-based iterative DFS.
        """
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * self.V
        
        for source in range(self.V):
            if color[source] != WHITE:
                continue
            
            # Stack: (vertex, iterator over remaining neighbors)
            stack = [(source, iter(self.adj[source]))]
            color[source] = GRAY
            
            while stack:
                vertex, neighbors = stack[-1]
                
                try:
                    neighbor = next(neighbors)
                    
                    if color[neighbor] == GRAY:
                        return True  # Back edge!
                    elif color[neighbor] == WHITE:
                        color[neighbor] = GRAY
                        stack.append((neighbor, iter(self.adj[neighbor])))
                
                except StopIteration:
                    # Done with all neighbors
                    stack.pop()
                    color[vertex] = BLACK
        
        return False
 
 
# Demonstration
g = IterativeDFSColors(6)
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]
for u, v in edges:
    g.add_edge(u, v)
 
g.run_dfs()
g.print_state()
 
# Add a back edge
g.add_edge(5, 2)
g.run_dfs()
g.print_state()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

def verify_dfs_timestamps(vertices: int, discovery: list, finish: list) -> list[str]:
    """
    Verify that DFS timestamps are valid.
    Returns list of any violations found.
    """
    violations = []
    
    # Check basic bounds
    for v in range(vertices):
        if discovery[v] < 1 or discovery[v] > 2 * vertices:
            violations.append(f"Vertex {v}: invalid discovery time {discovery[v]}")
        if finish[v] < 1 or finish[v] > 2 * vertices:
            violations.append(f"Vertex {v}: invalid finish time {finish[v]}")
        if discovery[v] >= finish[v]:
            violations.append(f"Vertex {v}: discovery ({discovery[v]}) >= finish ({finish[v]})")
    
    # Check all timestamps are unique
    all_times = discovery + finish
    if len(all_times) != len(set(all_times)):
        violations.append("Duplicate timestamps found!")
    
    # Check parenthesis property: intervals must be properly nested
    for u in range(vertices):
        for v in range(u + 1, vertices):
            interval_u = (discovery[u], finish[u])
            interval_v = (discovery[v], finish[v])
            
            # Check if they overlap improperly
            if (interval_u[0] < interval_v[0] < interval_u[1] < interval_v[1] or
                interval_v[0] < interval_u[0] < interval_v[1] < interval_u[1]):
                violations.append(f"Vertices {u} and {v} have improperly overlapping intervals")
    
    return violations
 
 
def trace_dfs_execution(adj: dict, source: int = 0) -> None:
    """
    Trace DFS execution step by step for debugging.
    """
    vertices = len(adj)
    color = ['W'] * vertices  # WHITE
    discovery = [0] * vertices
    finish = [0] * vertices
    time = 0
    
    def dfs(u: int, indent: str = ""):
        nonlocal time
        time += 1
        discovery[u] = time
        color[u] = 'G'  # GRAY
        
        print(f"{indent}DISCOVER {u} at time {time}")
        print(f"{indent}  Colors: {color}")
        
        for v in adj.get(u, []):
            edge_type = ""
            if color[v] == 'W':
                edge_type = "TREE"
                dfs(v, indent + "    ")
            elif color[v] == 'G':
                edge_type = "BACK (cycle!)"
            else:
                edge_type = "CROSS/FORWARD"
            print(f"{indent}  Edge {u}→{v}: {edge_type}")
        
        color[u] = 'B'  # BLACK  
        time += 1
        finish[u] = time
        print(f"{indent}FINISH {u} at time {time}")
    
    print(f"\nDFS Trace from source {source}")
    print("=" * 50)
    
    for v in range(vertices):
        if color[v] == 'W':
            if v != source:
                print(f"\nNew tree starting at {v}")
            dfs(v)
    
    print("\nFinal timestamps:")
    for v in range(vertices):
        print(f"  Vertex {v}: d={discovery[v]}, f={finish[v]}")
    
    errors = verify_dfs_timestamps(vertices, discovery, finish)
    if errors:
        print("\nValidation FAILED:")
        for e in errors:
            print(f"  - {e}")
    else:
        print("\nValidation PASSED ✓")
 
 
# Example trace
trace_dfs_execution({
    0: [1, 2],
    1: [3],
    2: [3],
    3: [4],
    4: []
})