package ocamlgraph
Module Pack.DigraphSource
Directed imperative graphs with edges and vertices labeled with integer.
Graph structure
abstract type of graphs
module V : sig ... endVertices
module E : sig ... endEdges
is this an implementation of directed graphs?
Graph constructors and destructors
Return an empty graph. Optionally, a size can be given, which should be on the order of the expected number of vertices that will be in the graph (for hash tables-based implementations). The graph grows as needed, so size is just an initial guess.
copy g returns a copy of g. Vertices and edges (and eventually marks, see module Mark) are duplicated.
add_vertex g v adds the vertex v from the graph g. Do nothing if v is already in g.
remove g v removes the vertex v from the graph g (and all the edges going from v in g). Do nothing if v is not in g.
add_edge g v1 v2 adds an edge from the vertex v1 to the vertex v2 in the graph g. Add also v1 (resp. v2) in g if v1 (resp. v2) is not in g. Do nothing if this edge is already in g.
add_edge_e g e adds the edge e in the graph g. Add also E.src e (resp. E.dst e) in g if E.src e (resp. E.dst e) is not in g. Do nothing if e is already in g.
remove_edge g v1 v2 removes the edge going from v1 to v2 from the graph g. Do nothing if this edge is not in g.
remove_edge_e g e removes the edge e from the graph g. Do nothing if e is not in g.
module Mark : sig ... endVertices contains integers marks, which can be set or used by some algorithms (see for instance module Marking below)
Size functions
Degree of a vertex
Membership functions
Successors and predecessors of a vertex
Labeled edges going from/to a vertex
Graph iterators
iter/fold on all vertices/edges of a graph
iter/fold on all labeled edges of a graph
Vertex iterators
Each iterator iterator f v g iters f to the successors/predecessors of v in the graph g and raises Invalid_argument if v is not in g.
iter/fold on all successors/predecessors of a vertex.
iter/fold on all edges going from/to a vertex.
Basic operations
vertex g i returns a vertex of label i in g. The behaviour is unspecified if g has several vertices with label i. Note: this function is inefficient (linear in the number of vertices); you should better keep the vertices as long as you create them.
transitive_closure ?reflexive g returns the transitive closure of g (as a new graph). Loops (i.e. edges from a vertex to itself) are added only if reflexive is true (default is false).
add_transitive_closure ?reflexive g replaces g by its transitive closure. Meaningless for persistent implementations (then acts as transitive_closure).
transitive_reduction ?reflexive g returns the transitive reduction of g (as a new graph). Loops (i.e. edges from a vertex to itself) are removed only if reflexive is true (default is false).
replace_by_transitive_reduction ?reflexive g replaces g by its transitive reduction. Meaningless for persistent implementations (then acts as transitive_reduction).
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. For undirected graphs, it simply returns a copy of g.
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. Edges of the returned graph are unlabeled.
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.
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.
Traversal
Graph generators
Strongly connected components
Classical algorithms
Dijkstra's shortest path algorithm. Weights are the labels.
Ford Fulkerson maximum flow algorithm
Goldberg-Tarjan maximum flow algorithm
bellman_ford g v finds a negative cycle from v, and returns it, or raises Not_found if there is no such cycle
Topological order
Input / Output
Displays the given graph using the external tools "dot" and "gv" and returns when gv's window is closed