fregel-1.2.0: sample-programs/ds.fgl
{- 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)]]
-}
-}