package ocamlgraph

  1. Overview
  2. Docs
package ocamlgraph
Legend:
Library
Module
Module type
Parameter
Class
Class type

Algorithms related to cycles in directed graphs.

type weight =
  1. | Normal of int
    (*

    Weighted arc that can be included in the feedback set. The weight must be zero (not normally a good choice) or positive (1 may be a good choice).

    *)
  2. | Obligatory of int
    (*

    Obligatory arc that cannot be returned in the feedback set. Set the weight to zero to completely ignore obligatory arcs when choosing which vertex to schedule. Set it to a positive value (1 may be a good choice) to adjust the preference for choosing vertexes that may "unblock" other vertexes by removing their incoming obligatory arcs.

    *)
module Fashwo (GB : sig ... end) : sig ... end

Adaptation of the FASH algorithm of Eades and Lin (1995) to handle edge weights and obligatory arcs. The algorithm tries to minimize the total weight of the returned feedback arc set. Obligatory arcs are respected and never returned in the feedback arc set, an exception is raised if the obligatory arcs form a cycle. The adapted algorithm is hereby called FASHWO: “feedback arc set heuristic + weights and obligations”.