module Skeleton (A : Traversal.A) (G : G) : sig .. end
module T: Traversal.Traversal(A)
val of_forest : ?tfac:float ->
?tadd:int -> T.t -> bool A.t * int A.t * int A.t
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.
module Bfs: Traversal.Bfs(A)(G)
val of_graph_comp : ?tfac:float ->
?tadd:int ->
?girth:int ->
G.t -> Bfs.Queue.V.elt -> G.t * G.t * G.t * int
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.).