prbnmcn-stats

Basic statistics
Library prbnmcn-stats
Module type Stats . Graph . Graph_statistics
type t

t is the type of (undirected) graphs.

type vertex

vertex is the type of vertices.

Undirected 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.t
module Vertex_bij : Finbij.S with type elt = vertex

Finite bijections between vertices and integers.

val adjacency_matrix : t -> (int * int) Linalg.Mat.Float.t * Vertex_bij.t

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

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

type distance_table = ( vertex * vertex, Dist.t ) Hashtbl.t
val floyd_warshall : t -> Dist.t Table.t

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.

val diameter : t -> Dist.t

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

volume g computes the sum over all vertices of their degree.

val degree_dist : t -> ( int, float ) Stats_intf.fin_prb

degree_dist g computes the degree distribution of g.