5,337
edits
Parallel Algorithms: Difference between revisions
→List Ranking Cluster
| Line 330: | Line 330: | ||
===Rooting a tree=== | ===Rooting a tree=== | ||
Inputs | Technique: Euler tours | ||
;Inputs | |||
* Vector of vertices which point to an index in edges | * Vector of vertices which point to an index in edges | ||
* Vector of edges e.g. (1,2) | * Vector of edges e.g. (1,2) | ||
| Line 336: | Line 338: | ||
* A vertex <math>r</math> | * A vertex <math>r</math> | ||
Goal: | ;Goal: | ||
* Select a direction for each edge to make our graph a tree with root <math>r</math> | * Select a direction for each edge to make our graph a tree with root <math>r</math> | ||
Algorithm | ;Algorithm | ||
* Step 1: For every edge <math>(u,v)</math>, add two edges <math>u \rightarrow v</math> and <math>v \rightarrow u</math> | * Step 1: For every edge <math>(u,v)</math>, add two edges <math>u \rightarrow v</math> and <math>v \rightarrow u</math> | ||
* Step 2: For every directed edge <math>u \rightarrow v</math>, set a pointer to another directed edge from <math>v</math>, <math>next(u \rightarrow v)</math> | * Step 2: For every directed edge <math>u \rightarrow v</math>, set a pointer to another directed edge from <math>v</math>, <math>next(u \rightarrow v)</math> | ||
** If our edge is 1 -> 2, then the next edge is the immediate next edge of edge 2->1 in our edges array | |||
** If edge 2 -> 1 is the last edge coming out of 2, then the next edge is the first edge coming out of 2 | |||
** Now we have an euler cycle (or euler tour) among the edges | |||
* Step 3: <math>next(u_{r,1} \rightarrow r) = NIL </math> | * Step 3: <math>next(u_{r,1} \rightarrow r) = NIL </math> | ||
* Step 4: Apply a list ranking algorithm. | * Step 4: Apply a list ranking algorithm to the edges. | ||
* Step 5: Delete the edge between every two vertices with the lower ranking | |||
;Notes | |||
* Every step except 4, list ranking, is a local operation which is constant time and linear work | |||
* Requires a list ranking algorithm | |||
====Preorder Numbering==== | |||
Define: tree-edges point away from root, non-tree edges point to root | |||
* Step 1: For every edge pardo, if e is a tree edge, distance(e) = 1 else distance(e) = 0 | |||
* Step 2: List ranking | |||
* Step 3: For every edge e: u->v, preorder(v) = n-distance(e) + 1 | |||
==Resources== | ==Resources== | ||