This module implements a data type of directed graphs
where there may be multiple edges between a pair of vertices.
There are a variety of ways to think of this:
As two finite sets `V`

, `E`

with two maps source, target : `E -> V`

.
As a finite Set `V`

, a finite set of labels `L`

, and a ternary relation as a subset of `(V,L,V)`

.

- data LabelledGraph n e
- type Weight = Double
- empty :: (Ord n, Ord e) => LabelledGraph n e
- addNode :: Ord n => n -> LabelledGraph n e -> LabelledGraph n e
- addEdge :: (Ord n, Ord e) => e -> (n, n) -> Weight -> LabelledGraph n e -> LabelledGraph n e
- adjustEdgeWeight :: (Ord n, Ord e) => e -> (Weight -> Weight) -> LabelledGraph n e -> LabelledGraph n e
- deleteNode :: (Ord e, Ord n) => n -> LabelledGraph n e -> LabelledGraph n e
- deleteEdge :: (Ord n, Ord e) => e -> LabelledGraph n e -> LabelledGraph n e
- nodes :: Ord n => LabelledGraph n e -> [n]
- numberOfNodes :: Ord n => LabelledGraph n e -> Int
- edgesOutOf :: (Ord e, Ord n) => n -> LabelledGraph n e -> [(e, n)]
- edgesFromTo :: (Ord e, Ord n) => n -> n -> LabelledGraph n e -> [(e, Weight)]
- edges :: LabelledGraph n e -> [(e, Weight)]
- data LTree a b = LNode a [(b, LTree a b)]
- pathTree :: (Ord n, Ord e) => LabelledGraph n e -> n -> n -> Maybe (LTree n (e, Weight))
- mapLTree :: (a -> c) -> (b -> d) -> LTree a b -> LTree c d
- drawTree :: LTree String String -> String

# Documentation

data LabelledGraph n e Source

(Show n, Show e) => Show (LabelledGraph n e) |

# Construction

empty :: (Ord n, Ord e) => LabelledGraph n eSource

addNode :: Ord n => n -> LabelledGraph n e -> LabelledGraph n eSource

addEdge :: (Ord n, Ord e) => e -> (n, n) -> Weight -> LabelledGraph n e -> LabelledGraph n eSource

adjustEdgeWeight :: (Ord n, Ord e) => e -> (Weight -> Weight) -> LabelledGraph n e -> LabelledGraph n eSource

deleteNode :: (Ord e, Ord n) => n -> LabelledGraph n e -> LabelledGraph n eSource

deleteEdge :: (Ord n, Ord e) => e -> LabelledGraph n e -> LabelledGraph n eSource

# Query

nodes :: Ord n => LabelledGraph n e -> [n]Source

numberOfNodes :: Ord n => LabelledGraph n e -> IntSource

edgesOutOf :: (Ord e, Ord n) => n -> LabelledGraph n e -> [(e, n)]Source

edgesFromTo :: (Ord e, Ord n) => n -> n -> LabelledGraph n e -> [(e, Weight)]Source

edges :: LabelledGraph n e -> [(e, Weight)]Source

# Path tree

pathTree :: (Ord n, Ord e) => LabelledGraph n e -> n -> n -> Maybe (LTree n (e, Weight))Source

Computes the path tree from one node to another node of the graph. Each node of the tree is a path in the graph from the source to some node in the graph. The parent of a node is the node representing the path with one less edge than the node.