{- densest subgraph (global/in-neightbor/out-neighbor aggregations)
   (NOTE: this is corrected version.) -}

data DsRecord =
  DsRecord { ins :: Bool, inst :: Bool, ft :: Double, deg :: Double }
  deriving (Eq, Show)

ds g =
  let epsilon = 0.01                                                      ;
      ds_0 v = DsRecord True True 0.0 0.0                                 ;
      ds_t v prev curr =
        let deg' = sum [ 1.0 | (e,u) <- is v, prev u.^ins ]               ;
            nDeg = sum [ curr u.^deg | u <- g, prev u.^ins ]              ;
            nS = sum [ 1.0 | u <- g, prev u.^ins ]                        ;
            f = 2.0 * (1.0 + epsilon) * (nDeg / 2.0 / nS)                 ;
            ina = deg' <= f                                               ;
            ins' = prev v.^ins && not ina                                 ;
            inst' = if f >= prev v.^ft then prev v.^ins else prev v.^inst ;
            ft' = f `max` (prev v.^ft)
        in DsRecord ins' inst' ft' deg'
  in fregel ds_0 ds_t (Until (\g -> and [ not (val u.^ins) | u <- g])) g 

{-
ds' g =
  let epsilon = 0.01                                                      ;
      ds_0 v = DsRecord True True 0.0 0.0                                 ;
      ds_t v prev curr =
        let deg' = sum [ 1.0 | (e,u) <- is v, prev u.^ins ]               ;
            nDeg = sum [ curr u.^deg | u <- gof v, prev u.^ins ]          ;
            nS = sum [ 1.0 | u <- gof v, prev u.^ins ]                    ;
            f = 2.0 * (1.0 + epsilon) * (nDeg / 2.0 / nS)                 ;
            ina = deg' <= f                                               ;
            ins' = prev v.^ins && not ina                                 ;
            inst' = if f >= prev v.^ft then prev v.^ins else prev v.^inst ;
            ft' = f `max` (prev v.^ft)
        in DsRecord ins' inst' ft' deg'
  in fregel ds_0 ds_t (Until (\g -> and [ not (val u.^ins) | u <- g])) g 
-}

ds01 g =
  let epsilon = 0.1                                                       ;
      ds_0 v = DsRecord True True 0.0 0.0                                 ;
      ds_t v prev curr =
        let deg' = sum [ 1.0 | (e,u) <- is v, prev u.^ins ]               ;
            nDeg = sum [ curr u.^deg | u <- g, prev u.^ins ]              ;
            nS = sum [ 1.0 | u <- g, prev u.^ins ]                        ;
            f = 2.0 * (1.0 + epsilon) * (nDeg / 2.0 / nS)                 ;
            ina = deg' <= f                                               ;
            ins' = prev v.^ins && not ina                                 ;
            inst' = if f >= prev v.^ft then prev v.^ins else prev v.^inst ;
            ft' = f `max` (prev v.^ft)
        in DsRecord ins' inst' ft' deg'
  in fregel ds_0 ds_t (Until (\g -> and [ not (val u.^ins) | u <- g])) g 

{-

*Main> ds graph4
[V 0 DsRecord {ins = False, inst = False, ft = 3.0300000000000002, deg = 0.0} [(1,v2)] [(1,v2)],
 V 1 DsRecord {ins = False, inst = False, ft = 3.0300000000000002, deg = 0.0} [(1,v2)] [(1,v2)],
 V 2 DsRecord {ins = False, inst = False, ft = 3.0300000000000002, deg = 1.0} [(1,v0), (1,v1), (1,v3)] [(1,v3), (1,v0), (1,v1)],
 V 3 DsRecord {ins = False, inst = True, ft = 3.0300000000000002, deg = 3.0} [(1,v2), (1,v4), (1,v5), (1,v6)] [(1,v4), (1,v5), (1,v6), (1,v2)],
 V 4 DsRecord {ins = False, inst = True, ft = 3.0300000000000002, deg = 3.0} [(1,v3), (1,v5), (1,v6)] [(1,v5), (1,v6), (1,v3)],
 V 5 DsRecord {ins = False, inst = True, ft = 3.0300000000000002, deg = 3.0} [(1,v3), (1,v4), (1,v6), (1,v7)] [(1,v6), (1,v7), (1,v3), (1,v4)],
 V 6 DsRecord {ins = False, inst = True, ft = 3.0300000000000002, deg = 3.0} [(1,v3), (1,v4), (1,v5)] [(1,v3), (1,v4), (1,v5)],
 V 7 DsRecord {ins = False, inst = False, ft = 3.0300000000000002, deg = 1.0} [(1,v5)] [(1,v5)]]

*Main> ds01 graph4
[V 0 DsRecord {ins = False, inst = False, ft = 3.08, deg = 0.0} [(1,v2)] [(1,v2)],
 V 1 DsRecord {ins = False, inst = False, ft = 3.08, deg = 0.0} [(1,v2)] [(1,v2)],
 V 2 DsRecord {ins = False, inst = True, ft = 3.08, deg = 1.0} [(1,v0), (1,v1), (1,v3)] [(1,v3), (1,v0), (1,v1)],
 V 3 DsRecord {ins = False, inst = True, ft = 3.08, deg = 0.0} [(1,v2), (1,v4), (1,v5), (1,v6)] [(1,v4), (1,v5), (1,v6), (1,v2)],
 V 4 DsRecord {ins = False, inst = True, ft = 3.08, deg = 1.0} [(1,v3), (1,v5), (1,v6)] [(1,v5), (1,v6), (1,v3)],
 V 5 DsRecord {ins = False, inst = True, ft = 3.08, deg = 1.0} [(1,v3), (1,v4), (1,v6), (1,v7)] [(1,v6), (1,v7), (1,v3), (1,v4)],
 V 6 DsRecord {ins = False, inst = True, ft = 3.08, deg = 1.0} [(1,v3), (1,v4), (1,v5)] [(1,v3), (1,v4), (1,v5)],
 V 7 DsRecord {ins = False, inst = False, ft = 3.08, deg = 0.0} [(1,v5)] [(1,v5)]]

-}
{- something wrong with NDSLtoPregel::
  Main: NDSLtoPregel.hs:644:1-67: Non-exhaustive patterns in function hasAccessToCurr

{- another densest subgraph on the basis of the greedy algorithm
   presented in the ``denser than the densest'' paper. -}

ds_dtd1 g =
  let alpha = 1.0 / 3.0                                                   ;
      ds_0 v = DsRecord True True (-9999.0) 0.0                           ;
      ds_t v prev curr =
        let deg' = sum [ 1.0 | (e,u) <- is v, prev u.^ins ]               ;
            nDeg = sum [ curr u.^deg | u <- g, prev u.^ins ]              ;
            (minDeg, minDegId) =
               minimum [ (curr u.^deg, vid u) | u <- g, prev u.^ins ]     ;
            nS = sum [ 1.0 | u <- g, prev u.^ins ]                        ;
            f = nDeg / 2.0 - alpha * nS * (nS - 1.0) / 2.0                ;
            ina = (vid v == minDegId)                                     ;
            ins' = prev v.^ins && not ina                                 ;
            inst' = if f >= prev v.^ft then prev v.^ins else prev v.^inst ;
            ft' = f `max` (prev v.^ft)
        in DsRecord ins' inst' ft' deg'
  in fregel ds_0 ds_t (Until (\g -> and [ not (val u.^ins) | u <- g])) g 

{-

*Main> ds_dtd1 graph4
[V 0 DsRecord {ins = False, inst = False, ft = 4.0, deg = 0.0} [(1,v2)] [(1,v2)],
 V 1 DsRecord {ins = False, inst = False, ft = 4.0, deg = 0.0} [(1,v2)] [(1,v2)],
 V 2 DsRecord {ins = False, inst = False, ft = 4.0, deg = 0.0} [(1,v0), (1,v1), (1,v3)] [(1,v3), (1,v0), (1,v1)],
 V 3 DsRecord {ins = False, inst = True, ft = 4.0, deg = 1.0} [(1,v2), (1,v4), (1,v5), (1,v6)] [(1,v4), (1,v5), (1,v6), (1,v2)],
 V 4 DsRecord {ins = False, inst = True, ft = 4.0, deg = 1.0} [(1,v3), (1,v5), (1,v6)] [(1,v5), (1,v6), (1,v3)],
 V 5 DsRecord {ins = False, inst = True, ft = 4.0, deg = 1.0} [(1,v3), (1,v4), (1,v6), (1,v7)] [(1,v6), (1,v7), (1,v3), (1,v4)],
 V 6 DsRecord {ins = False, inst = True, ft = 4.0, deg = 0.0} [(1,v3), (1,v4), (1,v5)] [(1,v3), (1,v4), (1,v5)],
 V 7 DsRecord {ins = False, inst = False, ft = 4.0, deg = 0.0} [(1,v5)] [(1,v5)]]


{- Another densest subgraph on the basis of the local-search algorithm
   presented in the ``denser than the densest'' paper.
   This program is an ``increasing'' pattern, which means that, from a
   singleton set of vertices, it repeatedly adds such a vertex that most
   contributes to increasing the value of f(S). -}
-}
data DsDtdRecord =
  DsDtdRecord { b :: Bool, inr :: Bool, ns :: Double, ndeg :: Double,
                fs :: Double, alldeg :: Double, delta :: Double }
  deriving (Eq, Show)

ds_dtd2 g =
  let alpha = 1.0 / 3.0                                                   ;
      seed = 3                                                            ;
      ds_0 v = DsDtdRecord True (vid v == seed) 1.0 0.0 (-9999.0) 0.0 0.0 ;
      ds_t v prev curr =
        let delta' = sum [ 1.0 | (e,u) <- is v, prev u.^inr ]             ;
            alldeg' = sum [ 1.0 | (e,u) <- is v ]                         ;
            (maxDelta, maxAllDeg, maxDeltaId) =
               maximum [ (curr u.^delta, curr u.^alldeg, vid u) |
                         u <- g, prev u.^inr == False ]                   ;
            ns' = prev v.^ns + 1.0                                        ;
            ndeg' = prev v.^ndeg + maxDelta                               ;
            f = ndeg' - alpha * ns' * (ns' - 1.0) / 2.0                   ;
            b' = f >= prev v.^fs                                          ;
            inr' = if b' then prev v.^inr || vid v == maxDeltaId
                         else prev v.^inr                                 ;
            fs' = f `max` (prev v.^fs)
        in DsDtdRecord b' inr' ns' ndeg' fs' alldeg' delta'
  in fregel ds_0 ds_t (Until (\g -> not (or [ val u.^b | u <- g]))) g

{-

*Main> ds_dtd2 graph4
[V 0 DsDtdRecord {b = False, inr = False, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 1.0, delta = 0.0} [(1,v2)] [(1,v2)],
 V 1 DsDtdRecord {b = False, inr = False, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 1.0, delta = 0.0} [(1,v2)] [(1,v2)],
 V 2 DsDtdRecord {b = False, inr = False, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 3.0, delta = 1.0} [(1,v0), (1,v1), (1,v3)] [(1,v3), (1,v0), (1,v1)],
 V 3 DsDtdRecord {b = False, inr = True, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 4.0, delta = 3.0} [(1,v2), (1,v4), (1,v5), (1,v6)] [(1,v4), (1,v5), (1,v6), (1,v2)],
 V 4 DsDtdRecord {b = False, inr = True, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 3.0, delta = 3.0} [(1,v3), (1,v5), (1,v6)] [(1,v5), (1,v6), (1,v3)],
 V 5 DsDtdRecord {b = False, inr = True, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 4.0, delta = 3.0} [(1,v3), (1,v4), (1,v6), (1,v7)] [(1,v6), (1,v7), (1,v3), (1,v4)],
 V 6 DsDtdRecord {b = False, inr = True, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 3.0, delta = 3.0} [(1,v3), (1,v4), (1,v5)] [(1,v3), (1,v4), (1,v5)],
 V 7 DsDtdRecord {b = False, inr = False, ns = 5.0, ndeg = 7.0, fs = 4.0, alldeg = 1.0, delta = 1.0} [(1,v5)] [(1,v5)]]

-}
-}