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 Gargantext.Core.Viz.Graph.Index
  21 import Graph.Types (ClusterNode(..))
  22 import IGraph hiding (mkGraph, neighbors, edges, nodes, Node, Graph)
  23 import Protolude
  24 import qualified Data.List                   as List
  25 import qualified Data.Map                    as Map
  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
  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              <$> List.concat
  67              <$> mapM (partitions_spinglass' s) g'
  68   where
  69     -- Not connected components of the graph make crash spinglass
  70     g' = IG.decompose $ mkGraphUfromEdges
  71                       $ Map.keys
  72                       $ toIndex toI g
  73
  74     (toI, fromI) = createIndices g
  75
  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 toClusterNode :: [[Int]] -> [ClusterNode]
  86 toClusterNode ns = List.concat
  87                  $ map (\(cId, ns') -> map (\n -> ClusterNode n cId) ns')
  88                  $ List.zip [1..] ns
  89
  90 ------------------------------------------------------------------
  91 mkGraph :: (SingI d, Ord v,
  92              Serialize v, Serialize e) =>
  93      [v] -> [LEdge e] -> IG.Graph d v e
  94 mkGraph = IG.mkGraph
  95
  96 ------------------------------------------------------------------
  97 mkGraphUfromEdges :: [(Int, Int)] -> Graph_Undirected
  98 mkGraphUfromEdges es = mkGraph (List.replicate n ()) $ zip es $ repeat ()
  99   where
 100     (a,b) = List.unzip es
 101     n = List.length (List.nub $ a <> b)
 102
 103 {-
 104 mkGraphDfromEdges :: [(Int, Int)] -> Graph_Directed
 105 mkGraphDfromEdges = undefined
 106 -}