module BioInf.RNAdesign.Graph where
import Control.Arrow (first,second)
import Data.Graph.Inductive.Basic
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.PatriciaTree
import Data.Graph.Inductive.Query
import Data.List (nub,partition)
import Biobase.Secondary.Diagrams
independentGraphs xs
| null xs = error "You should give at least one structure. If you did, you have found a bug, yeah!"
| any ((/=lx).length) xs = error $ "At least one structure with different length was found" ++ show xs
| otherwise = independentComponents g
where
lx = length $ head xs
g = mkUnionGraph xs
mkUnionGraph = unions . map (pairlistToGraph . (mkD1S :: String -> D1Secondary))
unions :: Eq b => [Gr a b] -> Gr a b
unions [] = empty
unions xs@(x:_) = mkGraph (labNodes x) (nub $ concatMap labEdges xs) where
pairlistToGraph :: D1Secondary -> Gr () ()
pairlistToGraph d =
let (len, ps) = fromD1S d
in undir $ mkUGraph [0..len 1] ps
independentComponents :: DynGraph gr => gr () () -> [gr () ()]
independentComponents g = map f $ components g where
f ns = mkUGraph ns (edges g)
isBipartite :: DynGraph gr => gr a b -> Bool
isBipartite g = e && o where
(e,o) = both (null . edges) $ f g
f g = both (flip delNodes g . map fst) . partition (even . snd) $ level (fst $ head $ labNodes g) g
both f = second f . first f