module HGraph.Directed.Packing.Cycles.Internal where

import HGraph.Directed
import HGraph.Directed.Connectivity

import Prelude hiding (maximum)
import qualified Data.Map as M
import qualified Data.Set as S
import Data.Maybe

-- | A packing of pairwise arc-disjoint cycles of maximum size.
arcMaximumI :: t Int -> ([[Int]], Int)
arcMaximumI t Int
d =
  let (t Int
ld, [(Int, (Int, Int))]
iToA) = t Int -> (t Int, [(Int, (Int, Int))])
forall (t :: * -> *).
(DirectedGraph t, Adjacency t, Mutable t) =>
t Int -> (t Int, [(Int, (Int, Int))])
lineDigraphI t Int
d
      iToA' :: Map Int (Int, Int)
iToA' = [(Int, (Int, Int))] -> Map Int (Int, Int)
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList [(Int, (Int, Int))]
iToA
      ([[Int]]
packing', Int
k) = t Int -> ([[Int]], Int)
forall (t :: * -> *).
(DirectedGraph t, Mutable t, Adjacency t) =>
t Int -> ([[Int]], Int)
maximumI t Int
ld
  in (([Int] -> [Int]) -> [[Int]] -> [[Int]]
forall a b. (a -> b) -> [a] -> [b]
map (((Int, Int) -> Int) -> [(Int, Int)] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int, Int) -> Int
forall a b. (a, b) -> a
fst ([(Int, Int)] -> [Int])
-> ([Int] -> [(Int, Int)]) -> [Int] -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> (Int, Int)) -> [Int] -> [(Int, Int)]
forall a b. (a -> b) -> [a] -> [b]
map (Map Int (Int, Int)
iToA' Map Int (Int, Int) -> Int -> (Int, Int)
forall k a. Ord k => Map k a -> k -> a
M.!)) [[Int]]
packing', Int
k)

-- | Computes a packing of pairwise disjoint cycles of maximum size.
maximum :: (DirectedGraph t, Mutable t, Adjacency t) => t a -> ([[a]], Int)
maximum :: forall (t :: * -> *) a.
(DirectedGraph t, Mutable t, Adjacency t) =>
t a -> ([[a]], Int)
maximum t a
d = 
  let (t Int
di, [(Int, a)]
iToL) = t a -> (t Int, [(Int, a)])
forall a. t a -> (t Int, [(Int, a)])
forall (t :: * -> *) a.
DirectedGraph t =>
t a -> (t Int, [(Int, a)])
linearizeVertices t a
d
      ([[Int]]
cs, Int
k) =  t Int -> ([[Int]], Int)
forall (t :: * -> *).
(DirectedGraph t, Mutable t, Adjacency t) =>
t Int -> ([[Int]], Int)
maximumI t Int
di
      labels :: Map Int a
labels = [(Int, a)] -> Map Int a
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList [(Int, a)]
iToL
  in (([Int] -> [a]) -> [[Int]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map ((Int -> a) -> [Int] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (Map Int a
labels Map Int a -> Int -> a
forall k a. Ord k => Map k a -> k -> a
M.!)) [[Int]]
cs, Int
k)

-- | Computes a packing of pairwise disjoint cycles of maximum size.
-- Vertices of the input digraph must be labeled with integers from `0` to `n - 1`.
maximumI :: (DirectedGraph t, Mutable t, Adjacency t) => t Int -> ([[Int]], Int)
maximumI :: forall (t :: * -> *).
(DirectedGraph t, Mutable t, Adjacency t) =>
t Int -> ([[Int]], Int)
maximumI t Int
d
  | t Int -> Integer
forall b a. Integral b => t a -> b
forall (t :: * -> *) b a. (DirectedGraph t, Integral b) => t a -> b
numVertices t Int
d Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = ([], Int
0)
  | Bool
otherwise = 
      let loops :: [Int]
loops = [Int
v | Int
v <- t Int -> [Int]
forall a. t a -> [a]
forall (t :: * -> *) a. DirectedGraph t => t a -> [a]
vertices t Int
d, t Int -> (Int, Int) -> Bool
forall a. t a -> (a, a) -> Bool
forall (t :: * -> *) a. Adjacency t => t a -> (a, a) -> Bool
arcExists t Int
d (Int
v,Int
v)]
          d' :: t Int
d' = (Int -> t Int -> t Int) -> t Int -> [Int] -> t Int
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Int -> t Int -> t Int
forall a. a -> t a -> t a
forall (t :: * -> *) a. Mutable t => a -> t a -> t a
removeVertex t Int
d [Int]
loops
          components :: [[Int]]
components = t Int -> [[Int]]
forall {t :: * -> *} {a}.
(DirectedGraph t, Adjacency t, Mutable t, Ord a) =>
t a -> [[a]]
strongComponents t Int
d'
      in ([Int] -> ([[Int]], Int) -> ([[Int]], Int))
-> ([[Int]], Int) -> [[Int]] -> ([[Int]], Int)
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
           (\[Int]
c ([[Int]]
cs', Int
k') ->
              let h :: t Int
h = t Int -> Set Int -> t Int
forall {t :: * -> *} {a}.
(Mutable t, DirectedGraph t, Ord a) =>
t a -> Set a -> t a
inducedSubgraph t Int
d (Set Int -> t Int) -> Set Int -> t Int
forall a b. (a -> b) -> a -> b
$ [Int] -> Set Int
forall a. Ord a => [a] -> Set a
S.fromList [Int]
c
                  ([[Int]]
cs1, Int
k1) = Maybe ([[Int]], Int) -> ([[Int]], Int)
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe ([[Int]], Int) -> ([[Int]], Int))
-> Maybe ([[Int]], Int) -> ([[Int]], Int)
forall a b. (a -> b) -> a -> b
$ t Int -> Int -> Maybe ([[Int]], Int)
forall {t :: * -> *}.
(DirectedGraph t, Adjacency t, Mutable t) =>
t Int -> Int -> Maybe ([[Int]], Int)
maximumI' t Int
h Int
1
              in ([[Int]]
cs1 [[Int]] -> [[Int]] -> [[Int]]
forall a. [a] -> [a] -> [a]
++ [[Int]]
cs', Int
k1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k')
           )
           ((Int -> [Int]) -> [Int] -> [[Int]]
forall a b. (a -> b) -> [a] -> [b]
map (Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[]) [Int]
loops, [Int] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
loops)
           (([Int] -> Bool) -> [[Int]] -> [[Int]]
forall a. (a -> Bool) -> [a] -> [a]
filter (\[Int]
c -> Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ [Int] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([Int] -> Bool) -> [Int] -> Bool
forall a b. (a -> b) -> a -> b
$ Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
drop Int
1 [Int]
c) [[Int]]
components)

maximumI' :: t Int -> Int -> Maybe ([[Int]], Int)
maximumI' t Int
d Int
kMin 
  | t Int -> Integer
forall b a. Integral b => t a -> b
forall (t :: * -> *) b a. (DirectedGraph t, Integral b) => t a -> b
numVertices t Int
d Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
1 Bool -> Bool -> Bool
&& Int
kMin Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = ([[Int]], Int) -> Maybe ([[Int]], Int)
forall a. a -> Maybe a
Just ([], Int
0)
  | t Int -> Int
forall b a. Integral b => t a -> b
forall (t :: * -> *) b a. (DirectedGraph t, Integral b) => t a -> b
numVertices t Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
kMin) = Maybe ([[Int]], Int)
forall a. Maybe a
Nothing
  | t Int -> Integer
forall b a. Integral b => t a -> b
forall (t :: * -> *) b a. (DirectedGraph t, Integral b) => t a -> b
numArcs t Int
d Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Maybe ([[Int]], Int)
forall a. Maybe a
Nothing
  | Bool
otherwise = t Int -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
guessArc t Int
d Int
kMin ((Int, Int) -> Maybe ([[Int]], Int))
-> (Int, Int) -> Maybe ([[Int]], Int)
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> (Int, Int)
forall a. HasCallStack => [a] -> a
head (t Int -> [(Int, Int)]
forall a. t a -> [(a, a)]
forall (t :: * -> *) a. DirectedGraph t => t a -> [(a, a)]
arcs t Int
d)

maximumIWeak :: t Int -> Int -> Maybe ([[Int]], Int)
maximumIWeak t Int
d Int
kMin = 
  let components :: [[Int]]
components = t Int -> [[Int]]
forall {t :: * -> *} {a}.
(DirectedGraph t, Adjacency t, Mutable t, Ord a) =>
t a -> [[a]]
strongComponents t Int
d
      ds :: [t Int]
ds = ([Int] -> t Int) -> [[Int]] -> [t Int]
forall a b. (a -> b) -> [a] -> [b]
map (\[Int]
c -> t Int -> Set Int -> t Int
forall {t :: * -> *} {a}.
(Mutable t, DirectedGraph t, Ord a) =>
t a -> Set a -> t a
inducedSubgraph t Int
d (Set Int -> t Int) -> Set Int -> t Int
forall a b. (a -> b) -> a -> b
$ [Int] -> Set Int
forall a. Ord a => [a] -> Set a
S.fromList [Int]
c) ([[Int]] -> [t Int]) -> [[Int]] -> [t Int]
forall a b. (a -> b) -> a -> b
$ ([Int] -> Bool) -> [[Int]] -> [[Int]]
forall a. (a -> Bool) -> [a] -> [a]
filter (\[Int]
c -> Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ [Int] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([Int] -> Bool) -> [Int] -> Bool
forall a b. (a -> b) -> a -> b
$ Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
drop Int
1 [Int]
c) [[Int]]
components
      kMaxs :: [Int]
kMaxs = (t Int -> Int) -> [t Int] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (\t Int
h -> (t Int -> Int
forall b a. Integral b => t a -> b
forall (t :: * -> *) b a. (DirectedGraph t, Integral b) => t a -> b
numVertices t Int
h) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) [t Int]
ds
      kMax :: Int
kMax = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Int]
kMaxs
      solution :: Maybe ([[Int]], Int)
solution = (Maybe ([[Int]], Int), Int) -> Maybe ([[Int]], Int)
forall a b. (a, b) -> a
fst ((Maybe ([[Int]], Int), Int) -> Maybe ([[Int]], Int))
-> (Maybe ([[Int]], Int), Int) -> Maybe ([[Int]], Int)
forall a b. (a -> b) -> a -> b
$ ((t Int, Int)
 -> (Maybe ([[Int]], Int), Int) -> (Maybe ([[Int]], Int), Int))
-> (Maybe ([[Int]], Int), Int)
-> [(t Int, Int)]
-> (Maybe ([[Int]], Int), Int)
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr 
                 (\(t Int
h, Int
kMaxH) (Maybe ([[Int]], Int)
solution, Int
kMaxRest) ->
                     case Maybe ([[Int]], Int)
solution of
                       Maybe ([[Int]], Int)
Nothing -> (Maybe ([[Int]], Int)
forall a. Maybe a
Nothing, Int
kMaxRest)
                       Just ([[Int]]
cs', Int
k') ->
                         case t Int -> Int -> Maybe ([[Int]], Int)
maximumI' t Int
h (Int -> Maybe ([[Int]], Int)) -> Int -> Maybe ([[Int]], Int)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
1 (Int
kMin Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
kMaxRest Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
k' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
kMaxH) of
                           Maybe ([[Int]], Int)
Nothing -> (Maybe ([[Int]], Int)
forall a. Maybe a
Nothing, Int
kMaxRest)
                           Just ([[Int]]
csH, Int
kH) -> (([[Int]], Int) -> Maybe ([[Int]], Int)
forall a. a -> Maybe a
Just ([[Int]]
csH [[Int]] -> [[Int]] -> [[Int]]
forall a. [a] -> [a] -> [a]
++ [[Int]]
cs', Int
kH Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
k'), Int
kMaxRest Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
kMaxH))
                 ( ([[Int]], Int) -> Maybe ([[Int]], Int)
forall a. a -> Maybe a
Just ([], Int
0)
                 , Int
kMax)
                 ([t Int] -> [Int] -> [(t Int, Int)]
forall a b. [a] -> [b] -> [(a, b)]
zip [t Int]
ds [Int]
kMaxs)
  in case Maybe ([[Int]], Int)
solution of
      Maybe ([[Int]], Int)
Nothing -> Maybe ([[Int]], Int)
forall a. Maybe a
Nothing
      sol :: Maybe ([[Int]], Int)
sol@(Just ([], Int
0)) ->
        if Int
kMin Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 then
          Maybe ([[Int]], Int)
sol
        else
          Maybe ([[Int]], Int)
forall a. Maybe a
Nothing
      sol :: Maybe ([[Int]], Int)
sol@(Just ([[Int]]
cs, Int
k)) ->
        if Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
kMin then
          Maybe ([[Int]], Int)
sol
        else
          Maybe ([[Int]], Int)
forall a. Maybe a
Nothing

guessArc :: t Int -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
guessArc t Int
d Int
kMin (Int
v,Int
u) = 
  let withArc :: Maybe ([[Int]], Int)
withArc = t Int -> Int -> [Int] -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
forall (t :: * -> *).
(DirectedGraph t, Mutable t, Adjacency t) =>
t Int -> Int -> [Int] -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
packArc t Int
d Int
kMin [Int
u,Int
v] Int
v (Int
v,Int
u)
      d' :: t Int
d' = (Int, Int) -> t Int -> t Int
forall a. (a, a) -> t a -> t a
forall (t :: * -> *) a. Mutable t => (a, a) -> t a -> t a
removeArc (Int
v,Int
u) t Int
d
      withoutArc :: Int -> Maybe ([[Int]], Int)
withoutArc Int
kMin' = t Int -> Int -> Maybe ([[Int]], Int)
maximumIWeak t Int
d' Int
kMin'
  in case Maybe ([[Int]], Int)
withArc of
      Maybe ([[Int]], Int)
Nothing -> Int -> Maybe ([[Int]], Int)
withoutArc Int
kMin
      Just ([[Int]]
cs, Int
k) -> 
        case Int -> Maybe ([[Int]], Int)
withoutArc (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) of
          Maybe ([[Int]], Int)
Nothing -> Maybe ([[Int]], Int)
withArc
          Just ([[Int]]
cs', Int
k') -> if Int
k' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
k then ([[Int]], Int) -> Maybe ([[Int]], Int)
forall a. a -> Maybe a
Just ([[Int]]
cs', Int
k') else Maybe ([[Int]], Int)
withArc

packArc :: (DirectedGraph t, Mutable t, Adjacency t) 
        => t Int -> Int -> [Int] -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
packArc :: forall (t :: * -> *).
(DirectedGraph t, Mutable t, Adjacency t) =>
t Int -> Int -> [Int] -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
packArc t Int
d Int
kMin [Int]
cv Int
w (Int
v,Int
u)
  | Int
u Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
w = 
    let h :: t Int
h = (Int -> t Int -> t Int) -> t Int -> [Int] -> t Int
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Int -> t Int -> t Int
forall a. a -> t a -> t a
forall (t :: * -> *) a. Mutable t => a -> t a -> t a
removeVertex t Int
d ([Int] -> t Int) -> [Int] -> t Int
forall a b. (a -> b) -> a -> b
$ Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
drop Int
1 [Int]
cv
    in case t Int -> Int -> Maybe ([[Int]], Int)
forall {t :: * -> *}.
(DirectedGraph t, Adjacency t, Mutable t) =>
t Int -> Int -> Maybe ([[Int]], Int)
maximumIWeak t Int
h (Int
kMin Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) of
          Maybe ([[Int]], Int)
Nothing -> Maybe ([[Int]], Int)
forall a. Maybe a
Nothing
          Just ([[Int]]
cs, Int
k) -> ([[Int]], Int) -> Maybe ([[Int]], Int)
forall a. a -> Maybe a
Just (([Int] -> [Int]
forall a. [a] -> [a]
reverse ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
drop Int
1 [Int]
cv) [Int] -> [[Int]] -> [[Int]]
forall a. a -> [a] -> [a]
: [[Int]]
cs, Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  | Bool
otherwise = 
      let d1 :: t Int
d1 = ((Int, Int) -> t Int -> t Int) -> t Int -> [(Int, Int)] -> t Int
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Int, Int) -> t Int -> t Int
forall a. (a, a) -> t a -> t a
forall (t :: * -> *) a. Mutable t => (a, a) -> t a -> t a
removeArc t Int
d
                            [(Int
v,Int
x) | Int
x <- t Int -> Int -> [Int]
forall a. t a -> a -> [a]
forall (t :: * -> *) a. Adjacency t => t a -> a -> [a]
outneighbors t Int
d Int
v
                            , Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
u]
          d' :: t Int
d' = ((Int, Int) -> t Int -> t Int) -> t Int -> [(Int, Int)] -> t Int
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Int, Int) -> t Int -> t Int
forall a. (a, a) -> t a -> t a
forall (t :: * -> *) a. Mutable t => (a, a) -> t a -> t a
removeArc 
                     t Int
d1
                     [(Int
x,Int
u) | Int
x <- t Int -> Int -> [Int]
forall a. t a -> a -> [a]
forall (t :: * -> *) a. Adjacency t => t a -> a -> [a]
inneighbors t Int
d1 Int
u
                     , Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
v]
          candidates :: [Int]
candidates = [ Int
x | Int
x <- 
                              if Int
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
w then
                                t Int -> Int -> [Int]
forall a. t a -> a -> [a]
forall (t :: * -> *) a. Adjacency t => t a -> a -> [a]
outneighbors t Int
d' Int
u
                              else
                                (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/=Int
v) ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ t Int -> Int -> [Int]
forall a. t a -> a -> [a]
forall (t :: * -> *) a. Adjacency t => t a -> a -> [a]
outneighbors t Int
d' Int
u
                       , t Int -> Int -> Int -> Bool
forall {a} {t :: * -> *}.
(Adjacency t, Ord a) =>
t a -> a -> a -> Bool
reachable t Int
d' Int
x Int
w
                       ]
          bestChoice :: Maybe ([[Int]], Int) -> Int -> [Int] -> Maybe ([[Int]], Int)
bestChoice Maybe ([[Int]], Int)
solution Int
_ [] = Maybe ([[Int]], Int)
solution
          bestChoice Maybe ([[Int]], Int)
solution Int
kMin' (Int
x:[Int]
xs) = 
            case t Int -> Int -> [Int] -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
forall (t :: * -> *).
(DirectedGraph t, Mutable t, Adjacency t) =>
t Int -> Int -> [Int] -> Int -> (Int, Int) -> Maybe ([[Int]], Int)
packArc t Int
d' Int
kMin' (Int
x Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: [Int]
cv) Int
w (Int
u,Int
x) of
              Maybe ([[Int]], Int)
Nothing -> Maybe ([[Int]], Int) -> Int -> [Int] -> Maybe ([[Int]], Int)
bestChoice Maybe ([[Int]], Int)
solution Int
kMin' [Int]
xs
              sol :: Maybe ([[Int]], Int)
sol@(Just ([[Int]]
cs, Int
k')) -> Maybe ([[Int]], Int) -> Int -> [Int] -> Maybe ([[Int]], Int)
bestChoice Maybe ([[Int]], Int)
sol (Int
k' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) [Int]
xs
      in 
      if t Int -> (Int, Int) -> Bool
forall a. t a -> (a, a) -> Bool
forall (t :: * -> *) a. Adjacency t => t a -> (a, a) -> Bool
arcExists t Int
d (Int
u, Int
w) then
        Maybe ([[Int]], Int) -> Int -> [Int] -> Maybe ([[Int]], Int)
bestChoice Maybe ([[Int]], Int)
forall a. Maybe a
Nothing Int
kMin [Int
w]
      else
        Maybe ([[Int]], Int) -> Int -> [Int] -> Maybe ([[Int]], Int)
bestChoice Maybe ([[Int]], Int)
forall a. Maybe a
Nothing Int
kMin [Int]
candidates