Graph (adjacency list) for BFS and DFS in Golang

Question

I am trying to implement a Graph data structure in Golang and choose to use adjacency list representation. When starting to implement adjacency list, I have an idea that if I use map instead of list. I think (not sure though) this is much much easier to implement and I can find element in \$O(1)\$ rather using \$O(n)\$. I hope anyone can help review my code and the correct way to do adjacency graph.

I try to make it general by declaring payload as a new Interface type which needs a Compare() method to use in BFS and DFS later on.

type Graph struct {
 nodes map[int]Node
}
type Node struct {
 payload Interface
 adjNodes map[int]struct{}
}
func (g *Graph) addNode(key int, payload Interface) {
 if _, ok := g.nodes[key]; ok {
 return
 }
 g.nodes[key] = Node{payload: payload, adjNodes: make(map[int]struct{})}
}
func (g *Graph) addEdge(src, dst int) {
 // expand if no this node in graph
 if src < 0 || dst < 0 {
 panic("Node number can't be below 0")
 }
 // check if node exists
 if _, ok := g.nodes[src]; !ok {
 panic("No node " + string(src))
 }
 if _, ok := g.nodes[dst]; !ok {
 panic("No node " + string(dst))
 }
 // connect by adjacent list
 g.nodes[src].adjNodes[dst] = struct{}{}
 g.nodes[dst].adjNodes[src] = struct{}{}
}

Answer 1

I don't know Go so I'll limit this to a more general review. If I recommend non-standard things, please point them out so someone else doesn't pick up bad habits. :)

Unless the error result is always named ok in Go, I would prefer found in the cases where you are searching for a node by key to clarify its meaning.

A comment in addEdge says missing nodes will be created automatically ("make new node if doesn't have one"), but the code doesn't match. The problem is that there's no payload for the new node(s).

The graph will let you add nodes to which you cannot attach edges. Move the key checking to a new getNode method, and call it from addNode and addEdge.

func (g *Graph) addNode(key int, payload Interface) {
 if node, found := g.getNode(key); !found {
 node = Node{payload: payload, adjNodes: make(map[int]struct{})}
 g.nodes[key] = node
 }
 return node
}
func (g *Graph) getNode(key int) {
 if key < 0 {
 panic("Node key can't be negative")
 }
 if node, found := g.nodes[key]; !found {
 panic("Node key not found")
 }
 return node
}
func (g *Graph) addEdge(src, dst int) {
 if srcNode, found := g.getNode(src); !found {
 panic("No node " + string(src))
 }
 if dstNode, found := g.getNode(dst); !found {
 panic("No node " + string(dst))
 }
 // connect by adjacent list
 srcNode.adjNodes[dst] = struct{}{}
 dstNode.adjNodes[src] = struct{}{}
}

Map vs. List

To your comment, since the caller is free to use sparse keys, e.g., 1, 29187, 23957172, 6832, 4772589, etc., the map (assuming it's a hash map under the hood) will give you \$O(1)\$ access for the most part.

If you were to assign the keys as indices into a list in addNode and return the new key, you could use a list instead. I don't know how Go's internal map and list are implemented, but I assume it must provide some sort of growable array class. If not, they aren't difficult to build.

As a user, I would prefer to have the graph assign the keys for me.

• A-letubby: Sorry, when I was coding, I though of making a new node if add edge cannot find one. But in the end, I don't do it and still have the old comments. I updated the code.
• A-letubby: Also, how do you think about between using map and list for adjacency list?
• David Harkness: @A-letubby See the update at the end of my answer.