graphite-0.4.1.0: Graphs and networks library

Safe HaskellSafe
LanguageHaskell2010

Data.Graph.Connectivity

Contents

Description

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

Synopsis

Documentation

areConnected :: forall g v e. (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> v -> Bool Source #

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

areDisconnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> v -> Bool Source #

Tell if two vertices of a UGraph are disconnected | Two vertices are disconnected if it doesn't exist a path between them

isIsolated :: (Graph g, Hashable v, Eq v) => g v e -> v -> Bool Source #

Tell if a vertex is isolated | A vertex is isolated if it has no incidet edges, that is, it has a degree | of zero

isConnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> Bool Source #

Tell if a graph is connected | An Undirected Graph is connected when there is a path between every pair | of vertices

isBridgeless :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool Source #

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

isOrientable :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool Source #

Tell if a UGraph is orietable | An undirected graph is orietable if it can be converted into a directed | graph that is strongly connected (See isStronglyConnected)

isWeaklyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool Source #

Tell if a DGraph is weakly connected | A Directed Graph is weakly connected if the underlying undirected graph | is connected

isStronglyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool Source #

Tell if a DGraph is strongly connected | A Directed Graph is strongly connected if it contains a directed path | on every pair of vertices

connected component

strong components

vertex cut

vertex connectivity

bridge

edge-connectivity

maximally connected

maximally edge-connected

super-connectivity

hyper-connectivity

Menger's theorem