Module `Graph.Make`Source

Graph statistics generic on an undirected Graph implementation.

Parameters

module Graph : Stats_intf.Graph

Signature

Sourcetype t = Graph.t

t is the type of (undirected) graphs.

Sourcetype vertex = Graph.vertex

vertex is the type of vertices.

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

Source

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.

Sourcemodule Table : Hashtbl.S with type key = Undirected_edge.t

Table is a hashtable module with undirected edges as keys.

Sourcemodule Vertex_set : Set.S with type elt = vertex

Vertex_set handles sets of vertices.

Sourcemodule Vertex_table : Hashtbl.S with type key = vertex

Vertex_table is a hashtable module with vertices as keys.

Sourcemodule Vertex_bij : Finbij.S with type elt = vertex

Finite bijections between vertices and integers.

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

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

Sourcetype distance_table = (vertex * vertex, Dist.t) Hashtbl.t

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

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

Sourceval volume : t -> int

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

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

Source

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

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

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

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

degree_dist g computes the degree distribution of g.

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

Sourcemodule Tree : sig ... end

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

Sourceval 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

Module Graph.MakeSource

Parameters

Signature

Module `Graph.Make`Source