hgraph-1.2.0.0: src/HGraph/Undirected/Expanders.hs

module HGraph.Undirected.Expanders
       ( edgeExpansion
       , vertexExpansion
       )
where

import HGraph.Undirected
import qualified Data.Map as M

edgeExpansion :: (UndirectedGraph g, Adjacency g) => g a -> (Double, [a])
-- | Edge expansion of a graph, together with a set of verticies certifying that the expansion is not greater.
edgeExpansion g = (expansion, cert)
  where
    (expansion, cert') = edgeExpansion' (numVertices gi `div` 2) (vertices gi) []
    cert = map (idT M.!) cert'
    (gi, itol) = linearizeVertices g
    idT = M.fromList itol
    edgeExpansion' budget [] [] = (fromIntegral $ numVertices gi, [])
    edgeExpansion' budget [] as = (fromIntegral e / (fromIntegral $ length as), as)
      where
        e = sum [degree gi v | v <- as]
    edgeExpansion' 0 _ as = edgeExpansion' 0 [] as
    edgeExpansion' budget (v:vs) as = (e, c)
      where
        (e0,c0) = edgeExpansion' (budget - 1) vs (v : as)
        (e1,c1) = edgeExpansion' budget vs as
        (e,c) = if e0 < e1 then (e0,c0) else (e1,c1)

vertexExpansion :: (Adjacency g) => g a -> (Double, [a])
-- | Vertex expansion of a graph, together with a set of verticies certifying that the expansion is not greater.
vertexExpansion g = (0,[])