Index of values

Addition of weights.

add_edge g v1 v2 adds an edge from the vertex v1 to the vertex v2 in the graph g.

add_edge g v1 v2 adds an edge from the vertex v1 to the vertex v2 in the graph g.

add_edge g v1 v2 adds an edge from the vertex v1 to the vertex v2 in the graph g.

add_edge_e g e adds the edge e in the graph g.

add_edge_e g e adds the edge e in the graph g.

add_edge_e g e adds the edge e in the graph g.

add_transitive_closure ?reflexive g replaces g by its transitive closure.

add_transitive_closure ?reflexive g replaces g by its transitive closure.

add_vertex g v adds the vertex v to the graph g.

add_vertex g v adds the vertex v from the graph g.

add_vertex g v adds the vertex v to the graph g.

all_pairs_shortest_paths g computes the distance of shortest path between all pairs of vertices in g.

shortest_path g vs computes the distances of shortest paths from vertex vs to all other vertices in graph g.

allminsep g computes the list of all minimal separators of g.

the actual analysis of one edge; provided the edge and the incoming data, it needs to compute the outgoing data

analyze f g computes the fixpoint on the given graph using the work list algorithm.

How to analyze one edge: given an edge and the data stored at its origin, it must compute the resulting data to be stored at its destination.

bellman_ford g v finds a negative cycle from v, and returns it, or raises Not_found if there is no such cycle

The counterclockwise relation ccw p q r states that the circle through points (p,q,r) is traversed counterclockwise when we encounter the points in cyclic order p,q,r,p,... *

check_path pc v1 v2 checks whether there is a path from v1 to v2 in the graph associated to the path checker pc.

choose_edge g returns an edge from the graph.

choose_vertex g returns a vertex from the graph.

clear g sets all marks to 0 from all the vertives of g.

Remove all vertices and edges from the given graph.

clear g sets all the marks to 0 for all the vertices of g.

Remove all vertices and edges from the given graph.

coherent_player g p returns true iff the completion p is coherent w.r.t.

coherent_strat g s returns true iff the strategy s is coherent w.r.t.

coloring g k colors the nodes of graph g using k colors, assigning the marks integer values between 1 and k.

coloring g k colors the graph g with k colors and returns the coloring as a hash table mapping nodes to their colors.

Weights must be ordered.

complement g builds a new graph which is the complement of g: each edge present in g is not present in the resulting graph and vice-versa.

complement g returns a new graph which is the complement of g: each edge present in g is not present in the resulting graph and vice-versa.

Computes all dominance functions.

Computes the dominance frontier.

Computes the dominator tree, using the Lengauer-Tarjan algorithm.

contract p g will perform edge contraction on the graph g.

copy g returns a copy of g.

copy g returns a copy of g.

create g builds a new path checker for the graph g; if the graph is mutable, it must not be mutated while this path checker is in use (through the function check_path below).

create v1 l v2 creates an edge from v1 to v2 with label l

Return an empty graph.

create () returns an empty graph.

create v1 l v2 creates an edge from v1 to v2 with label l

de_bruijn n builds the de Bruijn graph of order n.

de_bruijn n builds the de Bruijn graph of order n.

dfs g traverses g in depth-first search, marking all nodes.

the direction of the analysis

Displays the given graph using the external tools "dot" and "gv" and returns when gv's window is closed

divisors n builds the graph of divisors.

divisors n builds the graph of divisors.

Given a function from a node to it's dominators, returns a function dom : V.t -> V.t -> bool s.t.

Computes a dominator tree (function from x to a list of nodes immediately dominated by x) for the given CFG and dominator function.

Given a function from a node to it's dominators, returns a function idoms : vertex -> vertex -> bool s.t.

Given a function from a node to it's dominators, returns a function sdom : V.t -> V.t -> bool s.t.

Given a a function from a node to it's dominators, returns a function from a node to it's strict dominators.

DOT output in a file

Edge destination.

The empty graph.

predicate to determine the fixpoint

Equality test for data.

filter_map f g applies f to each edge of g and so builds a new graph based on g; if None is returned by f the edge is omitted in the new graph.

filter_map f g applies f to each vertex of g and so builds a new graph based on g; if None is returned by f the vertex is omitted in the new graph.

find_all_edges g v1 v2 returns all the edges from v1 to v2.

find_edge g v1 v2 returns the edge from v1 to v2 if it exists.

find_negative_cycle g looks for a negative-length cycle in graph g and returns it.

find_negative_cycle_from g vs looks for a negative-length cycle in graph g that is reachable from vertex vs and returns it as a list of edges.

vertex g i returns a vertex of label i in g.

The function is applied each time a node is reached for the first time, before idoterating over its successors.

fold action g seed allows iterating over the graph g in topological order.

Idem, but limited to a single root vertex.

Fold on all edges of a graph.

Fold on all edges of a graph.

Folding over the elements of a weak topological ordering.

It is enough to fold over all the roots (vertices without predecessor) of the graph, even if folding over the other vertices is correct.

Fold on all vertices of a graph.

Ford Fulkerson maximum flow algorithm

fprint_graph ppf graph pretty prints the graph graph in the CGL language on the formatter ppf.

fprint_graph ppf graph pretty prints the graph graph in the CGL language on the formatter ppf.

full n builds a graph with n vertices and all possible edges.

full n builds a graph with n vertices and all possible edges.

game g p a b returns true iff a wins in g given the completion p (i.e.

Mark value (in O(1)).

The box (if exists) which the vertex belongs to.

random graph using the G(n,p) model.

gnp v prob generates a random graph with v vertices and where each edge is selected with probality prob (G(n,p) model)

gnp_labeled add_edge v e is similar to gnp except that edges are labeled using function f.

gnp_labeled add_edge v prob is similar to gnp except that edges are labeled using function f

Goldberg-Tarjan maximum flow algorithm

graph xrange yrange prob v generates a random planar graph with exactly v vertices.

graph v e generates a random graph with exactly v vertices and e edges.

random v e generates a random with v vertices and e edges.

has_cycle g checks for a cycle in g.

has_cycle g checks for a cycle in g.

Computes a dominator tree (function from x to a list of nodes immediately dominated by x) for the given CFG and idom function.

The relation in_circle p q r s states that s lies inside the circle (p,q,r) if ccw p q r is true, or outside that circle if ccw p q r is false.

in_degree g v returns the in-degree of v in g.

in_degree g v returns the in-degree of v in g.

intersect g1 g2 returns a new graph which is the intersection of g1 and g2: each vertex and edge present in g1 *and* g2 is present in the resulting graph.

intersect g1 g2 returns a new graph which is the intersection of g1 and g2: each vertex and edge present in g1 *and* g2 is present in the resulting graph.

is_chordal g uses the clique tree construction to test if a graph is chordal or not.

is this an implementation of directed graphs?

Is this an implementation of directed graphs?

iter pre post g visits all nodes of g in depth-first search, applying pre to each visited node before its successors, and post after them.

iter action calls action node repeatedly.

iter pre post g visits all nodes of g in depth-first search, applying pre to each visited node before its successors, and post after them.

iter f t iterates over all edges of the triangulation t.

Iter on all edges of a graph.

Iter on all edges of a graph.

It is enough to iter over all the roots (vertices without predecessor) of the graph, even if iterating over the other vertices is correct.

Iter on all vertices of a graph.

operation how to join data when paths meet

Operation to join data when several paths meet.

Get the label of an edge.

labeled f is similar to graph except that edges are labeled using function f.

random_labeled f is similar to random except that edges are labeled using function f

leader_lists graph root computes the leader lists or basic blocks of the given graph.

Neighbourhood of a vertex as a list.

Neighbourhood of a list of vertices as a list.

Less efficient that allminsep

Creation.

map f g applies f to each edge of g and so builds a new graph based on g

map f g applies f to each vertex of g and so builds a new graph based on g

map iterator on vertex

Map on all vertices of a graph.

maxflow g v1 v2 searchs the maximal flow from source v1 to terminal v2 using the Ford-Fulkerson algorithm.

maxflow g v1 v2 searchs the maximal flow from source v1 to terminal v2 using Goldberg-Tarjan algorithm (with gap detection heuristic).

maximalcliques g computes all the maximal cliques of g using the Bron-Kerbosch algorithm.

maxwidth g tri tree returns the maxwidth characteristic of the triangulation tri of graph g given the clique tree tree of tri.

mcs_clique g return an perfect elimination order of g (if it is chordal), the clique tree of g and its root.

mcsm g return a tuple (o, e) where o is a perfect elimination order of g' where g' is the triangulation e applied to g.

mcsm g returns a tuple (o, e) where o is a perfect elimination order of g' where g' is the triangulation e applied to g.

md g return a tuple (g', e, o) where g' is a triangulated graph, e is the triangulation of g and o is a perfect elimination order of g'

md g return a tuple (g', e, o) where g' is a triangulated graph, e is the triangulation of g and o is a perfect elimination order of g'

If no element of el belongs to g then merge_edges_e g (e::el) is the graph g.

The graph merge_edges_with_label ?src ?tgt ?label g l is the graph merge_edges_e ?src ?dst g el with el being the list of all edges of g carrying the label l.

A vertex v of g is called an end if every edge of g arriving to v also starts from v.

The graph merge_isolabelled_edges g is obtained from g by identifying two vertices when they are the sources (destinations) of two edges sharing the same label.

The vertex of every strongly connected component are identified.

A vertex v of g is called a start if every edge of g starting from v also arrives to v.

If no element of vl belongs to g then merge_vertex g (v::vl) is the graph g.

Find a minimal cutset.

mirror g returns a new graph which is the mirror image of g: each edge from u to v has been replaced by an edge from v to u.

mirror g returns a new graph which is the mirror image of g: each edge from u to v has been replaced by an edge from v to u.

out_degree g v returns the out-degree of v in g.

out_degree g v returns the out-degree of v in g.

output_graph oc graph pretty prints the graph graph in the dot language on the channel oc.

output_graph oc graph pretty prints the graph graph in the dot language on the channel oc.

Parses a dot file

Parses a dot file and returns the graph, its bounding box and a hash table from clusters to dot attributes

applies only a postfix function.

applies only a postfix function

pred g v returns the predecessors of v in g.

pred g v returns the predecessors of v in g.

pred_e g v returns the edges going to v in g.

pred_e g v returns the edges going to v in g.

applies only a prefix function; note that this function is more efficient than iter and is tail-recursive.

applies only a prefix function

print fmt graph print the GraphMl representation of the given graph on the given formatter

recurse g wto init widening_set widening_delay computes the fixpoint of the analysis of a graph.

recursive_scc g root_g computes a weak topological ordering of the vertices of g, with the general algorithm recursively computing the strongly connected components of g.

remove_edge g v1 v2 removes the edge going from v1 to v2 from the graph g.

remove_edge g v1 v2 removes the edge going from v1 to v2 from the graph g.

remove_edge g v1 v2 removes the edge going from v1 to v2 from the graph g.

remove_edge_e g e removes the edge e from the graph g.

remove_edge_e g e removes the edge e from the graph g.

remove_edge_e g e removes the edge e from the graph g.

remove g v removes the vertex v from the graph g (and all the edges going from v in g).

remove g v removes the vertex v from the graph g (and all the edges going from v in g).

remove g v removes the vertex v from the graph g (and all the edges going from v in g).

replace_by_transitive_reduction ?reflexive g replaces g by its transitive reduction.

replace_by_transitive_reduction ?reflexive g replaces g by its transitive reduction.

strongly connected components

scc g computes the strongly connected components of g.

scc_array g computes the strongly connected components of g.

scc_list g computes the strongly connected components of g.

Set the mark of the given vertex.

Several functions provided by this module run the external program neato.

Neighbourhood of a vertex as a set.

Neighbourhood of a list of vertices as a set.

Less efficient that allminsep

shortest_path g v1 v2 computes the shortest path from vertex v1 to vertex v2 in graph g.

Dijkstra's shortest path algorithm.

Kruskal algorithm

Edge origin.

strategy g p s returns true iff s wins in g given the completion p, whatever strategy plays the other player.

strategyA g p returns true iff there exists a winning stragegy for the true player.

Subtraction of weights.

succ g v returns the successors of v in g.

succ g v returns the successors of v in g.

succ_e g v returns the edges going from v in g.

succ_e g v returns the edges going from v in g.

transitive_closure ?reflexive g returns the transitive closure of g (as a new graph).

transitive_closure ?reflexive g returns the transitive closure of g (as a new graph).

transitive_reduction ?reflexive g returns the transitive reduction of g (as a new graph).

transitive_reduction ?reflexive g returns the transitive reduction of g (as a new graph).

triangulate g return the graph g' produced by applying miminum degree to g.

triangulate g return the graph g' produced by applying miminum degree to g.

triangulate g triangulates g using the MCS-M algorithm

triangulate g computes a triangulation of g using the MCS-M algorithm

triangulate a computes the Delaunay triangulation of a set of points, given as an array a.

union g1 g2 returns a new graph which is the union of g1 and g2: each vertex and edge present in g1 *or* g2 is present in the resulting graph.

union g1 g2 returns a new graph which is the union of g1 and g2: each vertex and edge present in g1 *or* g2 is present in the resulting graph.

vertex_only n builds a graph with n vertices and no edge.

vertex_only n builds a graph with n vertices and no edge.

Vertices in the clique tree edge (intersection of the two clique extremities).

Get the weight of an edge.

The widening operator.

Neutral element for Sig.WEIGHT.add.