1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
-- (c) 2000-2005 by Martin Erwig [see file COPYRIGHT]
-- | Inward directed trees as lists of paths.
module Data.Graph.Inductive.Internal.RootPath (
-- * Types
RTree,LRTree,
-- * Operations
getPath,getLPath,
getDistance,
getLPathNodes
) where
import Data.Graph.Inductive.Graph
type LRTree a = [LPath a]
type RTree = [Path]
first :: ([a] -> Bool) -> [[a]] -> [a]
first p xss = case filter p xss of
[] -> []
x:_ -> x
-- | Find the first path in a tree that starts with the given node.
--
-- Returns an empty list if there is no such path.
findP :: Node -> LRTree a -> [LNode a]
findP _ [] = []
findP v (LP []:ps) = findP v ps
findP v (LP (p@((w,_):_)):ps) | v==w = p
| otherwise = findP v ps
getPath :: Node -> RTree -> Path
getPath v = reverse . first ((==v) . head)
getLPath :: Node -> LRTree a -> LPath a
getLPath v = LP . reverse . findP v
-- | Return the distance to the given node in the given tree.
--
-- Returns 'Nothing' if the given node is not reachable.
getDistance :: Node -> LRTree a -> Maybe a
getDistance v t = case findP v t of
[] -> Nothing
(_,d):_ -> Just d
getLPathNodes :: Node -> LRTree a -> Path
getLPathNodes v = (\(LP p)->map fst p) . getLPath v
|
