darcs-2.18.3: a distributed, interactive, smart revision control system
Safe HaskellSafe-Inferred
LanguageHaskell2010

Darcs.Util.Graph

Synopsis

Documentation

type Graph = Vector VertexSet Source #

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

Instances details
Show Component Source # 
Instance details

Defined in Darcs.Util.Graph

Methods

showsPrec :: Int -> Component -> ShowS #

show :: Component -> String #

showList :: [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.

components :: Graph -> [Component] Source #

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

genComponents :: Int -> [Component] Source #

Properties

prop_ltmis_eq_bkmis :: Graph -> Bool Source #

Whether ltmis is equivalent to bkmis.

prop_ltmis_maximal_independent_sets :: Component -> Bool Source #

Whether ltmis generates only maximal independent sets.

prop_ltmis_all_maximal_independent_sets :: Component -> Bool Source #

Whether ltmis generates all maximal independent sets.

prop_components :: Graph -> Bool Source #

Complete specification of the components function.