1
$\begingroup$

I have a generic traversal algorithm for graphs:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
    }
}

and I want to make a time-efficient "child head count" for nodes that sets a flag for nodes whenever all their children have been visited:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        set close flag on parent nodes if last child to be visited
    }
}

The best ways that i could think of was to have pointers to "visited" booleans of the node's children and just "and" them up as such:

node1 -> [node2(true), node5(false), node7(true)]

node1.all_children_visited() = false

Or iterate through the parents whenever I visit the node for the first time:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        if first visit {
            for each parent {
                increase count
                if count(parent) = number of children {close(parent)}
            }
            if count(this) = number of children {close(this)}
        }
    }
}

Is there a way to do this with lower than O(n) complexity?

$\endgroup$
  • $\begingroup$ Do you want $o(n)$ per query if last child or for the whole traversal? $\endgroup$ – Raphael Jul 21 '14 at 15:49
  • $\begingroup$ What does close parent nodes if last child? What does it mean to close a node? The parent nodes of what? What does if last child mean? Also, what does "child head count" mean? Can you edit your question to explain this more clearly? $\endgroup$ – D.W. Jul 21 '14 at 22:25
  • 1
    $\begingroup$ It looks like you're writing a depth first search. Would you like help? $\endgroup$ – FrankW Jul 22 '14 at 4:45
  • $\begingroup$ The data structure you seem to be using appears to force all $\Omega(n)$ nodes to be visited to ensure that all of them are counted. If counting is important, then you could augment the data structure with a counter that is incremented when new a node is added and decremented when a node is removed. $\endgroup$ – András Salamon Jul 22 '14 at 12:24
  • 1
    $\begingroup$ So you're asking if you can visit $n$ nodes in less than $n$ time? $\endgroup$ – FrankW Jul 24 '14 at 17:41
2
$\begingroup$

If you can afford more memory, add a field to each node's data containing a count of already visited children. Assuming that you know the number of children, if you update this field each time you visit a child, you will know when all children have been visited.

$\endgroup$
  • $\begingroup$ Problem is whenever I do that I also have to update it for each other parent, which in turn turns into O(n) $\endgroup$ – Jean-Luc Nacif Coelho Jul 22 '14 at 12:41
  • $\begingroup$ The amortized complexity is still $O(1)$ per node. $\endgroup$ – Yuval Filmus Jul 22 '14 at 13:01
  • $\begingroup$ It's O(E) per node. $\endgroup$ – Jean-Luc Nacif Coelho Jul 22 '14 at 14:03
  • $\begingroup$ Each edge is accessed $O(1)$ times, so at worst its amortized $O(1)$ per edge. $\endgroup$ – Yuval Filmus Jul 22 '14 at 17:41
  • $\begingroup$ Which makes it O(Edge) if you count searching for a specific node count as O(1) $\endgroup$ – Jean-Luc Nacif Coelho Jul 24 '14 at 17:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.