src/Gargantext/Core/Viz/Graph/Tools/IGraph.hs

   1 {-|
   2 Module      : Gargantext.Core.Viz.Graph.Tools.IGraph
   3 Description : Tools to build Graph
   4 Copyright   : (c) CNRS, 2017-Present
   5 License     : AGPL + CECILL v3
   6 Maintainer  : team@gargantext.org
   7 Stability   : experimental
   8 Portability : POSIX
   9
  10 Reference:
  11 * Gábor Csárdi, Tamás Nepusz: The igraph software package for complex network research. InterJournal Complex Systems, 1695, 2006.
  12
  13 -}
  14
  15 module Gargantext.Core.Viz.Graph.Tools.IGraph
  16   where
  17
  18 import Data.Serialize
  19 import Data.Singletons (SingI)
  20 import Gargantext.Core.Viz.Graph.Index
  21 import Graph.Types (ClusterNode(..))
  22 import IGraph hiding (mkGraph, neighbors, edges, nodes, Node, Graph)
  23 import Protolude
  24 import Gargantext.Prelude (saveAsFileDebug)
  25 import qualified Data.List                   as List
  26 import qualified Data.Map.Strict             as Map
  27 import qualified IGraph                      as IG
  28 import qualified IGraph.Algorithms.Clique    as IG
  29 import qualified IGraph.Algorithms.Community as IG
  30 import qualified IGraph.Algorithms.Structure as IG
  31 import qualified IGraph.Random               as IG
  32 import qualified Data.Set                    as Set
  33
  34 ------------------------------------------------------------------
  35 -- | Main Types
  36 type Graph_Undirected = IG.Graph 'U () ()
  37 type Graph_Directed   = IG.Graph 'D () ()
  38
  39 type Node  = IG.Node
  40 type Graph = IG.Graph
  41
  42 ------------------------------------------------------------------
  43 -- | Main Graph management Functions
  44 neighbors :: IG.Graph d v e -> IG.Node -> [IG.Node]
  45 neighbors = IG.neighbors
  46
  47 edges :: IG.Graph d v e -> [Edge]
  48 edges = IG.edges
  49
  50 nodes :: IG.Graph d v e -> [IG.Node]
  51 nodes = IG.nodes
  52
  53 ------------------------------------------------------------------
  54 -- | Partitions
  55 maximalCliques :: IG.Graph d v e -> [[Int]]
  56 maximalCliques g = IG.maximalCliques g (min',max')
  57   where
  58     min' = 0
  59     max' = 0
  60
  61 ------------------------------------------------------------------
  62 type Seed = Int
  63
  64 spinglass :: Seed -> Map (Int, Int) Double -> IO [ClusterNode]
  65 spinglass s g = toClusterNode
  66              <$> map catMaybes
  67              <$> map (map (\n -> Map.lookup n fromI))
  68              <$> List.concat
  69              <$> mapM (partitions_spinglass' s) g'
  70   where
  71     -- Not connected components of the graph make crash spinglass
  72     g' = IG.decompose $ mkGraphUfromEdges
  73                       $ Map.keys
  74                       $ toIndex toI g
  75
  76     (toI, fromI) = createIndices g
  77
  78 spinglass' :: Seed -> Map (Int, Int) Double -> IO [Set Int]
  79 spinglass' s g = map Set.fromList
  80              <$> map catMaybes
  81              <$> map (map (\n -> Map.lookup n fromI))
  82              <$> List.concat
  83              <$> mapM (partitions_spinglass' s) g'
  84   where
  85     -- Not connected components of the graph make crash spinglass
  86     g' = IG.decompose $ mkGraphUfromEdges
  87                       $ Map.keys
  88                       $ toIndex toI g
  89
  90     (toI, fromI) = createIndices g
  91
  92
  93
  94
  95
  96 -- | Tools to analyze graphs
  97 partitions_spinglass' :: (Serialize v, Serialize e)
  98                          => Seed -> IG.Graph 'U v e -> IO [[Int]]
  99 partitions_spinglass' s g = do
 100   gen <- IG.withSeed s pure
 101   res <- IG.findCommunity g Nothing Nothing IG.spinglass gen
 102   -- res <- IG.findCommunity g Nothing Nothing IG.leiden gen
 103   -- res <- IG.findCommunity g Nothing Nothing IG.infomap  gen
 104   saveAsFileDebug "/tmp/res" res
 105   pure res
 106
 107
 108 toClusterNode :: [[Int]] -> [ClusterNode]
 109 toClusterNode ns = List.concat
 110                  $ map (\(cId, ns') -> map (\n -> ClusterNode n cId) ns')
 111                  $ List.zip [1..] ns
 112
 113 ------------------------------------------------------------------
 114 mkGraph :: (SingI d, Ord v,
 115              Serialize v, Serialize e) =>
 116      [v] -> [LEdge e] -> IG.Graph d v e
 117 mkGraph = IG.mkGraph
 118
 119 ------------------------------------------------------------------
 120 mkGraphUfromEdges :: [(Int, Int)] -> Graph_Undirected
 121 mkGraphUfromEdges es = mkGraph (List.replicate n ()) $ zip es $ repeat ()
 122   where
 123     (a,b) = List.unzip es
 124     n = List.length (List.nub $ a <> b)
 125
 126 {-
 127 mkGraphDfromEdges :: [(Int, Int)] -> Graph_Directed
 128 mkGraphDfromEdges = undefined
 129 -}