Index of values

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 from the graph g.

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

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

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

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.

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

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

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

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 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 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.

Return 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.

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.

DOT output

The empty graph.

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

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

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

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.

Goldberg 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.

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 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 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.

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

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 iterator on vertex

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 the Goldberg 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'

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.

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

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).

scc g computes the strongly connected components of g.

strongly connected components

scc_list computes the strongly connected components of g.

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

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).

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).