Graph statistics generic on an undirected Graph implementation.
module Graph : Stats_intf.Graphtype t = Graph.tt is the type of (undirected) graphs.
type vertex = Graph.vertexvertex is the type of vertices.
module Undirected_edge :
Basic_structures.Basic_intf.Std with type t = vertex * vertexUndirected edges. The equal and hash function are invariant under permutation of the vertices in the pair encoding the edge.
module Table : Hashtbl.S with type key = Undirected_edge.tmodule Vertex_bij : Finbij.S with type elt = vertexFinite bijections between vertices and integers.
module Vertex_set : Set.S with type elt = vertexFinite sets of vertices
val adjacency_matrix : t -> (int * int) Linalg.Mat.Float.t * Vertex_bij.tadjacency_matrix g computes the adjacency matrix of g as well as a bijection between the matrix dimensions and the vertices. The matrix is dense. Since the graph is undirected, it is also symmetric.
val laplacian : t -> (int * int) Linalg.Mat.Float.t * Vertex_bij.tlaplacian g computes the laplacian of the adjacency matrix, following the definition in 'Spectral Graph Theory', by Fan Chung Graham. The dimensions are the same as the adjacency matrix. A finite bijection is returned as well.
Floyd-warshall algorithm. Complexity is O(V^3) where V is the number of vertices of the graph. Returns a table of all distances between pairs of vertices.
Computes the diameter of the graph, ie the maximum over all pair of vertices of the shortest-path distance between those vertices.
val volume : t -> intvolume g computes the sum over all vertices of their degree.
val degree_dist : t -> (int, float) Stats_intf.fin_prbdegree_dist g computes the degree distribution of g.
val cut : t -> Vertex_set.t -> (vertex * vertex) listcut g set computes the cut associated to set, i.e. the subset of edges that have an end in set and the other end in the complement of set.