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
  33 ------------------------------------------------------------------
  34 -- | Main Types
  35 type Graph_Undirected = IG.Graph 'U () ()
  36 type Graph_Directed   = IG.Graph 'D () ()
  37
  38 type Node  = IG.Node
  39 type Graph = IG.Graph
  40
  41 ------------------------------------------------------------------
  42 -- | Main Graph management Functions
  43 neighbors :: IG.Graph d v e -> IG.Node -> [IG.Node]
  44 neighbors = IG.neighbors
  45
  46 edges :: IG.Graph d v e -> [Edge]
  47 edges = IG.edges
  48
  49 nodes :: IG.Graph d v e -> [IG.Node]
  50 nodes = IG.nodes
  51
  52 ------------------------------------------------------------------
  53 -- | Partitions
  54 maximalCliques :: IG.Graph d v e -> [[Int]]
  55 maximalCliques g = IG.maximalCliques g (min',max')
  56   where
  57     min' = 0
  58     max' = 0
  59
  60 ------------------------------------------------------------------
  61 type Seed = Int
  62
  63 spinglass :: Seed -> Map (Int, Int) Double -> IO [ClusterNode]
  64 spinglass s g = toClusterNode
  65              <$> map catMaybes
  66              <$> map (map (\n -> Map.lookup n fromI))
  67              <$> List.concat
  68              <$> mapM (partitions_spinglass' s) g'
  69   where
  70     -- Not connected components of the graph make crash spinglass
  71     g' = IG.decompose $ mkGraphUfromEdges
  72                       $ Map.keys
  73                       $ toIndex toI g
  74
  75     (toI, fromI) = createIndices g
  76
  77
  78 -- | Tools to analyze graphs
  79 partitions_spinglass' :: (Serialize v, Serialize e)
  80                          => Seed -> IG.Graph 'U v e -> IO [[Int]]
  81 partitions_spinglass' s g = do
  82   gen <- IG.withSeed s pure
  83   res <- IG.findCommunity g Nothing Nothing IG.spinglass gen
  84   -- res <- IG.findCommunity g Nothing Nothing IG.leiden gen
  85   -- res <- IG.findCommunity g Nothing Nothing IG.infomap  gen
  86   saveAsFileDebug "/tmp/res" res
  87   pure res
  88
  89
  90 toClusterNode :: [[Int]] -> [ClusterNode]
  91 toClusterNode ns = List.concat
  92                  $ map (\(cId, ns') -> map (\n -> ClusterNode n cId) ns')
  93                  $ List.zip [1..] ns
  94
  95 ------------------------------------------------------------------
  96 mkGraph :: (SingI d, Ord v,
  97              Serialize v, Serialize e) =>
  98      [v] -> [LEdge e] -> IG.Graph d v e
  99 mkGraph = IG.mkGraph
 100
 101 ------------------------------------------------------------------
 102 mkGraphUfromEdges :: [(Int, Int)] -> Graph_Undirected
 103 mkGraphUfromEdges es = mkGraph (List.replicate n ()) $ zip es $ repeat ()
 104   where
 105     (a,b) = List.unzip es
 106     n = List.length (List.nub $ a <> b)
 107
 108 {-
 109 mkGraphDfromEdges :: [(Int, Int)] -> Graph_Directed
 110 mkGraphDfromEdges = undefined
 111 -}