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 -> case head (IG.decompose g'') of
  72         Nothing    -> panic "[G.C.V.G.T.Igraph: not connected graph]"
  73         Just g'''' -> g''''
  74
  75     (toI, fromI) = createIndices g
  76
  77 -- | Tools to analyze graphs
  78 partitions_spinglass' :: (Serialize v, Serialize e)
  79                          => Seed -> IG.Graph 'U v e -> IO [[Int]]
  80 partitions_spinglass' s g = do
  81   gen <- IG.withSeed s pure
  82   IG.findCommunity g Nothing Nothing IG.spinglass gen
  83
  84
  85 data ClusterNode = ClusterNode { cl_node_id :: Int
  86                                , cl_community_id :: Int
  87                                }
  88
  89 toClusterNode :: [[Int]] -> [ClusterNode]
  90 toClusterNode ns = List.concat
  91                  $ map (\(cId, ns') -> map (\n -> ClusterNode n cId) ns')
  92                  $ List.zip [1..] ns
  93
  94 ------------------------------------------------------------------
  95 mkGraph :: (SingI d, Ord v,
  96              Serialize v, Serialize e) =>
  97      [v] -> [LEdge e] -> IG.Graph d v e
  98 mkGraph = IG.mkGraph
  99
 100 ------------------------------------------------------------------
 101 mkGraphUfromEdges :: [(Int, Int)] -> Graph_Undirected
 102 mkGraphUfromEdges es = mkGraph (List.replicate n ()) $ zip es $ repeat ()
 103   where
 104     (a,b) = List.unzip es
 105     n = List.length (List.nub $ a <> b)
 106
 107 {-
 108 mkGraphDfromEdges :: [(Int, Int)] -> Graph_Directed
 109 mkGraphDfromEdges = undefined
 110 -}