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$

closed as unclear what you're asking by D.W., FrankW, Juho, David Richerby, lPlant Jul 22 '14 at 13:56

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.