Data.Graph.Connectivity

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

Documentation

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

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

Opposite of areConnected

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

Tell if a vertex is isolated

A vertex is isolated if it has no incident edges, that is, it has a degree of zero

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

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

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

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

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

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)

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

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

Tell if a DGraph is strongly connected

A directed graph is strongly connected if it contains a directed path on every pair of vertices