Index of values

A
add [Strat.STRAT]
add [Flow.FLOW]
add [Sig.WEIGHT]

Addition of weights.

add_edge [Dominator.I]
add_edge [Builder.S]
add_edge [Sig_pack.S]

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

add_edge [Sig.I]

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

add_edge [Sig.P]

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

add_edge_e [Contraction.G]
add_edge_e [Gmap.E_DST]
add_edge_e [Builder.S]
add_edge_e [Sig_pack.S]

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

add_edge_e [Sig.I]

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

add_edge_e [Sig.P]

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

add_transitive_closure [Oper.S]

add_transitive_closure ?reflexive g replaces g by its transitive closure.

add_transitive_closure [Sig_pack.S]

add_transitive_closure ?reflexive g replaces g by its transitive closure.

add_vertex [Gmap.V_DST]
add_vertex [Builder.S]
add_vertex [Sig_pack.S]

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

add_vertex [Sig.I]

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

add_vertex [Sig.P]

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

all_pairs_shortest_paths [Path.Johnson]

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

all_shortest_paths [Path.BellmanFord]

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

allminsep [Minsep.MINSEP]

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

analyze [ChaoticIteration.Data]

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.

analyze [Fixpoint.Analysis]

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

analyze [Fixpoint.Make]

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

B
bellman_ford [Sig_pack.S]

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

C
ccw [Delaunay.CCC]

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 [Path.Check]

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

check_path [Sig_pack.S.PathCheck]
choose_edge [Oper.Choose]

choose_edge g returns an edge from the graph.

choose_vertex [Oper.Choose]

choose_vertex g returns a vertex from the graph.

clear [Traverse.GM.Mark]
clear [Sig_pack.S.Mark]

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

clear [Sig_pack.S]

Remove all vertices and edges from the given graph.

clear [Sig.MARK]

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

clear [Sig.I]

Remove all vertices and edges from the given graph.

coherent_player [Strat.Algo]

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

coherent_strat [Strat.Algo]

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

color_to_color_with_transparency [Graphviz]
coloring [Coloring.Mark]

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

coloring [Coloring.Make]

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

compare [Cliquetree.CliqueTree.CliqueTreeE]
compare [Cliquetree.CliqueTree.CliqueTreeV]
compare [Cliquetree.CliqueTree.CliqueV]
compare [Prim.G.E]
compare [Flow.FLOW]
compare [Util.DataV]
compare [Sig_pack.S.E]
compare [Sig_pack.S.V]
compare [Sig.WEIGHT]

Weights must be ordered.

compare [Sig.EDGE]
compare [Sig.COMPARABLE]
compare [Sig.ORDERED_TYPE]
complement [Oper.S]

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.

complement [Sig_pack.S]

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.

components [Components.Undirected]
components_array [Components.Undirected]
components_list [Components.Undirected]
compute_all [Dominator.Make_graph]

Computes all dominance functions.

compute_dom_frontier [Dominator.S]

Computes the dominance frontier.

compute_dom_graph [Dominator.Make_graph]
compute_idom [Dominator.S]

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

contract [Contraction.Make]

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

copy [Builder.S]
copy [Sig_pack.S]

copy g returns a copy of g.

copy [Sig.I]

copy g returns a copy of g.

create [Cliquetree.CliqueTree.CliqueTreeE]
create [Cliquetree.CliqueTree.CliqueTreeV]
create [Cliquetree.CliqueTree.CliqueV]
create [Dominator.I]
create [Path.G.E]
create [Path.Check]

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 [Util.DataV]
create [Sig_pack.S.PathCheck]
create [Sig_pack.S.E]

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

create [Sig_pack.S.V]
create [Sig_pack.S]

Return an empty graph.

create [Sig.I]

create () returns an empty graph.

create [Sig.EDGE]

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

create [Sig.VERTEX]
D
data [Cliquetree.CliqueTree.CliqueTreeV]
data [Util.DataV]
de_bruijn [Classic.S]

de_bruijn n builds the de Bruijn graph of order n.

de_bruijn [Sig_pack.S.Classic]

de_bruijn n builds the de Bruijn graph of order n.

default [Cliquetree.CliqueTree.CliqueTreeE]
default [Sig.ORDERED_TYPE_DFT]
default_edge_attributes [Graphviz.GraphWithDotAttrs]

Edge attributes

default_vertex_attributes [Graphviz.GraphWithDotAttrs]

Vertex attributes

dfs [Traverse.Mark]

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

dfs [Sig_pack.S.Marking]
direction [Fixpoint.Analysis]

the direction of the analysis

display_with_gv [Sig_pack.S]

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

divisors [Classic.S]

divisors n builds the graph of divisors.

divisors [Sig_pack.S.Classic]

divisors n builds the graph of divisors.

dom_to_sdom [Dominator.S]
dominators_to_dom [Dominator.S]

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

dominators_to_dom_tree [Dominator.S]

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

dominators_to_idoms [Dominator.S]

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

dominators_to_sdom [Dominator.S]

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

dominators_to_sdominators [Dominator.S]

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

dot_output [Sig_pack.S]

DOT output in a file

dst [Graphml.G.E]
dst [Fixpoint.G.E]
dst [Gml.G.E]
dst [Prim.G.E]
dst [Flow.G_FORD_FULKERSON.E]
dst [Kruskal.G.E]
dst [Path.G.E]
dst [Sig_pack.S.E]
dst [Sig.EDGE]

Edge destination.

E
edge_attributes [Graphviz.GraphWithDotAttrs]
empty [Contraction.G]
empty [Strat.STRAT]
empty [Gmap.E_DST]
empty [Gmap.V_DST]
empty [Builder.S]
empty [Sig.P]

The empty graph.

equal [ChaoticIteration.Data]

Equality test for data.

equal [Fixpoint.Analysis]

predicate to determine the fixpoint

equal [Cliquetree.CliqueTree.CliqueTreeV]
equal [Cliquetree.CliqueTree.CliqueV]
equal [Gml.G.V]
equal [Util.DataV]
equal [Sig_pack.S.V]
equal [Sig.COMPARABLE]
equal [Sig.HASHABLE]
F
filter_map [Gmap.Edge]

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 [Gmap.Vertex]

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 [Kruskal.UNIONFIND]
find_all_edges [Sig_pack.S]
find_all_edges [Sig.G]

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

find_edge [Sig_pack.S]
find_edge [Sig.G]

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

find_negative_cycle [Path.BellmanFord]

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

find_negative_cycle_from [Path.BellmanFord]

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.

find_vertex [Sig_pack.S]

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

flow [Flow.FLOW]
fold [Topological.Make_stable]
fold [Topological.Make]

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

fold [Traverse.Bfs]
fold [Traverse.Dfs]

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

fold [Delaunay.Triangulation]
fold [Sig_pack.S.Topological]
fold [Sig_pack.S.Dfs]
fold_component [Traverse.Bfs]
fold_component [Traverse.Dfs]

Idem, but limited to a single root vertex.

fold_component [Sig_pack.S.Dfs]
fold_edges [Sig_pack.S]
fold_edges [Sig.G]

Fold on all edges of a graph.

fold_edges_e [Contraction.G]
fold_edges_e [Gmap.E_SRC]
fold_edges_e [Flow.G_GOLDBERG_TARJAN]
fold_edges_e [Path.G]
fold_edges_e [Sig_pack.S]
fold_edges_e [Sig.G]

Fold on all edges of a graph.

fold_left [WeakTopological]

Folding over the elements of a weak topological ordering.

fold_pred [Sig_pack.S]
fold_pred [Sig.G]
fold_pred_e [ChaoticIteration.G]
fold_pred_e [Flow.G_GOLDBERG_TARJAN]
fold_pred_e [Sig_pack.S]
fold_pred_e [Sig.G]
fold_stable [Sig_pack.S.Topological]
fold_succ [Strat.G]
fold_succ [Minsep.G]
fold_succ [Coloring.GM]
fold_succ [Coloring.G]
fold_succ [Traverse.G]
fold_succ [Sig_pack.S]
fold_succ [Sig.G]
fold_succ_e [Flow.G_GOLDBERG_TARJAN]
fold_succ_e [Sig_pack.S]
fold_succ_e [Sig.G]
fold_vertex [Clique.G]
fold_vertex [Contraction.G]
fold_vertex [Leaderlist.G]
fold_vertex [Fixpoint.G]
fold_vertex [Strat.G]
fold_vertex [Minsep.G]
fold_vertex [Gmap.V_SRC]
fold_vertex [Dominator.G]
fold_vertex [Kruskal.G]
fold_vertex [Coloring.GM]
fold_vertex [Coloring.G]
fold_vertex [Traverse.G]

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_vertex [Path.G]
fold_vertex [Sig_pack.S]
fold_vertex [Sig.G]

Fold on all vertices of a graph.

ford_fulkerson [Sig_pack.S]

Ford Fulkerson maximum flow algorithm

fprint_graph [Graphviz.Neato]

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

fprint_graph [Graphviz.Dot]

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

full [Classic.S]

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

full [Sig_pack.S.Classic]

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

G
game [Strat.Algo]

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

get [Coloring.GM.Mark]
get [Traverse.GM.Mark]
get [Traverse.Bfs]
get [Traverse.Dfs]
get [Sig_pack.S.Mark]
get [Sig.MARK]

Mark value (in O(1)).

get_initial [Strat.PLAYER]
get_subgraph [Graphviz.GraphWithDotAttrs]

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

gnp [Rand.S]

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

gnp [Sig_pack.S.Rand]

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 [Rand.S]

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

gnp_labeled [Sig_pack.S.Rand]

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

goldberg_tarjan [Sig_pack.S]

Goldberg-Tarjan maximum flow algorithm

graph [Rand.Planar.S]

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

graph [Rand.S]

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

graph [Sig_pack.S.Rand]

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

graph_attributes [Graphviz.GraphWithDotAttrs]

Graph, vertex and edge attributes.

H
handle_error [Graphviz.Neato]
has_cycle [Traverse.Mark]

has_cycle g checks for a cycle in g.

has_cycle [Traverse.Dfs]

has_cycle g checks for a cycle in g.

has_cycle [Sig_pack.S.Marking]
has_cycle [Sig_pack.S.Dfs]
hash [Cliquetree.CliqueTree.CliqueTreeV]
hash [Cliquetree.CliqueTree.CliqueV]
hash [Gml.G.V]
hash [Util.DataV]
hash [Sig_pack.S.V]
hash [Sig.COMPARABLE]
hash [Sig.HASHABLE]
I
idom_to_dom [Dominator.S]
idom_to_dom_tree [Dominator.S]

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

idom_to_dominators [Dominator.S]
idom_to_idoms [Dominator.S]
in_circle [Delaunay.CCC]

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 [Sig_pack.S]

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

in_degree [Sig.G]

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

init [Kruskal.UNIONFIND]
intersect [Oper.S]

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 [Sig_pack.S]

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 [Cliquetree.CliqueTree]

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

is_directed [Graphml.G]
is_directed [Coloring.GM]
is_directed [Coloring.G]
is_directed [Traverse.G]
is_directed [Sig_pack.S]

is this an implementation of directed graphs?

is_directed [Sig.G]

Is this an implementation of directed graphs?

is_empty [Sig_pack.S]
is_empty [Sig.G]
is_final [Strat.PLAYER]
iter [Topological.Make_stable]
iter [Topological.Make]

iter action calls action node repeatedly.

iter [Traverse.Bfs]
iter [Traverse.Dfs]

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 [Delaunay.Triangulation]

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

iter [Sig_pack.S.Topological]
iter [Sig_pack.S.Bfs]
iter [Sig_pack.S.Dfs]

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_component [Traverse.Bfs]
iter_component [Traverse.Dfs]
iter_component [Sig_pack.S.Bfs]
iter_component [Sig_pack.S.Dfs]
iter_edges [Components.U]
iter_edges [Sig_pack.S]
iter_edges [Sig.G]

Iter on all edges of a graph.

iter_edges_e [Graphml.G]
iter_edges_e [Gml.G]
iter_edges_e [Prim.G]
iter_edges_e [Kruskal.G]
iter_edges_e [Sig_pack.S]
iter_edges_e [Sig.G]

Iter on all edges of a graph.

iter_pred [Sig_pack.S]
iter_pred [Sig.G]
iter_pred_e [Flow.G_FORD_FULKERSON]
iter_pred_e [Sig_pack.S]
iter_pred_e [Sig.G]
iter_stable [Sig_pack.S.Topological]
iter_succ [WeakTopological.G]
iter_succ [Minsep.G]
iter_succ [Dominator.G]
iter_succ [Topological.G]
iter_succ [Coloring.GM]
iter_succ [Coloring.G]
iter_succ [Traverse.GM]
iter_succ [Traverse.G]
iter_succ [Path.G]
iter_succ [Components.G]
iter_succ [Sig_pack.S]
iter_succ [Sig.G]
iter_succ_e [Prim.G]
iter_succ_e [Flow.G_FORD_FULKERSON]
iter_succ_e [Path.G]
iter_succ_e [Sig_pack.S]
iter_succ_e [Sig.G]
iter_triangles [Delaunay.Triangulation]
iter_vertex [WeakTopological.G]
iter_vertex [Graphml.G]
iter_vertex [Minsep.G]
iter_vertex [Gml.G]
iter_vertex [Dominator.G]
iter_vertex [Prim.G]
iter_vertex [Topological.G]
iter_vertex [Coloring.GM]
iter_vertex [Coloring.G]
iter_vertex [Traverse.GM]
iter_vertex [Traverse.G]

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_vertex [Path.G]
iter_vertex [Components.U]
iter_vertex [Components.G]
iter_vertex [Sig_pack.S]
iter_vertex [Sig.G]

Iter on all vertices of a graph.

J
join [ChaoticIteration.Data]

Operation to join data when several paths meet.

join [Fixpoint.Analysis]

operation how to join data when paths meet

L
label [Cliquetree.CliqueTree.CliqueTreeV]
label [Cliquetree.CliqueTree.CliqueV]
label [Gml.G.E]
label [Gml.G.V]
label [Prim.G.E]
label [Flow.G_FORD_FULKERSON.E]
label [Kruskal.G.E]
label [Path.G.E]
label [Util.DataV]
label [Sig_pack.S.E]
label [Sig_pack.S.V]
label [Sig.EDGE]

Get the label of an edge.

label [Sig.VERTEX]
labeled [Rand.S]

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

labeled [Sig_pack.S.Rand]

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

leader_lists [Leaderlist.Make]

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

list_from_vertex [Oper.Neighbourhood]

Neighbourhood of a vertex as a list.

list_from_vertices [Oper.Neighbourhood]

Neighbourhood of a list of vertices as a list.

list_of_allminsep [Minsep.MINSEP]

Less efficient that allminsep

M
make [Imperative.Matrix.S]

Creation.

map [Gmap.Edge]

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

map [Gmap.Vertex]

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

map_vertex [Sig_pack.S]

map iterator on vertex

map_vertex [Sig.G]

Map on all vertices of a graph.

max_capacity [Flow.FLOW]
maxflow [Flow.Ford_Fulkerson]

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

maxflow [Flow.Goldberg_Tarjan]

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

maximalcliques [Clique.Bron_Kerbosch]

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

maxwidth [Cliquetree.CliqueTree]

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

mcs_clique [Cliquetree.CliqueTree]

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

mcsm [Mcs_m.MaximalCardinalitySearch.I]

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 [Mcs_m.MaximalCardinalitySearch.P]

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 [Md.I]

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 [Md.P]

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'

mem_edge [Sig_pack.S]
mem_edge [Sig.G]
mem_edge_e [Sig_pack.S]
mem_edge_e [Sig.G]
mem_vertex [Strat.G]
mem_vertex [Sig_pack.S]
mem_vertex [Sig.G]
merge_edges_e [Merge.I]
merge_edges_e [Merge.S]

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

merge_edges_with_label [Merge.I]
merge_edges_with_label [Merge.S]

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.

merge_ends [Merge.I]
merge_ends [Merge.S]

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

merge_isolabelled_edges [Merge.I]
merge_isolabelled_edges [Merge.S]

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.

merge_scc [Merge.I]
merge_scc [Merge.S]

The vertex of every strongly connected component are identified.

merge_starts [Merge.I]
merge_starts [Merge.S]

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

merge_vertex [Merge.I]
merge_vertex [Merge.S]

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

min_capacity [Flow.FLOWMIN]
min_cutset [Mincut.Make]

Find a minimal cutset.

mirror [Oper.S]

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 [Sig_pack.S]

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.

N
nb_edges [Flow.G_GOLDBERG_TARJAN]
nb_edges [Sig_pack.S]
nb_edges [Sig.G]
nb_vertex [Dominator.G]
nb_vertex [Flow.G_GOLDBERG_TARJAN]
nb_vertex [Coloring.GM]
nb_vertex [Coloring.G]
nb_vertex [Path.G]
nb_vertex [Sig_pack.S]
nb_vertex [Sig.G]
next [Strat.STRAT]
O
out_degree [Coloring.GM]
out_degree [Coloring.G]
out_degree [Sig_pack.S]

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

out_degree [Sig.G]

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

output_graph [Graphviz.Neato]

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

output_graph [Graphviz.Dot]

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

P
parse [Dot.Parse]

Parses a dot file

parse [Gml.Parse]
parse_bounding_box_and_clusters [Dot.Parse]

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

parse_dot_ast [Dot]
parse_dot_file [Sig_pack.S]
parse_gml_file [Sig_pack.S]
postfix [Traverse.Dfs]

applies only a postfix function.

postfix [Sig_pack.S.Dfs]

applies only a postfix function

postfix_component [Traverse.Dfs]
postfix_component [Sig_pack.S.Dfs]
pred [Leaderlist.G]
pred [Fixpoint.G]
pred [Dominator.G]
pred [Sig_pack.S]

pred g v returns the predecessors of v in g.

pred [Sig.G]

pred g v returns the predecessors of v in g.

pred_e [Fixpoint.G]
pred_e [Sig_pack.S]

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

pred_e [Sig.G]

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

prefix [Traverse.Dfs]

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

prefix [Sig_pack.S.Dfs]

applies only a prefix function

prefix_component [Traverse.Dfs]
prefix_component [Sig_pack.S.Dfs]
print [Graphml.Print]

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

print [Gml.Print]
print_gml [Sig_pack.S]
print_gml_file [Sig_pack.S]
R
random_few_edges [Rand.S]
random_many_edges [Rand.S]
recurse [ChaoticIteration.Make]

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

recursive_scc [WeakTopological.Make]

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 [Builder.S]
remove_edge [Sig_pack.S]

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

remove_edge [Sig.I]

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

remove_edge [Sig.P]

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

remove_edge_e [Builder.S]
remove_edge_e [Sig_pack.S]

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

remove_edge_e [Sig.I]

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

remove_edge_e [Sig.P]

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

remove_vertex [Builder.S]
remove_vertex [Sig_pack.S]

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

remove_vertex [Sig.I]

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

remove_vertex [Sig.P]

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

replace_by_transitive_reduction [Oper.S]

replace_by_transitive_reduction ?reflexive g replaces g by its transitive reduction.

replace_by_transitive_reduction [Sig_pack.S]

replace_by_transitive_reduction ?reflexive g replaces g by its transitive reduction.

S
scc [Components.Make]

scc g computes the strongly connected components of g.

scc [Sig_pack.S.Components]

strongly connected components

scc_array [Components.Make]

scc_array g computes the strongly connected components of g.

scc_array [Sig_pack.S.Components]
scc_list [Components.Make]

scc_list g computes the strongly connected components of g.

scc_list [Sig_pack.S.Components]
set [Coloring.GM.Mark]
set [Traverse.GM.Mark]
set [Sig_pack.S.Mark]
set [Sig.MARK]

Set the mark of the given vertex.

set_command [Graphviz.Neato]

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

set_data [Util.DataV]
set_from_vertex [Oper.Neighbourhood]

Neighbourhood of a vertex as a set.

set_from_vertices [Oper.Neighbourhood]

Neighbourhood of a list of vertices as a set.

set_of_allminsep [Minsep.MINSEP]

Less efficient that allminsep

shortest_path [Path.Dijkstra]

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

shortest_path [Sig_pack.S]

Dijkstra's shortest path algorithm.

spanningtree [Prim.Make]
spanningtree [Kruskal.Generic]
spanningtree [Kruskal.Make]
spanningtree [Sig_pack.S]

Kruskal algorithm

spanningtree_from [Prim.Make]
src [ChaoticIteration.G.E]
src [Graphml.G.E]
src [Fixpoint.G.E]
src [Gml.G.E]
src [Prim.G.E]
src [Flow.G_FORD_FULKERSON.E]
src [Kruskal.G.E]
src [Path.G.E]
src [Sig_pack.S.E]
src [Sig.EDGE]

Edge origin.

start [Traverse.Bfs]
start [Traverse.Dfs]
step [Traverse.Bfs]
step [Traverse.Dfs]
strategy [Strat.Algo]

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

strategyA [Strat.Algo]

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

sub [Flow.FLOW]
sub [Path.WJ]

Subtraction of weights.

succ [Clique.G]
succ [Mincut.G]
succ [Leaderlist.G]
succ [Fixpoint.G]
succ [Strat.G]
succ [Minsep.G]
succ [Dominator.G]
succ [Sig_pack.S]

succ g v returns the successors of v in g.

succ [Sig.G]

succ g v returns the successors of v in g.

succ_e [Fixpoint.G]
succ_e [Sig_pack.S]

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

succ_e [Sig.G]

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

T
transitive_closure [Oper.S]

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

transitive_closure [Sig_pack.S]

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

transitive_reduction [Oper.S]

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

transitive_reduction [Sig_pack.S]

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

triangulate [Md.I]

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

triangulate [Md.P]

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

triangulate [Mcs_m.MaximalCardinalitySearch.I]

triangulate g triangulates g using the MCS-M algorithm

triangulate [Mcs_m.MaximalCardinalitySearch.P]

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

triangulate [Delaunay.Triangulation]

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

turn [Strat.PLAYER]
U
union [Kruskal.UNIONFIND]
union [Oper.S]

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 [Sig_pack.S]

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.

V
vertex [Cliquetree.CliqueTree.CliqueV]
vertex_attributes [Graphviz.GraphWithDotAttrs]
vertex_name [Graphviz.GraphWithDotAttrs]
vertex_only [Classic.S]

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

vertex_only [Sig_pack.S.Classic]

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

vertices [Cliquetree.CliqueTree.CliqueTreeE]

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

W
weight [Sig.WEIGHT]

Get the weight of an edge.

widening [ChaoticIteration.Data]

The widening operator.

Z
zero [Flow.FLOW]
zero [Sig.WEIGHT]

Neutral element for Sig.WEIGHT.add.