Connectivity.hs

-- | For Connectivity analysis 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 (fromV : reachableAdjacentVertices 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 (v : reachableAdjacentVertices g v) banned' v'
                || search vs banned' v'
            where banned' = v `S.insert` banned

-- | Opposite of 'areConnected'
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 incident 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
-- FIXME: Use a O(n) algorithm
isConnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> Bool
isConnected 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

-- | Tell if a graph is bridgeless
--
-- A graph is @bridgeless@ if it has no edges that, when removed, split the
-- graph in two isolated components
-- FIXME: Use a O(n) algorithm
isBridgeless :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool
isBridgeless g =
    foldl' (\b vs -> b && isConnected (removeEdgePair vs g)) True (edgePairs g)

-- | Tell if a 'UGraph' is orientable
--
-- An undirected graph is @orientable@ if it can be converted into a directed
-- graph that is @strongly connected@ (See 'isStronglyConnected')
isOrientable :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool
isOrientable g = isConnected g && isBridgeless 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, Ord 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 = isConnected

-- 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