leetcode day 30: clone a graph

Given a graph, clone it and return it with all links intact.

I chose to use a caching crawl of the graph, and then reconstruct the new graph from the cache.

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */


func cloneGraph(node *Node) *Node {
    // need to crawl the graph and make sure we've visited all
    // the nodes, saving the connections at each node. Once we
    // have all the nodes and connections, we can rebuild the
    // graph.

    // start at the first node. add it to the queue.
    // while the queue is not empty:
    //  - pull the next item
    //  - if this node is not in the map, add it, and add all the
    //    values from the nodes it links to as the adjacency list.
    //  - for each node in the adjacency list:
    //      if the node is not in the map, add it to the queue
    //         to be explored
    if node == nil {
        return nil
    }

    rootNodeVal := node.Val  // will be used to find and return new root

    queue := []*Node{node}
    // adjacency list for scanned nodes:
    //   key is node pointer
    //   value is list of adjacent nodes
    adj := map[*Node][]*Node{}

    for len(queue) != 0 {
        item := queue[0]
        if len(queue) == 1 {
            queue = []*Node{} // empty it
        } else {
            queue = queue[1:]
        }
        for _,neighbor := range(item.Neighbors) {
            if _, ok := adj[neighbor]; !ok {
                // not visited, add to queue
                queue = append(queue, neighbor)
            }
        }
        adj[item] = item.Neighbors
    }

    // all nodes crawled. each entry in the map is a node address ->
    // list of neighbors.
    
    type task struct {
        from int
        to int
    }

    valToNode := map[int]*Node{}
    linkTasks := []task{}
    for nodeptr, neighbors := range(adj) {
        // we have a pointer to the old node, and all the things it points to.
        // - allocate a new node and record it.
        n := &Node{
            Val: nodeptr.Val,
            Neighbors: []*Node{},
        }
        valToNode[nodeptr.Val] = n
        for _,linkedNode := range(neighbors) {
            if target, ok := valToNode[linkedNode.Val]; ok {
                // Node has been reallocated, link it
                n.Neighbors = append(n.Neighbors, target)
            } else {
                // not allocated yet, add link task for it
                linkTasks = append(linkTasks, task{from:n.Val, to:linkedNode.Val})
            }
        }
    }
    fmt.Println(valToNode)
    // At this point we have allocated all the nodes, but have links
    // left to handle in the queue. for each item in the queue:
    //    - look up the from and to nodes in the map
    //    - append a link to the 'to' node to the 'from' node's link list.
    // when the queue is empty, the links have been built, and we're done.
    for _,task := range(linkTasks) {
        fmt.Println(task.from, task.to)
        fmt.Println(valToNode[task.from])
        fmt.Println(valToNode[task.to])
        fromNode := valToNode[task.from]
        toNode := valToNode[task.to]
        fromNode.Neighbors = append(fromNode.Neighbors, toNode)
    }
    // return the root node.
    return valToNode[rootNodeVal]
}

Works, but slow: 32nd percentile runtime, 8th percentile memory. So there must be some tricks here. (Betting on arrays instead of maps.) Yes, I’ve overengineered it: there are 100 nodes at max, and the node.Val willl be 1-100. SO I can allocate an array instead of a map for my valToNode map. Let’s try that first and see how much speed we get…absolutely none! Exactly the same performance!

Well. What else can I do to speed this up? All right, let’s make the initial adjacency computation just store the integer node values. Since these are unique per node, and we have 100 or less, we can make that [][]int and see what happens.

Had a little trouble that I tracked down to the queue drop getting lost in the adjacency computation. Once that was back in, it worked fine, and now is perfectly acceptable: 78th percentile CPU. Memory still sucky, but I’ll take it.