| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Math.Graph.Reversible
Description
Graph representation as a set with action of a monoid. See Lawvere,Rosebrugh: Sets for Mathematics for details.
This module implements graphs using a representation as a set with an action of a monoid.
For directed graph, the monoid Three is used, which represents operations of id,source and target
For undirected graph, the monoid Four is used, which represents operations of id,source, target and inverse.
See Math.Graph.InGraphMonad for how to read graphs in monadic context
See Math.Graph.InGraphA for how to read graphs in arrow context
Synopsis
- data Graph m a = Graph {}
- elements :: Ord a => Graph m a -> Set a
- action :: Graph m a -> a -> m Bool Bool -> a
- setAction :: Ord a => Graph m a -> Set a -> m Bool Bool -> Set a
- listAction :: Ord a => Graph m a -> [a] -> m Bool Bool -> [a]
- action_rep :: Graph m a -> Endo a :<-: m Bool Bool
- inverseImageG :: (m Bool Bool -> n Bool Bool) -> Graph n a -> Graph m a
- emptyG :: Graph m b
- vertexG :: a -> Graph m a
- verticesFromSetG :: Set a -> Graph m a
- verticesG :: Ord a => [a] -> Graph m a
- edgeG :: Ord a => a -> a -> a -> Graph Three a
- binopG :: Set b -> Set b -> (arr Bool Bool -> b -> b) -> Graph arr b
- data EitherMonoid m a b where
- EitherMonoid :: m Bool Bool -> m Bool Bool -> EitherMonoid m a a
- discriminatedUnionG :: (Ord a, Ord b) => Graph m a -> Graph m b -> Graph (EitherMonoid m) (Either a b)
- intersectionG :: Ord a => Graph m a -> Graph m a -> Graph m a
- complementG :: ReversibleGraphMonoid m Bool => Graph m a -> Graph m a
- productG :: (Ord a, Ord b) => Graph m a -> Graph m b -> Graph m (a, b)
- unionG :: (Ord a, Show a, Show (m Bool Bool)) => Graph m a -> Graph m a -> Graph m a
- completeG :: Ord a => [a] -> (a -> a -> a) -> Graph Three a
- edgesFromMapG :: Ord a => Map a (a, a) -> Graph Three a
- edgesG :: Ord a => [(a, (a, a))] -> Graph Three a
- loopG :: Ord a => [(a, a)] -> Graph Three a
- reversibleToDirectedG :: Graph Four a -> Graph Three a
- inverseGraphG :: Group (m Bool Bool) => Graph m a -> Graph m a
- mapG :: (Ord a, Ord b) => (a :==: b) -> Graph m a :==: Graph m b
- reversibleEdgeG :: Ord a => a -> a -> a -> a -> Graph Four a
- reversibleCompleteG :: Ord a => [a] -> (a -> a -> (a, a)) -> Graph Four a
- reversibleEdgesG :: Ord a => [((a, a), (a, a))] -> Graph Four a
- subobjectClassifierGraphG :: Graph Four Text
Documentation
Graph representation containing a set of elements. an element of a graph is either an edge or a vertex.
the action_endomorphism allows obtaining source vertex, target vertex and inverse edge of an element
See GraphMonoid for details.
Note that the monoid data structure contains only names of the monoid elements - the action_endomorphism is then used to convert it to actual operation.
Constructors
| Graph | |
Instances
verticesFromSetG :: Set a -> Graph m a Source #
data EitherMonoid m a b where Source #
Constructors
| EitherMonoid :: m Bool Bool -> m Bool Bool -> EitherMonoid m a a |
discriminatedUnionG :: (Ord a, Ord b) => Graph m a -> Graph m b -> Graph (EitherMonoid m) (Either a b) Source #
complementG :: ReversibleGraphMonoid m Bool => Graph m a -> Graph m a Source #
completeG :: Ord a => [a] -> (a -> a -> a) -> Graph Three a Source #
In a complete graph, every pair of vertices (x,y) has a single link.
completeG \["1","2","3"\] \(++\) == [1, 2, 3] ; [11 = 1 -> 1, 12 = 1 -> 2, 13 = 1 -> 3, 21 = 2 -> 1, 22 = 2 -> 2, 23 = 2 -> 3, 31 = 3 -> 1, 32 = 3 -> 2, 33 = 3 -> 3]
Note though that edge names produced from pair of vertices by the function given must be unique, no overlaps are allowed, so it is required that for call 'completeG vertices edge'
forall v,w : vertices . (v != v' || w != w') => edge v w != edge v' w'
loopG :: Ord a => [(a, a)] -> Graph Three a Source #
given a list of (v,e), the loopG contains looped edges of the form e : v -> v.
reversibleToDirectedG :: Graph Four a -> Graph Three a Source #
converts from undirected graph to directed graph
mapG :: (Ord a, Ord b) => (a :==: b) -> Graph m a :==: Graph m b Source #
mapG uses an isomorphism of graph elements to permute a graph.