Connectivity.hs

-- | For Connectivity analisis purposes a 'DGraph' can be converted into a
-- | 'UGraph' using 'toUndirected'

{-# LANGUAGE ScopedTypeVariables #-}

module Data.Graph.Connectivity where

import Data.List (foldl')

import           Data.Hashable
import qualified Data.Set      as S

import Data.Graph.DGraph
import Data.Graph.Types
import Data.Graph.UGraph

-- | Tell if two vertices of a graph are connected
-- | Two vertices are @connected@ if it exists a path between them
-- | The order of the vertices is relevant when the graph is directed
areConnected :: forall g v e . (Graph g, Hashable v, Eq v, Ord v)
 => g v e
 -> v
 -> v
 -> Bool
areConnected g fromV toV
    | fromV == toV = True
    | otherwise = search (directlyReachableVertices g fromV) S.empty toV
    where
        search :: [v] -> S.Set v -> v -> Bool
        search [] _ _ = False
        search (v:vs) banned v'
            | v `S.member` banned = search vs banned v'
            | v == v' = True
            | otherwise =
                search (directlyReachableVertices g v) banned' v'
                || search vs banned' v'
            where banned' = v `S.insert` banned

-- | Tell if two vertices of a 'UGraph' are disconnected
-- | Two vertices are @disconnected@ if it doesn't exist a path between them
areDisconnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> v -> Bool
areDisconnected g fromV toV = not $ areConnected g fromV toV

-- | Tell if a vertex is isolated
-- | A vertex is @isolated@ if it has no incidet edges, that is, it has a degree
-- | of zero
isIsolated :: (Graph g, Hashable v, Eq v) => g v e -> v -> Bool
isIsolated g v = vertexDegree g v == 0

-- | Tell if a graph is connected
-- | An Undirected Graph is @connected@ when there is a path between every pair
-- | of vertices
isConnected :: (Hashable v, Eq v) => UGraph v e -> Bool
isConnected g = foldl' (\b v -> b && (not $ isIsolated g v)) True $ vertices g

-- | Tell if a 'DGraph' is weakly connected
-- | A Directed Graph is @weakly connected@ if the underlying undirected graph
-- | is @connected@
isWeaklyConnected :: (Hashable v, Eq v) => DGraph v e -> Bool
isWeaklyConnected = isConnected . toUndirected

-- | Tell if a 'DGraph' is strongly connected
-- | A Directed Graph is @strongly connected@ if it contains a directed path
-- | on every pair of vertices
isStronglyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool
isStronglyConnected g = go vs True
    where
        vs = vertices g
        go _ False = False
        go [] bool = bool
        go (v':vs') bool =
            go vs' $ foldl' (\b v -> b && (areConnected g v v')) bool vs

-- TODO
-- * connected component
-- * strong components
-- * vertex cut
-- * vertex connectivity
--     * biconnectivity
--     * triconnectivity
--     * separable
-- * bridge
-- * edge-connectivity
-- * maximally connected
-- * maximally edge-connected
-- * super-connectivity
-- * hyper-connectivity
-- * Menger's theorem

-- Robin's Theorem: a graph is orientable if it is connected and has no bridges