module Data.Graph.Inductive.Query.Ear where
import Data.Function
import Data.Graph.Inductive.Basic
import Data.Graph.Inductive.Example
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Query
import Data.Graph.Inductive.Tree
import Data.List
import Data.Tree
import Data.Tuple
ears :: forall gr . DynGraph gr => gr () () -> gr () Int
ears g
| isConnected g = gWs
| otherwise = error "called ears on disconnected graph"
where
t :: Tree Node
[t] = dff' g
tps = treeToPaths t
te = treeToEdges t
g' = mkUGraph (nodes g) ((edges g \\ te) \\ (map swap te)) `asTypeOf` g
gE :: gr () Int = mkGraph (labNodes g') (map (lca tps) $ labEdges g')
gE' = mkGraph (labNodes gE) (labEdges gE ++ map (\(a,b) -> (a,b,0)) (te ++ map swap te))
teWs = map (shortestPaths gE') te
gWs = mkGraph (labNodes g') (labEdges gE ++ teWs ++ map swap12 teWs)
shortestPaths :: Gr () Int -> Edge -> LEdge Int
shortestPaths g (u,v) = (u,v,spLength u v g') where
g' = delEdge (u,v) $ delEdge (v,u) g
lca :: [[Node]] -> (LEdge ()) -> (LEdge Int)
lca ps (u,v,())
| any null ps = error $ "null path: " ++ show ps
| otherwise = (u,v,) . (subtract 1) . length . filter (uncurry (==)) $ zip u' v' where
[u'] = filter ((==u) . last) ps
[v'] = filter ((==v) . last) ps
swap12 (a,b,c) = (b,a,c)
sel3 (_,_,s) = s
treeToEdges :: Tree Node -> [Edge]
treeToEdges (Node _ []) = []
treeToEdges (Node k xs) = map ((k,) . rootLabel) xs ++ concatMap treeToEdges xs
treeToPaths :: Tree Node -> [[Node]]
treeToPaths (Node k []) = [[k]]
treeToPaths (Node k xs) = [[k]] ++ [ (k:ys) | ys <- concatMap treeToPaths xs ]