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