Index of values

Nodes are added if not prsent.

Number of cells allocated in memory.

Default value in vectors,

Distance from root.

Maximal index given to set so far, -1 if no value has been set yet.

Iterate on u, parent(u), ..., v if v is ancestor of u, and up to the root of the tree containing u otherwise.

Equivalent to 1 + index_max.

Total number of nodes (including non-visited nodes).

The (tfac,tadd)-skeleton of a forest is defined as follows : a node u is ``long'' if dist(u,e) >= tfac * dist(r,u) + tadd where e is the descendant of u that is furthest from u and r is the root of the tree containing u,, the ``branch'' of a node u is the path from u to its furthest descendant e,, the skeleton is the union of the branches of long nodes.

of_graph_comp g u computes a skeleton of the component of u in graph g as follows: An ``extremal'' node r is chosen (we use the last node in a BFS from u)., A skeleton tree of the single source shortest path tree rooted at r is computed., We remove branches that are covered by their parent branche where a branch b is covered when all nodes of b are at distance at most tadd from the branch containing the parent of the root of b, and a branch is a path from a root node to its furthest descendant in the tree (we consider only branches that are maximal for inclusion)., If a path of length tadd = 4 is found between two branches, it is added in the skeleton if this does create a cycle with length less than girth = 3*tadd. Note that the resulting graph has girth (i.e. minimum cycle length) at least girth. (Paremeters can be optionally set: ~tfac:1.5 ~tadd:6 control the computation of the skeleton tree, ~girth:10 would set the minimum cycle length to 10.).

Visited nodes in traversal order.

The two above functions allow to print progress information during algorithms.

Has vertex been visited.