prbnmcn-stats 0.0.8 · OCaml Package

Graph statistics generic on an undirected Graph implementation.

Parameters

module Graph : Stats_intf.Graph

Signature

type t = Graph.t

t is the type of (undirected) graphs.

type vertex = Graph.vertex

vertex is the type of vertices.

type matrix = (int * int, float) Stats_intf.fin_fun

module Undirected_edge : 
  Basic_structures.Basic_intf.Std with type t = vertex * vertex

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

Table is a hashtable module with undirected edges as keys.

module Vertex_set : Set.S with type elt = vertex

Vertex_set handles sets of vertices.

module Vertex_table : Hashtbl.S with type key = vertex

Vertex_table is a hashtable module with vertices as keys.

module Vertex_bij : Finbij.S with type elt = vertex

Finite bijections between vertices and integers.

val adjacency_matrix : t -> matrix * 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 -> matrix * 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 connected_component : t -> vertex -> (vertex -> bool) -> vertex Seq.t

connected_component g v predicate produces the connected component of v in g that satisfies the given predicate.

val connected_component_ : 
  t ->
  vertex ->
  (vertex -> bool) ->
  unit Vertex_table.t

See connected_component. Returns a table instead of a Seq.t.

val is_induced_subgraph_connected : t -> (vertex -> bool) -> bool

is_induced_subgraph_connected g predicate is true if the subgraph of g induced by predicate is connected.

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.

module Tree : sig ... end

Tree defines a type of trees and functions to construct, deconstruct and iterate on those trees.

val aldous_broder : t -> vertex -> (vertex -> bool) -> Tree.t Gen.t

aldous_broder g v0 predicate returns a uniform sampler for spanning trees in the subgraph containing v0 and satisfying predicate, using the Aldous-Broder algorithm.

package prbnmcn-stats

Parameters

Signature