package prbnmcn-stats

  1. Overview
  2. Docs
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 : Stdlib.Hashtbl.S with type key = Undirected_edge.t
module Vertex_bij : Finbij.S with type elt = vertex

Finite bijections between vertices and integers.

module Vertex_set : Stdlib.Set.S with type elt = vertex

Finite sets of vertices

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

val cut : t -> Vertex_set.t -> (vertex * vertex) list

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