package graphlib

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

Graph library

Graphlib is a generic library that extends a well known OCamlGraph library. Graphlib uses its own, more reach, Graph interface that is isomorphic to OCamlGraph's Sigs.P signature for persistant graphs. Two functors witness the isomorphism of the interfaces: Graphlib.To_ocamlgraph and Graphlib.Of_ocamlgraph. Thanks to these functors, any algorithm written for OCamlGraph can be used on Graphlibs graph and vice verse.

The Graph interface provides a richer interface in a Core style. Nodes and Edges implements Opaque data structure, i.e., they come with Maps, Sets, Hashtbls, etc, preloaded (e.g., G.Node.Set is a set of node for graph implementation, provided by a module named G). Graphs also implement Printable interface, that makes them much easier to debug.

Along with graphs, auxiliary data structures are provided, like path to represent paths in graph, tree for representing different graph spannings, partition for graph partitioning, and more.

Graphlib is a library that provides a set of generic algorithms, as well as implementations of a Graph interface, and a suite of preinstantiated graphs.

Contrary to OCamlGraph, each Graphlib interface is provided as a function, not a functor. Thus making there use syntactically easier. Also, Graphlib heavily uses optional and keyword parameters. For die-hards, many algorithms still have functor a interface.

All Graphlib algorithms accept a first-class module with graph implementation as a first argument. You can think of this parameter as an explicit type class. Later, when modular implicits will be accepted in OCaml, this parameter can be omitted. But for now, we need to pass them.

A recommended way to work with Graphlib is to bind the chosen implementation with some short name, usually G would be a good choice:

module G = Graphlib.Make(String)(Bool)

This will bind name G with a graph implementation that has string nodes, with edges labeled by values of type bool.

To create a graph of type G.t one can use a generic Graphlib.create function:

let g = Graphlib.create (module G) ~edges:[
  "entry", "loop", true;
  "loop", "exit", true;
  "loop", "loop", false;
] ()

This will create an instance of type G.t. Of course, it is still possible to use non-generic G.empty, G.Node.insert, G.Edge.insert.

module type Node = sig ... end

Graph nodes.

module type Edge = sig ... end

Interface that every Graph edge should provide

module type Graph = sig ... end

Graph signature.

type ('c, 'n, 'e) graph = (module Graph with type edge = 'e and type node = 'n and type t = 'c)

a type abbreviation for a packed module, implementing graph interface. Note: this type prenexes only 3 out of 8 type variables, so, sometimes it is not enough.

type edge_kind = [
  1. | `Tree
    (*

    edge is a part of a tree

    *)
  2. | `Back
    (*

    back edge

    *)
  3. | `Cross
    (*

    cross edge

    *)
  4. | `Forward
    (*

    forward edge

    *)
]

Graph edges classification. For explanations see DFS.

type 'a tree

a Tree representation.

type 'a frontier

a type representing Frontiers

type 'a partition

a result of partitioning algorithms

type 'a group

a partition Cell

type 'a path

walk without a repetition of edges and inner nodes

type equiv

runtime witness of the equivalence class

module Tree : sig ... end

Tree is a particular subtype of a graph for which each node has only one predecessor, and there is only one path between tree root and any other node. Here is an example of a tree:

module Frontier : sig ... end

Frontier maps each node into a possibly empty set of nodes. This is used for representing dominance and post-dominance frontiers.

module Path : sig ... end

Path between two nodes.

module Partition : sig ... end

Result of a set partitioning.

module Group : sig ... end

Group is a non-empty set that is a result of partitioning of an underlying set S into a set of non-intersecting and non-empty subsets that cover set S. See Partition for more information.

module Equiv : sig ... end

Ordinal for representing equivalence. Useful, for indexing elements based on their equivalence.

Auxiliary graph data structures
module type Predicate = sig ... end

A type of modules for filtering graphs. See Graphlib.filtered or Graphlib.Filtered

module type Isomorphism = sig ... end

Isomorphism is a bijection between type s and t. Usefull for creating graph views and mapping graphs. See Graphlib.view and Graphlib.Mapper.

class type ['n, 'e, 's] dfs_visitor = object ... end
Visual attributes for graph vizualization.

Consult OCamlGraph library for more information.

type ('n, 'a) labeled = {
  1. node : 'n;
  2. node_label : 'a;
}
module Graphlib : sig ... end

Generic Graph Library