Tri-Color Marking Algorithm in Go
This challenge asks you to implement the Tri-Color Marking algorithm, a fundamental technique used in garbage collection in programming languages like Go. The algorithm efficiently identifies reachable objects in a graph, allowing for the collection of unreachable (garbage) objects. Your task is to implement the core marking logic.
Problem Description
You are given a graph represented as an adjacency list, where nodes are identified by integers. Each node can be in one of three states: White (unvisited), Gray (currently being visited), or Black (visited and all its descendants have been visited). The Tri-Color Marking algorithm starts with all nodes as White. It then performs a depth-first search (DFS) to mark reachable nodes. White nodes are marked Gray when first visited, and then their descendants are recursively marked. Once all descendants of a Gray node have been marked, the node itself is marked Black. The goal is to implement the marking phase of this algorithm.
Key Requirements:
- Graph Representation: The graph will be represented as a
map[int][]int, where the key is a node ID and the value is a slice of node IDs representing its neighbors. - Node States: Use an integer to represent node states: 0 for White, 1 for Gray, and 2 for Black.
- Marking Function: Implement a function
Mark(graph map[int][]int, startNode int, colors map[int]int)that performs the Tri-Color Marking algorithm starting from a givenstartNode. - Color Map: The
colorsmap will store the current color of each node. It is initialized with all nodes as White (0). - Reachability: The algorithm should correctly identify and mark all nodes reachable from the
startNode.
Expected Behavior:
After calling Mark, the colors map should reflect the following:
- The
startNodeand all nodes reachable from it should be marked Black (2). - All other nodes should remain White (0).
- No node should be Gray (1) after the marking process is complete.
Edge Cases to Consider:
- Disconnected Graph: The graph may not be fully connected. Only nodes reachable from the
startNodeshould be marked. - Cycles: The graph may contain cycles. The algorithm should handle cycles correctly without infinite recursion.
- Start Node Not in Graph: If the
startNodeis not present in the graph, the function should return without modifying thecolorsmap. - Empty Graph: If the graph is empty, the function should return without modifying the
colorsmap.
Examples
Example 1:
Input: graph = map[int][]int{0: {1, 2}, 1: {2}, 2: {0, 3}, 3: {3}}, startNode = 2, colors = map[int]int{0: 0, 1: 0, 2: 0, 3: 0}
Output: colors = map[int]int{0: 0, 1: 0, 2: 2, 3: 2}
Explanation: Starting from node 2, we visit 0, 1, and 3. All these nodes and 2 are marked Black.
Example 2:
Input: graph = map[int][]int{0: {1}, 1: {2}, 2: {0}}, startNode = 0, colors = map[int]int{0: 0, 1: 0, 2: 0}
Output: colors = map[int]int{0: 2, 1: 2, 2: 2}
Explanation: Starting from node 0, we visit 1 and 2, forming a cycle. All nodes in the cycle are marked Black.
Example 3:
Input: graph = map[int][]int{0: {1}, 2: {3}}, startNode = 0, colors = map[int]int{0: 0, 1: 0, 2: 0, 3: 0}
Output: colors = map[int]int{0: 2, 1: 2, 2: 0, 3: 0}
Explanation: Starting from node 0, we visit 1. Node 2 and 3 are disconnected and remain White.
Constraints
- The number of nodes in the graph will be between 0 and 1000.
- The number of edges in the graph will be between 0 and 10000.
- Node IDs will be non-negative integers.
- The algorithm should complete within 1 second for graphs of the specified size.
Notes
- Consider using recursion to implement the depth-first search.
- Be careful to avoid infinite loops when handling cycles. The Gray/Black coloring scheme is crucial for this.
- The
colorsmap is passed by reference, so modifications within theMarkfunction will be reflected in the caller's map. - Focus on the core marking logic; you don't need to implement garbage collection itself. Just mark the reachable nodes.
- Error handling (e.g., invalid node IDs) is not required for this challenge.