Copyright	(c) Andrey Mokhov 2016-2018
License	MIT (see the file LICENSE)
Maintainer	andrey.mokhov@gmail.com
Stability	unstable
Safe Haskell	None
Language	Haskell2010

Algebra.Graph.Labelled.AdjacencyMap.Internal

Contents

Labelled adjacency map implementation

Description

This module exposes the implementation of edge-labelled adjacency maps. The API is unstable and unsafe, and is exposed only for documentation. You should use the non-internal module Algebra.Graph.Labelled.AdjdacencyMap instead.

Synopsis

newtype AdjacencyMap e a = AM {
- adjacencyMap :: Map a (Map a e)
}
consistent :: (Ord a, Eq e, Monoid e) => AdjacencyMap e a -> Bool

Labelled adjacency map implementation

newtype AdjacencyMap e a #

Edge-labelled graphs, where the type variable e stands for edge labels. For example, AdjacencyMap Bool a is isomorphic to unlabelled graphs defined in the top-level module Algebra.Graph.AdjacencyMap, where False and True denote the lack of and the existence of an unlabelled edge, respectively.

Constructors

AM
Fields adjacencyMap :: Map a (Map a e) The adjacency map of an edge-labelled graph: each vertex is associated with a map from its direct successors to the corresponding edge labels.

Instances

(Eq a, Eq e) => Eq (AdjacencyMap e a) #
Instance details Defined in Algebra.Graph.Labelled.AdjacencyMap.Internal Methods (==) :: AdjacencyMap e a -> AdjacencyMap e a -> Bool # (/=) :: AdjacencyMap e a -> AdjacencyMap e a -> Bool #
(Eq e, Dioid e, Num a, Ord a) => Num (AdjacencyMap e a) #	Note: this does not satisfy the usual ring laws; see `AdjacencyMap` for more details.
Instance details Defined in Algebra.Graph.Labelled.AdjacencyMap.Internal Methods (+) :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a # (-) :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a # (*) :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a # negate :: AdjacencyMap e a -> AdjacencyMap e a # abs :: AdjacencyMap e a -> AdjacencyMap e a # signum :: AdjacencyMap e a -> AdjacencyMap e a # fromInteger :: Integer -> AdjacencyMap e a #
(Ord e, Monoid e, Ord a) => Ord (AdjacencyMap e a) #
Instance details Defined in Algebra.Graph.Labelled.AdjacencyMap.Internal Methods compare :: AdjacencyMap e a -> AdjacencyMap e a -> Ordering # (<) :: AdjacencyMap e a -> AdjacencyMap e a -> Bool # (<=) :: AdjacencyMap e a -> AdjacencyMap e a -> Bool # (>) :: AdjacencyMap e a -> AdjacencyMap e a -> Bool # (>=) :: AdjacencyMap e a -> AdjacencyMap e a -> Bool # max :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a # min :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a #
(Ord a, Show a, Ord e, Show e) => Show (AdjacencyMap e a) #
Instance details Defined in Algebra.Graph.Labelled.AdjacencyMap.Internal Methods showsPrec :: Int -> AdjacencyMap e a -> ShowS # show :: AdjacencyMap e a -> String # showList :: [AdjacencyMap e a] -> ShowS #
(NFData a, NFData e) => NFData (AdjacencyMap e a) #
Instance details Defined in Algebra.Graph.Labelled.AdjacencyMap.Internal Methods rnf :: AdjacencyMap e a -> () #
(Eq e, Monoid e, Ord a) => ToGraph (AdjacencyMap e a) #	See Algebra.Graph.Labelled.AdjacencyMap.
Instance details Defined in Algebra.Graph.ToGraph Associated Types type ToVertex (AdjacencyMap e a) :: Type # Methods toGraph :: AdjacencyMap e a -> Graph (ToVertex (AdjacencyMap e a)) # foldg :: r -> (ToVertex (AdjacencyMap e a) -> r) -> (r -> r -> r) -> (r -> r -> r) -> AdjacencyMap e a -> r # isEmpty :: AdjacencyMap e a -> Bool # size :: AdjacencyMap e a -> Int # hasVertex :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Bool # hasEdge :: ToVertex (AdjacencyMap e a) -> ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Bool # vertexCount :: AdjacencyMap e a -> Int # edgeCount :: AdjacencyMap e a -> Int # vertexList :: AdjacencyMap e a -> [ToVertex (AdjacencyMap e a)] # edgeList :: AdjacencyMap e a -> [(ToVertex (AdjacencyMap e a), ToVertex (AdjacencyMap e a))] # vertexSet :: AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a)) # vertexIntSet :: AdjacencyMap e a -> IntSet # edgeSet :: AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a), ToVertex (AdjacencyMap e a)) # preSet :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a)) # preIntSet :: Int -> AdjacencyMap e a -> IntSet # postSet :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a)) # postIntSet :: Int -> AdjacencyMap e a -> IntSet # adjacencyList :: AdjacencyMap e a -> [(ToVertex (AdjacencyMap e a), [ToVertex (AdjacencyMap e a)])] # adjacencyMap :: AdjacencyMap e a -> Map (ToVertex (AdjacencyMap e a)) (Set (ToVertex (AdjacencyMap e a))) # adjacencyIntMap :: AdjacencyMap e a -> IntMap IntSet # adjacencyMapTranspose :: AdjacencyMap e a -> Map (ToVertex (AdjacencyMap e a)) (Set (ToVertex (AdjacencyMap e a))) # adjacencyIntMapTranspose :: AdjacencyMap e a -> IntMap IntSet # dfsForest :: AdjacencyMap e a -> Forest (ToVertex (AdjacencyMap e a)) # dfsForestFrom :: [ToVertex (AdjacencyMap e a)] -> AdjacencyMap e a -> Forest (ToVertex (AdjacencyMap e a)) # dfs :: [ToVertex (AdjacencyMap e a)] -> AdjacencyMap e a -> [ToVertex (AdjacencyMap e a)] # reachable :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> [ToVertex (AdjacencyMap e a)] # topSort :: AdjacencyMap e a -> Maybe [ToVertex (AdjacencyMap e a)] # isAcyclic :: AdjacencyMap e a -> Bool # toAdjacencyMap :: AdjacencyMap e a -> AdjacencyMap0 (ToVertex (AdjacencyMap e a)) # toAdjacencyMapTranspose :: AdjacencyMap e a -> AdjacencyMap0 (ToVertex (AdjacencyMap e a)) # toAdjacencyIntMap :: AdjacencyMap e a -> AdjacencyIntMap # toAdjacencyIntMapTranspose :: AdjacencyMap e a -> AdjacencyIntMap # isDfsForestOf :: Forest (ToVertex (AdjacencyMap e a)) -> AdjacencyMap e a -> Bool # isTopSortOf :: [ToVertex (AdjacencyMap e a)] -> AdjacencyMap e a -> Bool #
(Dioid e, Eq e, Ord a) => Graph (AdjacencyMap e a) #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex (AdjacencyMap e a) :: Type # Methods empty :: AdjacencyMap e a # vertex :: Vertex (AdjacencyMap e a) -> AdjacencyMap e a # overlay :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a # connect :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a #
type ToVertex (AdjacencyMap e a) #
Instance details Defined in Algebra.Graph.ToGraph type ToVertex (AdjacencyMap e a) = a
type Vertex (AdjacencyMap e a) #
Instance details Defined in Algebra.Graph.Class type Vertex (AdjacencyMap e a) = a

consistent :: (Ord a, Eq e, Monoid e) => AdjacencyMap e a -> Bool #

Check if the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and there are no zero-labelled edges. It should be impossible to create an inconsistent adjacency map, and we use this function in testing. Note: this function is for internal use only.