| 40 | /** Find the root of the tree/set containing the vertex i : Use Path halving */ |
| 41 | template <typename Index, typename IndexVector> |
| 42 | Index etree_find(Index i, IndexVector& pp) { |
| 43 | Index p = pp(i); // Parent |
| 44 | Index gp = pp(p); // Grand parent |
| 45 | while (gp != p) { |
| 46 | pp(i) = gp; // Parent pointer on find path is changed to former grand parent |
| 47 | i = gp; |
| 48 | p = pp(i); |
| 49 | gp = pp(p); |
| 50 | } |
| 51 | return p; |
| 52 | } |
| 53 | |
| 54 | /** Compute the column elimination tree of a sparse matrix |
| 55 | * \param mat The matrix in column-major format. |