linear cycle detection in a directed graph (pseudocode)

gistfile1.txt

graph data struture:{
    list-of-all-nodes
    head
}

node data structure:{
    data
    childrenList
    hasBeenSeen
}

allocateNode(graph,childrenListRef){
    node = malloc()
    graph.list-of-all-nodes = cons(node,graph.list-of-all-nodes)
    childrenListRef->add(node)
}

deleteNode(graph,node){
    //precondition, already removed it from the childrenList of it's parent node
    graph.list-of-all-nodes = remove(graph.list-of-all-nodes,node)
    free(node)
}

traverseCheck(node)->bool{
    for(child in node.childrenList){
       if(child.hasBeenSeen){
            //OH NO, CYCLE
            return TRUE //aka, it is a cycle
        }else{
            child.hasBeenSeen = TRUE
        }
    }
}

clearMarkings(graph){
    for(node in graph){
        node.hasBeenSeen = FALSE
    }
}

isCyclical(graph) ->Bool{
    clearMarkings(graph)
    for (node in graph.list-of-all-nodes) { //O(N) where N is node count
        //this is Kyle's suggestion
        if(traverseCheck(node)){
            return TRUE
        }
        
        //we also have to do the check on everything else in the list that isn't already marked...it could be a disconnected region
        if(!node.hasBeenSeen){
            for(child in node.childrenList){
                if(traverseCheck(child)){
                    return TRUE
                }
            }
        }
    }
    return FALSE
}