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.