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 Graph.Types
  24 import Gargantext.Core.Viz.Graph.Types
  25 import qualified Data.List                   as List
  26 import qualified IGraph                      as IG
  27 import qualified IGraph.Algorithms.Clique    as IG
  28 import qualified IGraph.Algorithms.Community as IG
  29 import qualified IGraph.Algorithms.Structure as IG
  30 import qualified IGraph.Random               as IG
  31 import qualified Data.Map                    as Map
  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              <$> partitions_spinglass' s g'''
  68   where
  69     g'   = toIndex toI g
  70     g''  = mkGraphUfromEdges (Map.keys g')
  71     g''' = case IG.isConnected g'' of
  72       True -> g''
  73       False -> case head (IG.decompose g'') of
  74         Nothing    -> panic "[G.C.V.G.T.Igraph: not connected graph]"
  75         Just g'''' -> g''''
  76
  77     (toI, fromI) = createIndices g
  78
  79 -- | Tools to analyze graphs
  80 partitions_spinglass' :: (Serialize v, Serialize e)
  81                          => Seed -> IG.Graph 'U v e -> IO [[Int]]
  82 partitions_spinglass' s g = do
  83   gen <- IG.withSeed s pure
  84   IG.findCommunity g Nothing Nothing IG.spinglass gen
  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 -}