| 124 | */ |
| 125 | template <typename IndexVector> |
| 126 | void nr_etdfs(typename IndexVector::Scalar n, IndexVector& parent, IndexVector& first_kid, IndexVector& next_kid, |
| 127 | IndexVector& post, typename IndexVector::Scalar postnum) { |
| 128 | typedef typename IndexVector::Scalar StorageIndex; |
| 129 | StorageIndex current = n, first, next; |
| 130 | while (postnum != n) { |
| 131 | // No kid for the current node |
| 132 | first = first_kid(current); |
| 133 | |
| 134 | // no kid for the current node |
| 135 | if (first == -1) { |
| 136 | // Numbering this node because it has no kid |
| 137 | post(current) = postnum++; |
| 138 | |
| 139 | // looking for the next kid |
| 140 | next = next_kid(current); |
| 141 | while (next == -1) { |
| 142 | // No more kids : back to the parent node |
| 143 | current = parent(current); |
| 144 | // numbering the parent node |
| 145 | post(current) = postnum++; |
| 146 | |
| 147 | // Get the next kid |
| 148 | next = next_kid(current); |
| 149 | } |
| 150 | // stopping criterion |
| 151 | if (postnum == n + 1) return; |
| 152 | |
| 153 | // Updating current node |
| 154 | current = next; |
| 155 | } else { |
| 156 | current = first; |
| 157 | } |
| 158 | } |
| 159 | } |
| 160 | |
| 161 | /** |
| 162 | * \brief Post order a tree |