darcs-2.16.1: a distributed, interactive, smart revision control system

Darcs.Util.Graph

Synopsis

Documentation

Undirected graph represented as a Vector of adjacency VertexSets.

type Vertex = Int Source #

Vertices are represented as Int.

type VertexSet = [Vertex] Source #

Set of vertices, represented as a list for efficiency (yes, indeed).

data Component Source #

Constructors

 Component Graph VertexSet
Instances
 Source # Instance detailsDefined in Darcs.Util.Graph MethodsshowList :: [Component] -> ShowS #

Algorithms

ltmis :: (Bool, Bool) -> Component -> [VertexSet] Source #

Determine the maximal independent sets in a Component of a Graph.

bkmis :: Graph -> [VertexSet] Source #

The classic Bron-Kerbosch algorithm for determining the maximal independent sets in a Graph.

Split a Graph into connected components. For efficiency we don't represent the result as a list of Graphs, but rather of VertexSets.

Generating graphs

genGraphs :: Int -> [Graph] Source #

Enumerate all (simple) graphs of a given size (number of vertices).

Properties

Whether ltmis is equivalent to bkmis.

Whether ltmis generates only maximal independent sets.

Whether ltmis generates all maximal independent sets.

Complete specification of the components function.