1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
-- (c) 2000 - 2002 by Martin Erwig [see file COPYRIGHT]
-- | Maximum Independent Node Sets
module Data.Graph.Inductive.Query.Indep (
indep
) where
import Data.Graph.Inductive.Graph
first :: (a -> Bool) -> [a] -> a
first p = head . filter p
indep :: DynGraph gr => gr a b -> [Node]
indep g | isEmpty g = []
indep g = if length i1>length i2 then i1 else i2
where vs = nodes g
m = maximum (map (deg g) vs)
v = first (\v'->deg g v'==m) vs
(Just c,g') = match v g
i1 = indep g'
i2 = v:indep (delNodes (neighbors' c) g')
|
