libgraph 1.10 → 1.11

raw patch · 3 files changed

+23/−19 lines, 3 files

Files

• Data/Graph/Libgraph.hs +1/−0
• Data/Graph/Libgraph/AlgoDebug.hs +20/−17
• libgraph.cabal +2/−2

@@ -25,6 +25,7 @@ , findFaulty , findFaulty_dag , next_step+, next_daq , Judgement(..) , AssistedMessage(..) , showWith

@@ -34,23 +34,26 @@        | otherwise    = Just v                 -- v is an unassed node   findJust mvs = case (find (isJust) mvs) of Just justv -> justv; Nothing -> Nothing -{- A more efficient next_step implementation; that starts from the-   current computation statement. The problem with this implementation-   is that it can get "stuck" in trees with nodes that already have some-   judged nodes (e.g. due to free exploration or using property-assisted-   algorithmic debugging.)+{- Divide and Query: Try to find a node that divides the tree in two. -}+next_daq :: Ord v => Graph v a -> (v -> Judgement) -> v+next_daq tree j = snd (foldr1 f ws)+  where c  = succCache tree+        ws = weight j c+               -- start from deepest wrong node; if no wrong nodes start from the root node+               (case start j c (root tree) of (Just r) -> r; Nothing -> root tree)+        w  = (maximum (map fst ws)) `div` 2 -- the "ideal" weight+        f x y | abs (w - (fst x)) < abs (w - (fst y)) = x+              | otherwise                             = y -next_step :: Eq v => Graph v a -> (v -> Judgement) -> v -> v-next_step tree j v -  | j v == Wrong || v == root tree =-    case filter (\w -> j w == Unassessed) (succs tree v) of-                      []    -> v-                      (w:_) -> w+weight :: (v -> Judgement) -> (v -> [v]) -> v -> [(Int,v)]+weight j c v | j v == Right = [(0,v)]        -- discard subtrees that are right+             | otherwise    = (w,v) : foldr (++) [] vs+  where vs = map (weight j c) (c v)          -- weighted children+        w  = 1 + (sum $ map (fst . head) vs) -- weight of v -  | j v == Right =-    case preds tree v of-                      []    -> v-                      (w:_) -> next_step tree j w -  | otherwise = v -- j v is Unassessed or Assisted--}+-- find starting point (i.e. the "deepest" node that is wrong)+start :: (v -> Judgement) -> (v -> [v]) -> v -> Maybe v+start j c v = case filter isJust (map (start j c) (c v)) of+  []    -> if j v == Wrong then Just v else Nothing+  (w:_) -> w

@@ -1,5 +1,5 @@ Name:           libgraph
-Version:        1.10
+Version:        1.11
 Homepage:       http://maartenfaddegon.nl
 Synopsis:       Store and manipulate data in a graph.
 Description:    A graph type, analysis of graphs and manipulation of graphs.
@@ -7,7 +7,7 @@ license-file:   LICENSE
 Author:         Maarten Faddegon
 Maintainer:     libgraph@maartenfaddegon.nl
-Copyright:      (c) 2014 Maarten Faddegon
+Copyright:      (c) 2014-2016 Maarten Faddegon
 Category:       Algorithms, Data Structures
 Build-Type:     Simple
 Cabal-Version:  >= 1.10