src/Gargantext/Core/Viz/Graph/Bridgeness.hs

   1 {-|
   2 Module      : Gargantext.Core.Viz.Graph.Bridgeness
   3 Description : Bridgeness filter
   4 Copyright   : (c) CNRS, 2017-Present
   5 License     : AGPL + CECILL v3
   6 Maintainer  : team@gargantext.org
   7 Stability   : experimental
   8 Portability : POSIX
   9
  10 Let be a graph with partitions (from Louvain algo), Bridgeness uniformly
  11 filters inter-communities links.
  12
  13 TODO rewrite Bridgeness with "equivalence structurale" metrics (Confluence)
  14 TODO use Map LouvainNodeId (Map LouvainNodeId)
  15 -}
  16
  17
  18 module Gargantext.Core.Viz.Graph.Bridgeness -- (bridgeness)
  19   where
  20
  21 import Data.Graph.Clustering.Louvain.Utils (LouvainNode(..))
  22 import Data.List (concat, sortOn)
  23 import Data.Map (Map, fromListWith, lookup, toList, mapWithKey, elems)
  24 import Data.Maybe (catMaybes)
  25 import Data.Ord (Down(..))
  26 import Gargantext.Prelude
  27 import qualified Data.Map as DM
  28 import Gargantext.Core.Viz.Graph.Tools.IGraph (ClusterNode(..))
  29
  30 ----------------------------------------------------------------------
  31 type Partitions a = Map (Int, Int) Double -> IO [a]
  32 ----------------------------------------------------------------------
  33 class ToComId a where
  34   nodeId2comId :: a -> (NodeId,CommunityId)
  35
  36 type NodeId        = Int
  37 type CommunityId   = Int
  38
  39 ----------------------------------------------------------------------
  40 instance ToComId LouvainNode where
  41   nodeId2comId (LouvainNode i1 i2) = (i1, i2)
  42
  43 instance ToComId ClusterNode where
  44   nodeId2comId (ClusterNode i1 i2) = (i1, i2)
  45
  46 ----------------------------------------------------------------------
  47 ----------------------------------------------------------------------
  48 type Bridgeness = Double
  49
  50 bridgeness :: ToComId a => Bridgeness
  51            -> [a]
  52            -> Map (NodeId, NodeId) Double
  53            -> Map (NodeId, NodeId) Double
  54 bridgeness = bridgeness' nodeId2comId
  55
  56
  57 bridgeness' :: (a -> (Int, Int))
  58            -> Bridgeness
  59            -> [a]
  60            -> Map (Int, Int) Double
  61            -> Map (Int, Int) Double
  62 bridgeness' f b ns = DM.fromList
  63                    . concat
  64                    . DM.elems
  65                    . filterComs b
  66                    . groupEdges (DM.fromList $ map f ns)
  67
  68
  69 groupEdges :: (Ord a, Ord b1)
  70            => Map b1 a
  71            -> Map (b1, b1) b2
  72            -> Map (a, a) [((b1, b1), b2)]
  73 groupEdges m = fromListWith (<>)
  74              . catMaybes
  75              . map (\((n1,n2), d)
  76                      -> let
  77                           n1n2_m = (,) <$> lookup n1 m <*> lookup n2 m
  78                           n1n2_d = Just [((n1,n2),d)]
  79                         in (,) <$> n1n2_m <*> n1n2_d
  80                     )
  81              . toList
  82
  83 -- | TODO : sortOn Confluence
  84
  85 filterComs :: (Ord n1, Eq n2)
  86            => p
  87            -> Map (n2, n2) [(a3, n1)]
  88            -> Map (n2, n2) [(a3, n1)]
  89 filterComs _b m = DM.filter (\n -> length n > 0) $ mapWithKey filter' m
  90   where
  91     filter' (c1,c2) a
  92       | c1 == c2  = a
  93       -- TODO use n here
  94       | otherwise = take 1 $ sortOn (Down . snd) a
  95            where
  96             _n :: Int
  97             _n = round $ 100 * a' / t
  98             a'= fromIntegral $ length a
  99             t :: Double
 100             t = fromIntegral $ length $ concat $ elems m