package libsail

  1. Overview
  2. Docs

Module Jib_compile.IdGraphSource

include Graph.S with type node = Ast.id and type node_set = Ast_compare.IdSet.t
Sourcetype node = Ast.id
Sourcetype graph
Sourceval leaves : graph -> node_set
Sourceval empty : graph
Sourceval add_edge : node -> node -> graph -> graph

Add an edge from the first node to the second node, creating the nodes if they do not exist.

Sourceval has_edge : node -> node -> graph -> bool
Sourceval delete_edge : node -> node -> graph -> graph
Sourceval add_edges : node -> node list -> graph -> graph
Sourceval children : graph -> node -> node list
Sourceval nodes : graph -> node list
Sourceval reachable : node_set -> node_set -> graph -> node_set

Return the set of nodes that are reachable from the first set of nodes (roots), without passing through the second set of nodes (cuts).

Sourceval prune : node_set -> node_set -> graph -> graph

Prune a graph from roots to cuts.

Sourceval remove_self_loops : graph -> graph
Sourceval self_loops : graph -> node list
Sourceval reverse : graph -> graph
Sourceexception Not_a_DAG of node * graph
Sourceval topsort : graph -> node list

Topologically sort a graph. Throws Not_a_DAG if the graph is not directed acyclic.

Sourceval scc : ?original_order:node list -> graph -> node list list

Find strongly connected components using Tarjan's algorithm. This algorithm also returns a topological sorting of the graph components.

Sourceval edge_list : graph -> (node * node) list
Sourceval transitive_reduction : graph -> graph

Note that this is at least O(n^3) where n is the number of nodes and very inefficiently constructs the result graph!

Sourceval make_multi_dot : node_color:(node -> string) -> edge_color:(node -> node -> string) -> string_of_node:(node -> string) -> out_channel -> (string * graph) list -> unit
Sourceval make_dot : node_color:(node -> string) -> edge_color:(node -> node -> string) -> string_of_node:(node -> string) -> out_channel -> graph -> unit