+{--
+negativeCycleCheck :: (Graph gr, Real w) => BFState s gr a b w ->
+ BFPath b w -> ST s ()
+negativeCycleCheck state path =
+ let getNodes (BFPath _ dst from) = dst : case from of
+ Nothing -> []
+ Just (_, p1) -> getNodes p1 in
+ let nodes = getNodes path in
+ if length (nub nodes) < length nodes
+ then error ("Negative cycle detected: " ++ show path)
+ else nop
+--}
+
+offerPath :: (Graph gr, Real w) => BFState s gr a b w ->
+ BFPath b w -> ST s ()
+offerPath state newPath@(BFPath newLen dest _) = do
+ oldMPath <- readArray (bfsMPaths state) dest
+ -- Is newPath the first path to dest or shorter than the existing one?
+ let adoptPath = case oldMPath of
+ Nothing -> True
+ Just (BFPath oldLen _ _) -> newLen < oldLen
+ if adoptPath
+ then do
+ -- Save the new path.
+ writeArray (bfsMPaths state) dest (Just newPath)
+ -- Mark dest as changed.
+ aqEnqueue (bfsChanged state) dest
+ nop
+ else nop -- Don't update anything.