Aelve Codesearch

grep over package repositories
Please provide a string to search for.
3+ characters are required.
Index updated 3 hours ago

total matches: more than 1000

algebraic-graphs-0.4
30 matches
src/Algebra/Graph/AdjacencyIntMap/Internal.hs
-- non-internal module "Algebra.Graph.AdjacencyIntMap" instead.
-----------------------------------------------------------------------------
module Algebra.Graph.AdjacencyIntMap.Internal (
    -- * Adjacency map implementation
    AdjacencyIntMap (..), consistent
  ) where

import Prelude ()
import Prelude.Compat hiding (null)

            
src/Algebra/Graph/AdjacencyIntMap/Internal.hs
import qualified Data.IntMap.Strict as IntMap
import qualified Data.IntSet        as IntSet

{-| The 'AdjacencyIntMap' data type represents a graph by a map of vertices to
their adjacency sets. We define a 'Num' instance as a convenient notation for
working with graphs:

    > 0           == vertex 0
    > 1 + 2       == overlay (vertex 1) (vertex 2)

            
src/Algebra/Graph/AdjacencyIntMap/Internal.hs
x + y <= x * y@
-}
newtype AdjacencyIntMap = AM {
    -- | The /adjacency map/ of a graph: each vertex is associated with a set of
    -- its direct successors. Complexity: /O(1)/ time and memory.
    --
    -- @
    -- adjacencyIntMap 'empty'      == IntMap.'IntMap.empty'
    -- adjacencyIntMap ('vertex' x) == IntMap.'IntMap.singleton' x IntSet.'IntSet.empty'

            
src/Algebra/Graph/AdjacencyIntMap/Internal.hs

-- | Check if the internal graph representation is consistent, i.e. that all
-- edges refer to existing vertices. 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/.
--
-- @
-- consistent 'Algebra.Graph.AdjacencyIntMap.empty'         == True
-- consistent ('Algebra.Graph.AdjacencyIntMap.vertex' x)    == True

            
src/Algebra/Graph/AdjacencyIntMap/Internal.hs
referredToVertexSet :: IntMap IntSet -> IntSet
referredToVertexSet = IntSet.fromList . uncurry (++) . unzip . internalEdgeList

-- The list of edges in adjacency map
internalEdgeList :: IntMap IntSet -> [(Int, Int)]
internalEdgeList m = [ (x, y) | (x, ys) <- IntMap.toAscList m, y <- IntSet.toAscList ys ]

            
src/Algebra/Graph/AdjacencyMap/Internal.hs
-- Maintainer : andrey.mokhov@gmail.com
-- Stability  : unstable
--
-- This module exposes the implementation of adjacency maps. The API is unstable
-- and unsafe, and is exposed only for documentation. You should use the
-- non-internal module "Algebra.Graph.AdjacencyMap" instead.
-----------------------------------------------------------------------------
module Algebra.Graph.AdjacencyMap.Internal (
    -- * Adjacency map implementation

            
src/Algebra/Graph/AdjacencyMap/Internal.hs
-- non-internal module "Algebra.Graph.AdjacencyMap" instead.
-----------------------------------------------------------------------------
module Algebra.Graph.AdjacencyMap.Internal (
    -- * Adjacency map implementation
    AdjacencyMap (..), consistent, internalEdgeList, referredToVertexSet
  ) where

import Prelude ()
import Prelude.Compat hiding (null)

            
src/Algebra/Graph/AdjacencyMap/Internal.hs
import qualified Data.Map.Strict as Map
import qualified Data.Set        as Set

{-| The 'AdjacencyMap' data type represents a graph by a map of vertices to
their adjacency sets. We define a 'Num' instance as a convenient notation for
working with graphs:

    > 0           == vertex 0
    > 1 + 2       == overlay (vertex 1) (vertex 2)

            
src/Algebra/Graph/AdjacencyMap/Internal.hs
x + y <= x * y@
-}
newtype AdjacencyMap a = AM {
    -- | The /adjacency map/ of a graph: each vertex is associated with a set of
    -- its direct successors. Complexity: /O(1)/ time and memory.
    --
    -- @
    -- adjacencyMap 'Algebra.Graph.AdjacencyMap.empty'      == Map.'Map.empty'
    -- adjacencyMap ('Algebra.Graph.AdjacencyMap.vertex' x) == Map.'Map.singleton' x Set.'Set.empty'

            
src/Algebra/Graph/AdjacencyMap/Internal.hs

-- | Check if the internal graph representation is consistent, i.e. that all
-- edges refer to existing vertices. 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/.
--
-- @
-- consistent 'Algebra.Graph.AdjacencyMap.empty'         == True
-- consistent ('Algebra.Graph.AdjacencyMap.vertex' x)    == True

            
src/Algebra/Graph/AdjacencyMap/Internal.hs
consistent :: Ord a => AdjacencyMap a -> Bool
consistent (AM m) = referredToVertexSet m `Set.isSubsetOf` keysSet m

-- | The list of edges of an adjacency map.
-- /Note: this function is for internal use only/.
internalEdgeList :: Map a (Set a) -> [(a, a)]
internalEdgeList m = [ (x, y) | (x, ys) <- Map.toAscList m, y <- Set.toAscList ys ]

-- | The set of vertices that are referred to by the edges of an adjacency map.

            
src/Algebra/Graph/AdjacencyMap/Internal.hs
internalEdgeList :: Map a (Set a) -> [(a, a)]
internalEdgeList m = [ (x, y) | (x, ys) <- Map.toAscList m, y <- Set.toAscList ys ]

-- | The set of vertices that are referred to by the edges of an adjacency map.
-- /Note: this function is for internal use only/.
referredToVertexSet :: Ord a => Map a (Set a) -> Set a
referredToVertexSet = Set.fromList . uncurry (++) . unzip . internalEdgeList

            
src/Algebra/Graph/Class.hs
-- vertices [x] == 'vertex' x
-- @
vertices :: Graph g => [Vertex g] -> g
vertices = overlays . map vertex

-- | Construct the graph from a list of edges.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--

            
src/Algebra/Graph/Class.hs
-- edges [(x,y)] == 'edge' x y
-- @
edges :: Graph g => [(Vertex g, Vertex g)] -> g
edges = overlays . map (uncurry edge)

-- | Overlay a given list of graphs.
-- Complexity: /O(L)/ time and memory, and /O(S)/ size, where /L/ is the length
-- of the given list, and /S/ is the sum of sizes of the graphs in the list.
--

            
src/Algebra/Graph/Class.hs
-- clique (xs ++ ys) == 'connect' (clique xs) (clique ys)
-- @
clique :: Graph g => [Vertex g] -> g
clique = connects . map vertex

-- | The /biclique/ on two lists of vertices.
-- Complexity: /O(L1 + L2)/ time, memory and size, where /L1/ and /L2/ are the
-- lengths of the given lists.
--

            
src/Algebra/Graph/Class.hs
-- @
tree :: Graph g => Tree (Vertex g) -> g
tree (Node x []) = vertex x
tree (Node x f ) = star x (map rootLabel f)
    `overlay` forest (filter (not . null . subForest) f)

-- | The /forest graph/ constructed from a given 'Forest' data structure.
-- Complexity: /O(F)/ time, memory and size, where /F/ is the size of the
-- given forest (i.e. the number of vertices in the forest).

            
src/Algebra/Graph/Class.hs
-- forest []                                                  == 'empty'
-- forest [x]                                                 == 'tree' x
-- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == 'edges' [(1,2), (1,3), (4,5)]
-- forest                                                     == 'overlays' . 'map' 'tree'
-- @
forest :: Graph g => Forest (Vertex g) -> g
forest = overlays . map tree

            
src/Algebra/Graph/Export.hs
-- implementation uses difference lists). Here @s@ is the type of abstract
-- symbols or strings (text or binary). 'Doc' @s@ is a 'Monoid', therefore
-- 'mempty' corresponds to the /empty document/ and two documents can be
-- concatenated with 'mappend' (or operator 'Data.Monoid.<>'). Documents
-- comprising a single symbol or string can be constructed using the function
-- 'literal'. Alternatively, you can construct documents as string literals,
-- e.g. simply as @"alga"@, by using the @OverloadedStrings@ GHC extension. To
-- extract the document contents use the function 'render'.
--

            
src/Algebra/Graph/Export.hs
export :: (Ord a, ToGraph g, ToVertex g ~ a) => (a -> Doc s) -> (a -> a -> Doc s) -> g -> Doc s
export v e g = vDoc <> eDoc
  where
    vDoc   = mconcat $ map  v          (vertexList adjMap)
    eDoc   = mconcat $ map (uncurry e) (edgeList   adjMap)
    adjMap = toAdjacencyMap g

            
src/Algebra/Graph/Fold.hs
Converting a 'Fold' to the corresponding 'AM.AdjacencyMap' takes /O(s + m * log(m))/
time and /O(s + m)/ memory. This is also the complexity of the graph equality test,
because it is currently implemented by converting graph expressions to canonical
representations based on adjacency maps.

The total order on graphs is defined using /size-lexicographic/ comparison:

* Compare the number of vertices. In case of a tie, continue.
* Compare the sets of vertices. In case of a tie, continue.

            
src/Algebra/Graph/Fold.hs
    negate      = id

instance Functor Fold where
    fmap f = foldg empty (vertex . f) overlay connect

instance Applicative Fold where
    pure  = vertex
    (<*>) = ap


            
src/Algebra/Graph/Fold.hs
-- 'vertexSet'   . vertices == Set.'Set.fromList'
-- @
vertices :: [a] -> Fold a
vertices = overlays . map vertex
{-# NOINLINE [1] vertices #-}

-- | Construct the graph from a list of edges.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.

            
src/Algebra/Graph/Fold.hs
-- edgeList ('edge' x y)     == [(x,y)]
-- edgeList ('star' 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . 'edges'        == 'Data.List.nub' . 'Data.List.sort'
-- edgeList . 'transpose'    == 'Data.List.sort' . 'map' 'Data.Tuple.swap' . edgeList
-- @
edgeList :: Ord a => Fold a -> [(a, a)]
edgeList = T.edgeList

-- | The set of vertices of a given graph.

            
src/Algebra/Graph/Fold.hs
-- clique . 'reverse'  == 'transpose' . clique
-- @
clique :: [a] -> Fold a
clique = connects . map vertex
{-# NOINLINE [1] clique #-}

-- | The /biclique/ on two lists of vertices.
-- Complexity: /O(L1 + L2)/ time, memory and size, where /L1/ and /L2/ are the
-- lengths of the given lists.

            
src/Algebra/Graph/Fold.hs
-- stars [(x, [])]               == 'vertex' x
-- stars [(x, [y])]              == 'edge' x y
-- stars [(x, ys)]               == 'star' x ys
-- stars                         == 'overlays' . 'map' ('uncurry' 'star')
-- stars . 'adjacencyList'         == id
-- 'overlay' (stars xs) (stars ys) == stars (xs ++ ys)
-- @
stars :: [(a, [a])] -> Fold a
stars = overlays . map (uncurry star)

            
src/Algebra/Graph/Fold.hs
-- 'overlay' (stars xs) (stars ys) == stars (xs ++ ys)
-- @
stars :: [(a, [a])] -> Fold a
stars = overlays . map (uncurry star)
{-# INLINE stars #-}

-- | Remove a vertex from a given graph.
-- Complexity: /O(s)/ time, memory and size.
--

            
src/Algebra/Graph/Fold.hs
-- transpose ('edge' x y)  == 'edge' y x
-- transpose . transpose == id
-- transpose ('box' x y)   == 'box' (transpose x) (transpose y)
-- 'edgeList' . transpose  == 'Data.List.sort' . 'map' 'Data.Tuple.swap' . 'edgeList'
-- @
transpose :: Fold a -> Fold a
transpose = foldg empty vertex overlay (flip connect)
{-# NOINLINE [1] transpose #-}


            
src/Algebra/Graph/Fold.hs
"transpose/overlay"  forall g1 g2. transpose (overlay g1 g2) = overlay (transpose g1) (transpose g2)
"transpose/connect"  forall g1 g2. transpose (connect g1 g2) = connect (transpose g2) (transpose g1)

"transpose/overlays" forall xs. transpose (overlays xs) = overlays (map transpose xs)
"transpose/connects" forall xs. transpose (connects xs) = connects (reverse (map transpose xs))

"transpose/vertices" forall xs. transpose (vertices xs) = vertices xs
"transpose/clique"   forall xs. transpose (clique xs)   = clique (reverse xs)
 #-}


            
src/Algebra/Graph/HigherKinded/Class.hs
-- edges [(x,y)] == 'edge' x y
-- @
edges :: Graph g => [(a, a)] -> g a
edges = overlays . map (uncurry edge)

-- | Overlay a given list of graphs.
-- Complexity: /O(L)/ time and memory, and /O(S)/ size, where /L/ is the length
-- of the given list, and /S/ is the sum of sizes of the graphs in the list.
--

            
src/Algebra/Graph/HigherKinded/Class.hs
-- clique (xs ++ ys) == 'connect' (clique xs) (clique ys)
-- @
clique :: Graph g => [a] -> g a
clique = connects . map vertex

-- | The /biclique/ on two lists of vertices.
-- Complexity: /O(L1 + L2)/ time, memory and size, where /L1/ and /L2/ are the
-- lengths of the given lists.
--