Index of modules

A
Abstract [Imperative.S]

Abstract Imperative Unlabeled Graphs.

Abstract [Persistent.S]

Abstract Persistent Unlabeled Graphs.

AbstractLabeled [Imperative.S]

Abstract Imperative Labeled Graphs.

AbstractLabeled [Persistent.S]

Abstract Persistent Labeled Graphs.

Algo [Strat]

Implements strategy algorithms on graphs

B
B [Merge]

Extension for the module X.

BellmanFord [Path]
Bfs [Traverse]

Breadth-first search

Bfs [Sig_pack.S]

Breadth-first search

Bron_Kerbosch [Clique]
Builder

Graph builders in order to persistent/imperative graphs sharing a same signature.

C
CMPProduct [Util]

Cartesian product of two comparable types.

CVS [Cliquetree.CliqueTree]

Set of original vertices

ChaoticIteration

Fixpoint computation with widenings using weak topological orderings as defined by François Bourdoncle and implemented in WeakTopological.

Check [Path]

Check for a path.

Choose [Oper]

Choose an element in a graph

Classic

Some classic graphs

Classic [Sig_pack.S]

Classic graphs

Clique

Graph cliques

CliqueTree [Cliquetree.CliqueTree]

The clique tree graph type

CliqueTree [Cliquetree]
CliqueTreeE [Cliquetree.CliqueTree]
CliqueTreeV [Cliquetree.CliqueTree]

Clique tree vertex type

CliqueV [Cliquetree.CliqueTree]

Original graph vertex

Cliquetree

Construction of the clique tree of a graph and recognition of chordal graphs.

Coloring

k-coloring of undirected graphs.

CommonAttributes [Graphviz]

The CommonAttributes module defines attributes for graphs, vertices and edges that are available in the two engines, dot and neato.

Components

Strongly connected components.

Components [Sig_pack.S]

Strongly connected components

Concrete [Imperative.S]

Imperative Unlabeled Graphs.

Concrete [Persistent.S]

Persistent Unlabeled Graphs.

ConcreteBidirectional [Imperative.Digraph]

Imperative Unlabeled, bidirectional graph.

ConcreteBidirectional [Persistent.Digraph]

Imperative Unlabeled, bidirectional graph.

ConcreteBidirectionalLabeled [Imperative.Digraph]

Imperative Labeled and bidirectional graph.

ConcreteBidirectionalLabeled [Persistent.Digraph]

Imperative Labeled and bidirectional graph.

ConcreteLabeled [Imperative.S]

Imperative Labeled Graphs.

ConcreteLabeled [Persistent.S]

Persistent Labeled Graphs.

Contraction

Edge contraction for directed, edge-labeled graphs

D
DataV [Util]

Create a vertex type with some data attached to it

Delaunay

Delaunay triangulation.

Dfs [Traverse]

Depth-first search

Dfs [Sig_pack.S]

Depth-first search

Digraph [Pack]

Directed imperative graphs with edges and vertices labeled with integer.

Digraph [Imperative.Matrix]

Imperative Directed Graphs implemented with adjacency matrices.

Digraph [Imperative]

Imperative Directed Graphs.

Digraph [Persistent]

Persistent Directed Graphs.

Dijkstra [Path]
Dominator

Dominators

Dot

Parser for DOT file format.

Dot [Graphviz]
DotAttributes [Graphviz]

DotAttributes extends CommonAttributes and implements ATTRIBUTES.

Dot_ast

AST for DOT file format.

E
E [ChaoticIteration.G]
E [Graphml.G]
E [Contraction.G]
E [Fixpoint.G]
E [Gmap.E_SRC]
E [Gml.G]
E [Prim.G]
E [Flow.G_FORD_FULKERSON]
E [Flow.G_GOLDBERG_TARJAN]
E [Kruskal.G]
E [Path.G]
E [Sig_pack.S]

Edges

E [Sig.G]

Edges have type E.t and are labeled with type E.label.

Edge [Gmap]

Provide a mapping function from a mapping of edges.

F
Fixpoint

Fixpoint computation implemented using the work list algorithm.

Float [Delaunay]

Delaunay triangulation with floating point coordinates

FloatPoints [Delaunay]

Points with floating point coordinates

Flow

Algorithms on flows

Ford_Fulkerson [Flow]
G
G [Minsep.MINSEP]

Implementation of a graph

G [Builder.S]
Generic [Kruskal]

Functor providing an implementation of Kruskal's minimum-spanning-tree algorithm using a user-defined union-find algorithm.

Gmap

Graph mapping.

Gml

Parser and pretty-printer for GML file format.

Goldberg_Tarjan [Flow]
Graph [Pack]

Undirected imperative graphs with edges and vertices labeled with integer.

Graph [Imperative.Matrix]

Imperative Undirected Graphs implemented with adjacency matrices.

Graph [Imperative]

Imperative Undirected Graphs.

Graph [Persistent]

Persistent Undirected Graphs.

Graphml

Generic GraphMl Printer

Graphviz

Interface with GraphViz

H
H [Coloring.Make]

Hash tables used to store the coloring

H [Path.BellmanFord]
HTProduct [Util]

Cartesian product of two hashable types.

HVV [Path.Johnson]
I
I [Merge]

Extension for the module G.

I [Md]
I [Mcs_m.MaximalCardinalitySearch]
I [Minsep]

Implementation for an imperative graph.

I [Oper]

Basic operations over imperative graphs

I [Rand.Planar]

Random imperative planar graphs

I [Rand]

Random imperative graphs

I [Classic]

Classic Imperative Graphs

I [Builder]

Imperative Graphs Builders.

Imperative [Nonnegative]
Imperative

Imperative Graph Implementations.

Int [Delaunay]

Delaunay triangulation with integer coordinates

IntPoints [Delaunay]

Points with integer coordinates

J
Johnson [Path]
K
Kruskal

Kruskal's minimum-spanning-tree algorithm.

L
Leaderlist

The leader list algorithm; it generates a list of basic blocks from a directed graph.

M
M [ChaoticIteration.Make]

Map used to store the result of the analysis

Make [ChaoticIteration]
Make [WeakTopological]
Make [Mincut]
Make [Contraction]
Make [Leaderlist]
Make [Fixpoint]
Make [Dominator]
Make [Prim]

Functor providing an implementation of Prim's minimum-spanning-tree algorithm.

Make [Kruskal]

Functor providing an implementation of Kruskal's minimum-spanning-tree algorithm.

Make [Topological]

Functor providing topological iterators over a graph.

Make [Coloring]

Provide a function for k-coloring a graph.

Make [Components]

Functor providing functions to compute strongly connected components of a graph.

Make [Oper]

Basic operations over graphs

Make [Rand.Planar]

Random planar graphs

Make [Rand]

Random graphs

Make [Delaunay]

Generic Delaunay triangulation

Make_graph [Dominator]
Make_stable [Topological]

Provide the same features than Topological.Make, except that the resulting topological ordering is stable according to vertices comparison: if two vertices v1 and v2 are topologically equal, v1 is presented first to the iterator if and only if G.V.compare v1 v2 <= 0.

Mark [Coloring.GM]
Mark [Coloring]

Provide a function for k-coloring a graph with integer marks.

Mark [Traverse.GM]
Mark [Traverse]

Graph traversal with marking.

Mark [Sig_pack.S]

Vertices contains integers marks, which can be set or used by some algorithms (see for instance module Marking below)

Mark [Sig.IM]

Mark on vertices.

Marking [Sig_pack.S]

Graph traversal with marking

Matrix [Imperative]

Imperative graphs implemented as adjacency matrices.

MaximalCardinalitySearch [Mcs_m]
Mcs_m

Maximal Cardinality Search (MCS-M) algorithm

Md

Minimum Degree algorithm

Merge

Provides functions to extend any module satisfying one of the signatures Sig.P, Sig.I and Builder.S .

Mincut

Minimal cutset of a graph

Minsep

Minimal separators of a graph

N
Neato [Graphviz]
NeatoAttributes [Graphviz]

The NeatoAttributes module defines attributes for graphs, nodes and edges that are available in the neato engine.

Neighbourhood [Oper]

Neighbourhood of vertex / vertices

Nonnegative

Weighted graphs without negative-cycles.

O
OTProduct [Util]

Cartesian product of two ordered types.

Oper

Basic operations over graphs

P
P [Merge]

Extension for the module G.

P [Md]
P [Mcs_m.MaximalCardinalitySearch]
P [Minsep]

Implementation for a persistent graph

P [Oper]

Basic operations over persistent graphs

P [Rand.Planar]

Random persistent planar graphs

P [Rand]

Random persistent graphs

P [Classic]

Classic Persistent Graphs

P [Builder]

Persistent Graphs Builders.

Pack

Immediate access to the library: provides implementation of imperative graphs labeled with integer as well as algorithms on such graphs.

Parse [Dot]

Provide a parser for DOT file format.

Parse [Gml]

Provide a parser for GML file format.

Path

Paths

PathCheck [Sig_pack.S]

Path checking

Persistent [Nonnegative]

Persistent graphs with negative-cycle prevention

Persistent

Persistent Graph Implementations.

Planar [Rand]
Prim
Print [Graphml]

Graphml Printer given a graph and required info

Print [Gml]

Provide a pretty-printer for GML file format.

R
Rand

Random graph generation.

Rand [Sig_pack.S]

Random graphs

S
S [Dominator.S]
S [Delaunay.Triangulation]
Sig

Signatures for graph implementations.

Sig_pack

Immediate access to the library: contain a signature gathering an imperative graph signature and all algorithms.

Strat

Strategies

T
Topological

Topological order.

Topological [Sig_pack.S]

Topological order

Traverse

Graph traversal.

U
Undirected [Components]
Util

Some useful operations.

V
V [ChaoticIteration.G]
V [WeakTopological.G]
V [Clique.G]
V [Mincut.G]
V [Contraction.G]
V [Leaderlist.G]
V [Fixpoint.G]
V [Strat.G]
V [Minsep.G]
V [Gmap.V_SRC]
V [Gml.G]
V [Dominator.G]
V [Prim.G]
V [Flow.G_FORD_FULKERSON]
V [Flow.G_GOLDBERG_TARJAN]
V [Kruskal.G]
V [Topological.G]
V [Coloring.GM]
V [Coloring.G]
V [Traverse.GM]
V [Traverse.G]
V [Path.G]
V [Components.U]
V [Components.G]
V [Sig_pack.S]

Vertices

V [Sig.G]

Vertices have type V.t and are labeled with type V.label (note that an implementation may identify the vertex with its label)

VSetset [Minsep.MINSEP]

Implementation of a set of Vertex_Set

Vertex [Gmap]

Provide a mapping function from a mapping of vertices.

Vertex_Set [Minsep.MINSEP]

Implementation of a set of vertex

Vertex_Set [Oper.Neighbourhood]
W
WeakTopological

Weak topological ordering of the vertices of a graph, as described by François Bourdoncle.