Darcs.Util.Graph

Documentation

type Graph = Vector VertexSet

Undirected graph represented as a Vector of adjacency VertexSets.

type Vertex = Int

Vertices are represented as Int.

type VertexSet = [Vertex]

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

data Component

Constructors

Component Graph VertexSet

Instances

Show Component

Defined in Darcs.Util.Graph

Methods

showsPrec :: Int -> Component -> ShowS

show :: Component -> String

showList :: [Component] -> ShowS

Algorithms

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

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

bkmis :: Graph -> [VertexSet]

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

components :: Graph -> [Component]

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]

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

genComponents :: Int -> [Component]

Properties

prop_ltmis_eq_bkmis :: Graph -> Bool

Whether ltmis is equivalent to bkmis.

prop_ltmis_maximal_independent_sets :: Component -> Bool

Whether ltmis generates only maximal independent sets.

prop_ltmis_all_maximal_independent_sets :: Component -> Bool

Whether ltmis generates all maximal independent sets.

prop_components :: Graph -> Bool

Complete specification of the components function.