Euler tour technique

From Wikipedia for FEVERv2
Jump to navigation Jump to search

The Euler tour technique (ETT), named after Leonhard Euler, is a method in graph theory for representing trees. Euler tour technique_sentence_0

The tree is viewed as a directed graph that contains two directed edges for each edge in the tree. Euler tour technique_sentence_1

The tree can then be represented as a Eulerian circuit of the directed graph, known as the Euler tour representation (ETR) of the tree. Euler tour technique_sentence_2

The ETT allows for efficient, parallel computation of solutions to common problems in algorithmic graph theory. Euler tour technique_sentence_3

It was introduced by Tarjan and Vishkin in 1984. Euler tour technique_sentence_4

Construction Euler tour technique_section_0

Given an undirected tree presented as a set of edges, the Euler tour representation (ETR) can be constructed in parallel as follows: Euler tour technique_sentence_5

Euler tour technique_unordered_list_0

  • We construct a symmetric list of directed edges:Euler tour technique_item_0_0
    • For each undirected edge {u,v} in the tree, insert (u,v) and (v,u) in the edge list.Euler tour technique_item_0_1
  • Sort the edge list lexicographically. (Here we assume that the nodes of the tree are ordered, and that the root is the first element in this order.)Euler tour technique_item_0_2
  • Construct adjacency lists for each node (called next) and a map from nodes to the first entries of the adjacency lists (called first):Euler tour technique_item_0_3
    • For each edge (u,v) in the list, do in parallel:Euler tour technique_item_0_4
      • If the previous edge (x,y) has x ≠ u, i.e. starts from a different node, set first(u) = (u,v)Euler tour technique_item_0_5
      • Else if x = u, i.e. starts from the same node, set next(x,y) = (u,v)Euler tour technique_item_0_6

Construct an edge list (called succ) in Euler tour order by setting pointers succ(u,v) for all edges (u,v) in parallel according to the following rule: Euler tour technique_sentence_6

The resulting list succ will be circular. Euler tour technique_sentence_7

The overall construction takes work W(n) = O(sort(n)) (the time it takes to sort n items in parallel) if the tree has n nodes, as in trees the number of edges is one less than the number of nodes. Euler tour technique_sentence_8

Roots, advance and retreat edges Euler tour technique_section_1

If the tree has a root, we can split the circular list succ at that root. Euler tour technique_sentence_9

In that case, we can speak of advance and retreat edges: given a pair of nodes u,v, the first occurrence of either (u,v) or (v,u) in the ETR is called the advance edge, and the second occurrence is called the retreat edge. Euler tour technique_sentence_10

This appeals to the intuition that the first time such an edge is traversed the distance to the root is increased, while the second time the distance decreases. Euler tour technique_sentence_11

Rerooting the tree can be done in constant time O(1) by splitting the circular list succ at the new root. Euler tour technique_sentence_12

Applications Euler tour technique_section_2

All of the following problems can be solved in O(Prefix sum(n)) (the time it takes to solve the prefix sum problem in parallel for a list of n items): Euler tour technique_sentence_13

Euler tour technique_ordered_list_1

  1. Classifying advance and retreat edges: Do list ranking on the ETR and save the result in a two-dimensional array A. Then (u,v) is an advance edge iff A(u,v) < A(v,u), and a retreat edge otherwise.Euler tour technique_item_1_7
  2. Determine the level of each node: Do a prefix sum on the ETR, where every advance edge counts as 1, and every retreat edge counts as −1. Then the value at the advance edge (u,v) is the level of v.Euler tour technique_item_1_8
  3. Number of nodes in a subtree rooted at v: determine advance edge (u,v), and the retreat edge (u,v) in parallel, and then count the number of advance edges between (u,v) and (u,v) using prefix sum.Euler tour technique_item_1_9
  4. The depth-first search index of a node v: count the number of advance edges up to and including (u,v).Euler tour technique_item_1_10
  5. Determine the lowest common ancestor of two nodes.Euler tour technique_item_1_11

Euler tour trees Euler tour technique_section_3

Henzinger and King suggest to represent a given tree by keeping its Euler tour in a balanced binary search tree, keyed by the index in the tour. Euler tour technique_sentence_14

So for example, the unbalanced tree in the example above, having 7 nodes, will be represented by a balanced binary tree with 14 nodes, one for each time each node appears on the tour. Euler tour technique_sentence_15

We can represent a forest (an acyclic graph) using a collection of ET trees - one ET tree for one forest tree. Euler tour technique_sentence_16

This representation allows us to quickly answer the question "what is the root of node v?" Euler tour technique_sentence_17

by just moving to the first node of the ET tree (since nodes in the ET tree are keyed by their location in the Euler tour, and the root is the first and last node in the tour). Euler tour technique_sentence_18

When the represented forest is updated (e.g. by connecting two trees to a single tree or by splitting a tree to two trees), the corresponding Euler-tour structure can be updated in time O(log(n)). Euler tour technique_sentence_19

Link/cut trees have similar performance guarantees. Euler tour technique_sentence_20

While LC trees are good for maintaining aggregates on paths of a tree (making it a good choice data structure in network flow algorithms), ET trees are better at keeping aggregate information on subtrees. Euler tour technique_sentence_21

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: tour technique.