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 IGraph hiding (mkGraph, neighbors, edges, nodes, Node, Graph)
  21 import Protolude
  22 import Gargantext.Core.Viz.Graph.Index
  23 import qualified Data.List                   as List
  24 import qualified IGraph                      as IG
  25 import qualified IGraph.Algorithms.Clique    as IG
  26 import qualified IGraph.Algorithms.Community as IG
  27 import qualified IGraph.Algorithms.Structure as IG
  28 import qualified IGraph.Random               as IG
  29 import qualified Data.Map                    as Map
  30
  31 ------------------------------------------------------------------
  32 -- | Main Types
  33 type Graph_Undirected = IG.Graph 'U () ()
  34 type Graph_Directed   = IG.Graph 'D () ()
  35
  36 type Node  = IG.Node
  37 type Graph = IG.Graph
  38
  39 ------------------------------------------------------------------
  40 -- | Main Graph management Functions
  41 neighbors :: IG.Graph d v e -> IG.Node -> [IG.Node]
  42 neighbors = IG.neighbors
  43
  44 edges :: IG.Graph d v e -> [Edge]
  45 edges = IG.edges
  46
  47 nodes :: IG.Graph d v e -> [IG.Node]
  48 nodes = IG.nodes
  49
  50 ------------------------------------------------------------------
  51 -- | Partitions
  52 maximalCliques :: IG.Graph d v e -> [[Int]]
  53 maximalCliques g = IG.maximalCliques g (min',max')
  54   where
  55     min' = 0
  56     max' = 0
  57
  58 ------------------------------------------------------------------
  59 type Seed = Int
  60
  61 spinglass :: Seed -> Map (Int, Int) Double -> IO [ClusterNode]
  62 spinglass s g = toClusterNode
  63              <$> map catMaybes
  64              <$> map (map (\n -> Map.lookup n fromI))
  65              <$> partitions_spinglass' s g'''
  66   where
  67     g'   = toIndex toI g
  68     g''  = mkGraphUfromEdges (Map.keys g')
  69     g''' = case IG.isConnected g'' of
  70       True -> g''
  71       False -> panic "[G.C.V.G.T.Igraph: not connected graph]"
  72
  73     (toI, fromI) = createIndices g
  74
  75 -- | Tools to analyze graphs
  76 partitions_spinglass' :: (Serialize v, Serialize e)
  77                          => Seed -> IG.Graph 'U v e -> IO [[Int]]
  78 partitions_spinglass' s g = do
  79   gen <- IG.withSeed s pure
  80   IG.findCommunity g Nothing Nothing IG.spinglass gen
  81
  82
  83 data ClusterNode = ClusterNode { cl_node_id :: Int
  84                                , cl_community_id :: Int
  85                                }
  86
  87 toClusterNode :: [[Int]] -> [ClusterNode]
  88 toClusterNode ns = List.concat
  89                  $ map (\(cId, ns') -> map (\n -> ClusterNode n cId) ns')
  90                  $ List.zip [1..] ns
  91
  92 ------------------------------------------------------------------
  93 mkGraph :: (SingI d, Ord v,
  94              Serialize v, Serialize e) =>
  95      [v] -> [LEdge e] -> IG.Graph d v e
  96 mkGraph = IG.mkGraph
  97
  98 ------------------------------------------------------------------
  99 mkGraphUfromEdges :: [(Int, Int)] -> Graph_Undirected
 100 mkGraphUfromEdges es = mkGraph (List.replicate n ()) $ zip es $ repeat ()
 101   where
 102     (a,b) = List.unzip es
 103     n = List.length (List.nub $ a <> b)
 104
 105 {-
 106 mkGraphDfromEdges :: [(Int, Int)] -> Graph_Directed
 107 mkGraphDfromEdges = undefined
 108 -}