Safe Haskell	Safe-Inferred
Language	Haskell2010

LabelledGraph

Description

Edge-labeled/weighted graphs

There are useful definitions and algorithms in Data.Tree and Data.Graph but sadly these only deal with unlabeled graphs. Most definitions here mirror those in Data.Graph.

Synopsis

type LEdge b = (Vertex, (b, Vertex))
type LGraph b = Array Vertex [(b, Vertex)]
data LTree b a = LNode {
- rootLabelL :: a
- subForestL :: [(b, LTree b a)]
}
buildLG :: Bounds -> [LEdge b] -> LGraph b
dfsLTree :: LGraph b -> Vertex -> LTree b Vertex
lTreeToTree :: LTree b a -> Tree a

Documentation

type LEdge b = (Vertex, (b, Vertex)) Source #

type LGraph b = Array Vertex [(b, Vertex)] Source #

data LTree b a Source #

Constructors

LNode
Fields rootLabelL :: a subForestL :: [(b, LTree b a)]

Instances

Instances details

Functor (LTree b) Source #
Instance details Defined in LabelledGraph Methods fmap :: (a -> b0) -> LTree b a -> LTree b b0 # (<$) :: a -> LTree b b0 -> LTree b a #
Foldable (LTree b) Source #
Instance details Defined in LabelledGraph Methods fold :: Monoid m => LTree b m -> m # foldMap :: Monoid m => (a -> m) -> LTree b a -> m # foldMap' :: Monoid m => (a -> m) -> LTree b a -> m # foldr :: (a -> b0 -> b0) -> b0 -> LTree b a -> b0 # foldr' :: (a -> b0 -> b0) -> b0 -> LTree b a -> b0 # foldl :: (b0 -> a -> b0) -> b0 -> LTree b a -> b0 # foldl' :: (b0 -> a -> b0) -> b0 -> LTree b a -> b0 # foldr1 :: (a -> a -> a) -> LTree b a -> a # foldl1 :: (a -> a -> a) -> LTree b a -> a # toList :: LTree b a -> [a] # null :: LTree b a -> Bool # length :: LTree b a -> Int # elem :: Eq a => a -> LTree b a -> Bool # maximum :: Ord a => LTree b a -> a # minimum :: Ord a => LTree b a -> a # sum :: Num a => LTree b a -> a # product :: Num a => LTree b a -> a #
Traversable (LTree b) Source #
Instance details Defined in LabelledGraph Methods traverse :: Applicative f => (a -> f b0) -> LTree b a -> f (LTree b b0) # sequenceA :: Applicative f => LTree b (f a) -> f (LTree b a) # mapM :: Monad m => (a -> m b0) -> LTree b a -> m (LTree b b0) # sequence :: Monad m => LTree b (m a) -> m (LTree b a) #
(Eq a, Eq b) => Eq (LTree b a) Source #
Instance details Defined in LabelledGraph Methods (==) :: LTree b a -> LTree b a -> Bool # (/=) :: LTree b a -> LTree b a -> Bool #
(Show a, Show b) => Show (LTree b a) Source #
Instance details Defined in LabelledGraph Methods showsPrec :: Int -> LTree b a -> ShowS # show :: LTree b a -> String # showList :: [LTree b a] -> ShowS #
(NFData a, NFData b) => NFData (LTree b a) Source #
Instance details Defined in LabelledGraph Methods rnf :: LTree b a -> () #

buildLG :: Bounds -> [LEdge b] -> LGraph b Source #

Builds a LGraph from a list of LEdges. O(n + m) for bounds size n and m edges.

dfsLTree :: LGraph b -> Vertex -> LTree b Vertex Source #

For a LGraph that is known to be a tree, returns its LTree representation. O(n).

lTreeToTree :: LTree b a -> Tree a Source #

Drops labels from an LTree. O(n).