Algebra.Graph.Labelled.AdjacencyMap.Internal

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.

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)

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.

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)

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)

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)

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.

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)

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)

Defined in Algebra.Graph.ToGraph

type ToVertex (AdjacencyMap e a) = a

type Vertex (AdjacencyMap e a)

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.