I've written an iterative version for DFS. For a quick overview of the benchmark results for a complete graph:
So it looks like it behaves within the boundaries of the theoretical complexity.
However, being my first real program in Go, I would like to hear from you some suggestions for improvements, both at the implementation level, as well as algorithmic.
(Except making it at least partially concurrent, which will be the job of another method, not Next()
presented below)
Here is the most relevant method:
func (it *DFSIterator) Next() *Node {
//vlevel := glog.Level(1)
//glog.V(vlevel).Infoln("\n------")
topNode := it.contextStack.TopNode()
//glog.V(vlevel).Infoln("top node", topNode)
//glog.V(vlevel).Infoln("visited", it.visited.String())
//glog.V(vlevel).Infoln("stack", it.contextStack.String(), "\n-")
if nil == topNode {
return nil
}
nextNeighbour := topNode.neighbours.FirstNodeNotIn(it.visited, it.contextStack.NodeSet())
//glog.V(vlevel).Infoln("NEIGHBOURS next", nextNeighbour)
if len(it.contextStack) == 0 {
//glog.V(vlevel).Infoln("RET nil")
return nil
}
if nextNeighbour == nil {
//glog.V(vlevel).Infoln("nextNeighbour nil, returning", it.contextStack.TopNode())
popped := it.contextStack.PopNode()
//glog.V(vlevel).Infoln("popped", popped, "top", topNode)
return it.returnNode(popped)
}
if !it.visited.ContainsNode(nextNeighbour) {
it.contextStack.PushNode(nextNeighbour)
//glog.V(vlevel).Infoln("pushed, new stack", it.contextStack.String(), "\n-")
return it.returnNode(it.Next())
} else {
panic("should never happen")
}
return nil
}
(the iterators2.go
file).
The benchmark and the whole code can be found here.