{-|
Module      : Data.Graph.AdjacencyList.Metrics
Description : Graph distance and density metrics
Copyright   : Thodoris Papakonstantinou, 2017-2026
License     : LGPL-3
Maintainer  : dev@tpapak.com
Stability   : experimental
Portability : POSIX

Graph metrics computed from a 'Distances' matrix (see "Data.Graph.AdjacencyList.WFI"):
<https://en.wikipedia.org/wiki/Distance_(graph_theory) eccentricity>,
radius, diameter, and density.
 -}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}


module Data.Graph.AdjacencyList.Metrics
  ( graphEccentricity
  , graphRadius
  , graphDiameter
  , graphDensity
  ) where

import Data.List
import Data.Maybe
import qualified Data.IntMap   as IM

import Data.Graph.AdjacencyList
import Data.Graph.AdjacencyList.WFI

-- | Eccentricity of a vertex: the maximum shortest-path distance from @v@
-- to any other reachable vertex.  Returns 'Nothing' if @v@ is not in the
-- distance matrix.
graphEccentricity :: Vertex -> Distances -> Maybe Weight
graphEccentricity :: Vertex -> Distances -> Maybe Rational
graphEccentricity Vertex
v (Distances IMArray
dis) =
  let vdis :: Maybe (IntMap Rational)
vdis = Vertex -> IMArray -> Maybe (IntMap Rational)
forall a. Vertex -> IntMap a -> Maybe a
IM.lookup Vertex
v IMArray
dis
   in IntMap Rational -> Rational
forall a. Ord a => IntMap a -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum (IntMap Rational -> Rational)
-> Maybe (IntMap Rational) -> Maybe Rational
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (IntMap Rational)
vdis

-- | Radius of the graph: the minimum eccentricity over all vertices
-- (excluding zero and absent eccentricities).
graphRadius :: Distances -> Maybe Weight
graphRadius :: Distances -> Maybe Rational
graphRadius Distances
dis =
  let (Distances IMArray
dism) = Distances
dis
      vs :: [Vertex]
vs = IMArray -> [Vertex]
forall a. IntMap a -> [Vertex]
IM.keys IMArray
dism
      filtdis :: [Maybe Rational]
filtdis = (Maybe Rational -> Bool) -> [Maybe Rational] -> [Maybe Rational]
forall a. (a -> Bool) -> [a] -> [a]
filter (\Maybe Rational
d -> Maybe Rational
d Maybe Rational -> Maybe Rational -> Bool
forall a. Eq a => a -> a -> Bool
/= Rational -> Maybe Rational
forall a. a -> Maybe a
Just Rational
0 Bool -> Bool -> Bool
&& Maybe Rational
d Maybe Rational -> Maybe Rational -> Bool
forall a. Eq a => a -> a -> Bool
/= Maybe Rational
forall a. Maybe a
Nothing) 
         ([Maybe Rational] -> [Maybe Rational])
-> [Maybe Rational] -> [Maybe Rational]
forall a b. (a -> b) -> a -> b
$ (Vertex -> Maybe Rational) -> [Vertex] -> [Maybe Rational]
forall a b. (a -> b) -> [a] -> [b]
map (\Vertex
v -> Vertex -> Distances -> Maybe Rational
graphEccentricity Vertex
v Distances
dis) [Vertex]
vs
   in if [Maybe Rational] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Maybe Rational]
filtdis
         then Maybe Rational
forall a. Maybe a
Nothing
         else [Maybe Rational] -> Maybe Rational
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Maybe Rational]
filtdis

-- | Diameter of the graph: the maximum eccentricity over all vertices.
graphDiameter :: Distances -> Maybe Weight
graphDiameter :: Distances -> Maybe Rational
graphDiameter Distances
dis =
  let (Distances IMArray
dism) = Distances
dis
      vs :: [Vertex]
vs = IMArray -> [Vertex]
forall a. IntMap a -> [Vertex]
IM.keys IMArray
dism
      filtdis :: [Maybe Rational]
filtdis = (Maybe Rational -> Bool) -> [Maybe Rational] -> [Maybe Rational]
forall a. (a -> Bool) -> [a] -> [a]
filter (\Maybe Rational
d -> Maybe Rational
d Maybe Rational -> Maybe Rational -> Bool
forall a. Eq a => a -> a -> Bool
/= Rational -> Maybe Rational
forall a. a -> Maybe a
Just Rational
0 Bool -> Bool -> Bool
&& Maybe Rational
d Maybe Rational -> Maybe Rational -> Bool
forall a. Eq a => a -> a -> Bool
/= Maybe Rational
forall a. Maybe a
Nothing) 
        ([Maybe Rational] -> [Maybe Rational])
-> [Maybe Rational] -> [Maybe Rational]
forall a b. (a -> b) -> a -> b
$ (Vertex -> Maybe Rational) -> [Vertex] -> [Maybe Rational]
forall a b. (a -> b) -> [a] -> [b]
map (\Vertex
v -> Vertex -> Distances -> Maybe Rational
graphEccentricity Vertex
v Distances
dis) [Vertex]
vs
   in if [Maybe Rational] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Maybe Rational]
filtdis
         then Maybe Rational
forall a. Maybe a
Nothing
         else [Maybe Rational] -> Maybe Rational
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Maybe Rational]
filtdis

-- | Since the representation of undirected graphs dublicated edges no need for
-- undirected version of density
graphDensity :: Graph -> Rational
graphDensity :: Graph -> Rational
graphDensity Graph
g =
  let ne :: Rational
ne = Vertex -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vertex -> Rational) -> Vertex -> Rational
forall a b. (a -> b) -> a -> b
$ [Edge] -> Vertex
forall a. [a] -> Vertex
forall (t :: * -> *) a. Foldable t => t a -> Vertex
length ([Edge] -> Vertex) -> [Edge] -> Vertex
forall a b. (a -> b) -> a -> b
$ Graph -> [Edge]
edges Graph
g
      nv :: Rational
nv = Vertex -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vertex -> Rational) -> Vertex -> Rational
forall a b. (a -> b) -> a -> b
$ [Vertex] -> Vertex
forall a. [a] -> Vertex
forall (t :: * -> *) a. Foldable t => t a -> Vertex
length ([Vertex] -> Vertex) -> [Vertex] -> Vertex
forall a b. (a -> b) -> a -> b
$ Graph -> [Vertex]
vertices Graph
g
   in Rational
ne Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/ (Rational
nv Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
* (Rational
nv Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
- Rational
1))