1 {-| Module : Gargantext.Core.Viz.Graph.MaxClique
2 Description : MaxCliques function
3 Copyright : (c) CNRS, 2017-Present
4 License : AGPL + CECILL v3
5 Maintainer : team@gargantext.org
6 Stability : experimental
9 - Result of Pyremiel 2019
10 - First written by Bruno Gaume in Python (see below for details)
11 - Then written by Alexandre Delanoë in Haskell (see below for details)
14 def fast_maximal_cliques(g):
16 def rec_maximal_cliques(g, subv):
18 if subv == []: # stop condition
21 for i in range(len(subv)):
22 newsubv = [j for j in subv[i+1:len(subv)]
23 if (j in g.neighbors(subv[i]))]
24 mci = rec_maximal_cliques(g, newsubv)
31 clustset = [set(x) for x in clust]
33 for i in range(len(clustset)):
35 for j in range(len(clustset)):
36 if clustset[i].issubset(clustset[j]) and (not (len(clustset[i]) == len(clustset[j])) ):
38 if ok and (not (clustset[i] in new_clust)):
39 new_clust.append(clustset[i])
40 return [list(x) for x in new_clust]
42 # to optimize : rank the vertices on the degrees
43 subv = [(v.index, v.degree()) for v in g.vs()]
44 subv.sort(key = lambda z:z[1])
45 subv = [x for (x, y) in subv]
46 return purge(rec_maximal_cliques(g, subv))
52 module Gargantext.Core.Viz.Graph.MaxClique
55 import Data.Maybe (catMaybes)
56 import Gargantext.Prelude
58 import qualified Data.Map as Map
59 import Data.List (sortOn, nub, concat)
61 import Data.Set (fromList, toList, isSubsetOf)
62 import Data.Graph.Inductive hiding (Graph, neighbors, subgraph, (&))
63 import Gargantext.Core.Viz.Graph.FGL (Graph_Undirected, degree, neighbors, mkGraphUfromEdges)
64 import Gargantext.Core.Viz.Graph.Tools (cooc2graph', Threshold)
65 import Gargantext.Core.Viz.Graph.Distances (Distance)
66 import Gargantext.Core.Viz.Graph.Index (createIndices, toIndex)
67 type Graph = Graph_Undirected
72 -- TODO chose distance order
73 getMaxCliques :: Ord a => Distance -> Threshold -> Map (a, a) Int -> [[a]]
74 getMaxCliques d t m = map fromIndices $ getMaxCliques' t m'
77 (to,from) = createIndices m
78 fromIndices = catMaybes . map (\n -> Map.lookup n from)
80 getMaxCliques' :: Threshold -> Map (Int, Int) Int -> [[Int]]
81 getMaxCliques' t' n = maxCliques graph
83 graph = mkGraphUfromEdges (Map.keys n')
84 n' = cooc2graph' d t' n
86 maxCliques :: Graph -> [[Node]]
87 maxCliques g = map (\n -> subMaxCliques g (n:ns)) ns & concat & takeMax
90 ns = sortOn (degree g) $ nodes g
92 subMaxCliques :: Graph -> [Node] -> [[Node]]
93 subMaxCliques _ [] = [[]]
94 subMaxCliques g' (x:xs) = add x $ subMaxCliques g' ns'
96 ns' = [n | n <- xs, elem n $ neighborsOut g' x]
98 add :: Node -> [[Node]] -> [[Node]]
100 add n (m:ms) = [n:m] <> add n ms
101 -- | Note, it is same as :
102 -- add n ns = map (\m -> n : m) ns
103 -- -- (but using pattern matching and recursivity)
104 -- -- (map is redefined in fact)
106 -- | To be sure self is not in neighbors of self
107 -- (out to exclude the self)
108 neighborsOut :: Graph -> Node -> [Node]
109 neighborsOut g'' n = filter (/= n) $ neighbors g'' n
112 takeMax :: [[Node]] -> [[Node]]
119 purge :: [Set Node] -> [Set Node]
121 purge (x:xs) = x' <> purge xs
123 x' = if all (== False) (map (isSubsetOf x) xs)
128 ------------------------------------------------------------------------
130 -- test_graph = mkGraphUfromEdges [(1,1), (2,2), (3,3)]
131 test_graph = mkGraphUfromEdges [(1,2), (3,3)]
134 test_graph' = mkGraphUfromEdges [(1,2), (3,3), (3,2)]
136 test_graph'' :: Graph
137 test_graph'' = mkGraphUfromEdges [(1,2), (2,3), (1,3)]
139 test_graph''' :: Graph
140 test_graph''' = mkGraphUfromEdges [ (4,1)