Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I've written an iterative version for DFS. For a quick overview of the benchmark results for a complete graph:

enter image description here

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.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.