A | |
add [Strat.STRAT] | |
add [Flow.FLOW] | |
add [Path.WEIGHT] |
Addition of weights.
|
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 [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 from the graph g .
|
add_vertex [Sig.P] | add_vertex g v adds the vertex v from the graph g .
|
allminsep [Minsep.MINSEP] | allminsep g computes the list of all minimal separators of g.
|
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.MARK] | clear g sets all the marks to 0 for all the vertices of g .
|
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.
|
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 [Flow.FLOW] | |
compare [Path.WEIGHT] |
Weights must be ordered.
|
compare [Util.DataV] | |
compare [Sig_pack.S.E] | |
compare [Sig_pack.S.V] | |
compare [Sig.COMPARABLE] | |
compare [Sig.ORDERED_TYPE] | |
compare [Sig.EDGE] | |
compare [Sig.VERTEX] | |
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.
|
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 [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] | |
dfs [Traverse.Mark] | dfs g traverses g in depth-first search, marking all nodes.
|
dfs [Sig_pack.S.Marking] | |
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.
|
dot_output [Sig_pack.S] |
DOT output
|
dst [Gml.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 | |
empty [Strat.STRAT] | |
empty [Gmap.E_DST] | |
empty [Gmap.V_DST] | |
empty [Builder.S] | |
empty [Sig.P] |
The empty graph.
|
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] | |
equal [Sig.VERTEX] | |
F | |
find [Kruskal.UNIONFIND] | |
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_vertex [Sig_pack.S] | vertex g i returns a vertex of label i in g .
|
flow [Flow.FLOW] | |
fold [Topological.Make] | fold action g seed allows iterating over the graph g
in topological order.
|
fold [Delaunay.Triangulation] | |
fold [Sig_pack.S.Topological] | |
fold_edges [Sig_pack.S] | |
fold_edges [Sig.G] |
Fold on all edges of a graph.
|
fold_edges_e [Gmap.E_SRC] | |
fold_edges_e [Sig_pack.S] | |
fold_edges_e [Sig.G] |
Fold on all edges of a graph.
|
fold_pred [Sig_pack.S] | |
fold_pred [Sig.G] | |
fold_pred_e [Flow.G_GOLDBERG] | |
fold_pred_e [Sig_pack.S] | |
fold_pred_e [Sig.G] | |
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] | |
fold_succ_e [Sig_pack.S] | |
fold_succ_e [Sig.G] | |
fold_vertex [Strat.G] | |
fold_vertex [Minsep.G] | |
fold_vertex [Gmap.V_SRC] | |
fold_vertex [Kruskal.G] | |
fold_vertex [Coloring.GM] | |
fold_vertex [Coloring.G] | |
fold_vertex [Traverse.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] | |
goldberg [Sig_pack.S] |
Goldberg 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.
|
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] | |
hash [Sig.VERTEX] | |
I | |
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 [Topological.G] | |
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 [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] | 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 [Sig_pack.S] | |
iter_edges [Sig.G] |
Iter on all edges of a graph.
|
iter_edges_e [Gml.G] | |
iter_edges_e [Flow.G_GOLDBERG] | |
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_succ [Minsep.G] | |
iter_succ [Components.G] | |
iter_succ [Topological.G] | |
iter_succ [Coloring.GM] | |
iter_succ [Coloring.G] | |
iter_succ [Traverse.GM] | |
iter_succ [Traverse.G] | |
iter_succ [Sig_pack.S] | |
iter_succ [Sig.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_vertex [Minsep.G] | |
iter_vertex [Gml.G] | |
iter_vertex [Flow.G_GOLDBERG] | |
iter_vertex [Components.G] | |
iter_vertex [Topological.G] | |
iter_vertex [Coloring.GM] | |
iter_vertex [Coloring.G] | |
iter_vertex [Traverse.GM] | |
iter_vertex [Traverse.G] | |
iter_vertex [Sig_pack.S] | |
iter_vertex [Sig.G] |
Iter on all vertices of a graph.
|
L | |
label [Cliquetree.CliqueTree.CliqueTreeV] | |
label [Cliquetree.CliqueTree.CliqueV] | |
label [Gml.G.E] | |
label [Gml.G.V] | |
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
|
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] | maxflow g v1 v2 searchs the maximal flow from source v1 to
terminal v2 using the Goldberg 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] | |
min_capacity [Flow.FLOW] | |
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 [Sig_pack.S] | |
nb_edges [Sig.G] | |
nb_vertex [Flow.G_GOLDBERG] | |
nb_vertex [Coloring.GM] | |
nb_vertex [Coloring.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] | |
parse [Gml.Parse] | |
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 [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 [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 [Gml.Print] | |
print_gml_file [Sig_pack.S] | |
R | |
random_few_edges [Rand.S] | |
random_many_edges [Rand.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 [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 [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 ).
|
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 computes the strongly connected components of g .
|
scc_array [Sig_pack.S.Components] | |
scc_list [Components.Make] | scc_list 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 [Kruskal.Generic] | |
spanningtree [Kruskal.Make] | |
spanningtree [Sig_pack.S] |
Kruskal algorithm
|
src [Gml.G.E] | |
src [Flow.G_FORD_FULKERSON.E] | |
src [Kruskal.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] | |
succ [Strat.G] | |
succ [Minsep.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 [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).
|
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_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 [Path.WEIGHT] |
Get the weight of an edge.
|
Z | |
zero [Flow.FLOW] | |
zero [Path.WEIGHT] |
Neutral element for
Path.WEIGHT.add .
|