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