Implementing Tri-Color Marking in Go

Tri-color marking is a fundamental algorithm used in garbage collection and graph traversal for detecting cycles and managing memory. The goal is to classify nodes in a graph into three categories: white, gray, and black, based on their visitation status. This challenge will have you implement this marking scheme in Go.

Problem Description

Your task is to implement a function that takes a directed graph and a starting node, and performs a tri-color marking traversal. You should classify all reachable nodes from the starting node into one of three states:

• White: Unvisited nodes.
• Gray: Nodes that have been visited but their neighbors haven't been fully processed yet.
• Black: Nodes whose neighbors have all been visited and processed.

The function should return the final state of all nodes in the graph.

Key Requirements:

1. Represent the graph using an adjacency list.
2. Implement a traversal mechanism (e.g., Depth-First Search or Breadth-First Search) to visit nodes.
3. Maintain the state (white, gray, black) for each node.
4. Ensure that once a node becomes black, it remains black.
5. Return a map where keys are node identifiers and values are their final color.

Expected Behavior:

The traversal should start with all nodes being white. When a node is first encountered, it becomes gray. When all of a gray node's neighbors have been processed, it becomes black.

Edge Cases:

• An empty graph.
• A graph with no edges.
• A graph with cycles.
• A starting node that is not present in the graph (though for this problem, we'll assume the starting node is valid).

Examples

Example 1:

Input:
graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["E"],
    "D": [],
    "E": []
}
startNode = "A"

Output:
map[string]string{
    "A": "black",
    "B": "black",
    "C": "black",
    "D": "black",
    "E": "black"
}
Explanation:
1. Start with all nodes white.
2. 'A' becomes gray.
3. Visit 'B' from 'A'. 'B' becomes gray.
4. Visit 'D' from 'B'. 'D' becomes gray.
5. 'D' has no neighbors, becomes black.
6. 'B' has processed all neighbors ('D'), becomes black.
7. Visit 'C' from 'A'. 'C' becomes gray.
8. Visit 'E' from 'C'. 'E' becomes gray.
9. 'E' has no neighbors, becomes black.
10. 'C' has processed all neighbors ('E'), becomes black.
11. 'A' has processed all neighbors ('B', 'C'), becomes black.

Example 2:

Input:
graph = {
    "1": ["2"],
    "2": ["3"],
    "3": ["1", "4"],
    "4": []
}
startNode = "1"

Output:
map[string]string{
    "1": "black",
    "2": "black",
    "3": "black",
    "4": "black"
}
Explanation:
This graph contains a cycle (1 -> 2 -> 3 -> 1). The tri-color marking correctly handles cycles. All nodes reachable from '1' will eventually be marked black.

Example 3:

Input:
graph = {
    "X": ["Y"],
    "Y": [],
    "Z": [] // Unreachable node
}
startNode = "X"

Output:
map[string]string{
    "X": "black",
    "Y": "black",
    "Z": "white" // 'Z' is not reachable from 'X'
}
Explanation:
Only nodes reachable from the startNode are visited and marked. 'Z' remains unvisited (white).

Constraints

• The graph will contain up to 1000 nodes.
• Node identifiers will be strings.
• The adjacency list will be a map[string][]string.
• The startNode will be a valid key in the input graph (or the graph might be empty).
• The solution should have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.

Notes

• You can use either Depth-First Search (DFS) or Breadth-First Search (BFS) for the traversal. DFS is often more intuitive for tri-color marking due to its recursive nature.
• You will need a way to store the color of each node. A map[string]string is a good choice for this.
• Remember to initialize all nodes to "white" before starting the traversal.
• Consider how you will handle the transition from "gray" to "black". This typically happens when all descendants of a gray node have been visited.