Math.Combinatorics.Graph

Description

A module defining a polymorphic data type for (simple, undirected) graphs, together with constructions of some common families of graphs, new from old constructions, and calculation of simple properties of graphs.

Synopsis

Documentation

combinationsOf :: Integral t => t -> [a] -> [[a]]Source

combinationsOf k xs returns the subsets of xs of size k. If xs is in ascending order, then the returned list is in ascending order

data Graph a Source

Datatype for graphs, represented as a list of vertices and a list of edges. Both the list of vertices and the list of edges, and also the 2-element lists representing the edges, are required to be in ascending order, without duplicates.

Constructors

G [a] [[a]]

Instances

Eq a => Eq (Graph a)
Ord a => Ord (Graph a)
Show a => Show (Graph a)

graph :: Ord t => ([t], [[t]]) -> Graph tSource

Safe constructor for graph from lists of vertices and edges. graph (vs,es) checks that vs and es are valid before returning the graph.

nullGraph :: Graph Int Source

c :: Integral t => t -> Graph tSource

c n is the cyclic graph on n vertices

k :: Integral t => t -> Graph tSource

k n is the complete graph on n vertices

fromDigits :: Integral a => Graph [a] -> Graph aSource

Given a graph with vertices which are lists of small integers, eg [1,2,3], return a graph with vertices which are the numbers obtained by interpreting these as digits, eg 123. The caller is responsible for ensuring that this makes sense (eg that the small integers are all < 10)

fromBinary :: Integral a => Graph [a] -> Graph aSource

Given a graph with vertices which are lists of 0s and 1s, return a graph with vertices which are the numbers obtained by interpreting these as binary digits. For example, [1,1,0] -> 6.

diameter :: Ord t => Graph t -> Int Source

The diameter of a graph is maximum distance between two distinct vertices

girth :: Eq t => Graph t -> Int Source

The girth of a graph is the size of the smallest cycle that it contains. Note: If the graph contains no cycles, we return -1, representing infinity.

kneser :: Integral t => t -> t -> Graph [t]Source

kneser n k returns the kneser graph KG n,k - whose vertices are the k-element subsets of [1..n], with edges joining disjoint subsets