# Tree Computations

## Required Readings

### Optional

## Summary

- Parallel Root Finder
- Parallel Independent Set
- Seemingly Sequential Tree Algorithm
- Euler Tour Technique

## Parallel Root Finder

Trees can be stored as an array pool, with an array storing the parents.

A sequential algorithm to find the root would look like so

```
root(P[1:n])
if n < 1 then return 0
node <- (any node, 1 .. n)
while P[node] != 0 do
node <- P[node]
return node
```

Runtime = O(n)

A parallel idea is to explore all nodes simultaneously by changing each parent to the grandparent, until there are no more grandparents.

```
hasGrandparent(k, P[1:n])
return (k>0) and (P[k]>0) and (P[P[k]] > 0)
adopt(P[1:n], G[1:n])
par-for i<-1 to n do
if hasGrandparent(i, P[:])
then G[i] <- P[P[i]]
else G[i] <- P[i]
findRoots(P[1:n], R[1:n])
let P_cur[1:n] <- P[:]
let P_next[1:n] <- temp_buf
for l <- 1 to ciel(log(n)) do
adopt(P_cur[:], P_next[:])
P_cur[:] <- P_next[:]
R[:] <- P_cur[:]
```

## Parallel Independent Set

If you want to shrink a list, a good tool is the Parallel Independent Set (PIS).

$define Independent Set Given a list, a set I of vertices such that every element in the set does not have its successor in the set.

$i \in I \implies N[i] \notin I$ define$

Sequentially, you can just start at the head and add every other node to the set.

To compute it in parallel, you need to break the `symmetry`

(all nodes lookging
the same).

- Flip a coin. If tails, the node is NOT in the set. If heads, the node is a candidate for the set.
- If a candidate’s successor is a candidate, the predecessor is not a candidate.
- Collect all remaining candidates.

```
ParIndSet(N[1:n], I[:])
let C[1:n], C'[1:n] <- space for coins
par-for i <- 1 to n do
C[i] <- flipCoin(H/T) // rand(0..1) > 0.5
C'[i] <- C[i] // make a copy
par-for i <- 1 to n do
// If I'm heads, and I have a successor, and the successor is heads, I am
// tails.
if (C'[i] = H) and (N[i]>0) and (C'[N[i]] = H) then
C[i] <- T
I[:] <- gatherIf(1:n, C[1:n])
```

Work = W(n) = O(n)

Span = D(n) = O(log(n))

On average, 1/4 nodes end up in the IS

For work optimal List Scanning, use PIS to determine the heads of Wyllie’s and/or Helmann-JaJa

## Seemingly Sequential Tree Algorithm

```
// Root, numbering, initial value
postOrder(root, V[1:n], v_0)
v <- v_0
for-each c in children(root) do
v <- postOrder(c, V[:], v) + 1
V[root] <- v
return v
```

## Euler Tour Technique

Take a tree, change every bidirectional edge to two unidirectional edges. Now we get a directed circuit. This circuit gives you a linked list.

define Directed Circuit A closed path that uses every edge exactly once. define

### How to get post order numbering:

- Set parent-to-child sink: 0
- Set child-to-parent sink: 1
- Do a scan
- child-to-parent sources now equal post order numbering!

### Implementing Euler Tours

You need a graph to get from node to node

Also, the successor function: $s(u_i,v) \equiv (v, u_{(i+1)\mod d_v})$

## What is s(s(s(6,8)))

$s(s(s(6,8))) = s(s(8,6))$

$\phantom{s(s(s(6,8)))} = s(6,1)$

$\phantom{s(s(s(6,8)))} = (1,0)$