Hoogle Search

Within LTS Haskell 24.45 (ghc-9.10.3)

Note that Stackage only displays results for the latest LTS and Nightly snapshot. Learn more.

  1. gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b

    algebraic-graphs Algebra.Graph.AdjacencyMap

    Transform a graph by applying a function to each of its vertices. This is similar to Functor's fmap but can be used with non-fully-parametric AdjacencyMap. Complexity: O((n + m) * log(n)) time. 

    gmap f empty      == empty
gmap f (vertex x) == vertex (f x)
gmap f (edge x y) == edge (f x) (f y)
gmap id           == id
gmap f . gmap g   == gmap (f . g)

  2. module Algebra.Graph.Bipartite.AdjacencyMap

    Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details. This module defines the AdjacencyMap data type for undirected bipartite graphs and associated functions. See Algebra.Graph.Bipartite.AdjacencyMap.Algorithm for basic bipartite graph algorithms. To avoid name clashes with Algebra.Graph.AdjacencyMap, this module can be imported qualified: 

    import qualified Algebra.Graph.Bipartite.AdjacencyMap as Bipartite

  3. data AdjacencyMap a b

    algebraic-graphs Algebra.Graph.Bipartite.AdjacencyMap

    The AdjacencyMap data type represents an undirected bipartite graph. The two type parameters determine the types of vertices of each part. If the types coincide, the vertices of the left part are still treated as disjoint from the vertices of the right part. See examples for more details. We define a Num instance as a convenient notation for working with bipartite graphs: 

    0                     == rightVertex 0
swap 1                == leftVertex 1
swap 1 + 2            == vertices [1] [2]
swap 1 * 2            == edge 1 2
swap 1 + 2 * swap 3   == overlay (leftVertex 1) (edge 3 2)
swap 1 * (2 + swap 3) == connect (leftVertex 1) (vertices [3] [2])
    Note: the Num instance does not satisfy several "customary laws" of Num, which dictate that fromInteger 0 and fromInteger 1 should act as additive and multiplicative identities, and negate as additive inverse. Nevertheless, overloading fromInteger, + and * is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws. The Show instance is defined using basic graph construction primitives: 
    show empty                 == "empty"
show 1                     == "rightVertex 1"
show (swap 2)              == "leftVertex 2"
show (1 + 2)               == "vertices [] [1,2]"
show (swap (1 + 2))        == "vertices [1,2] []"
show (swap 1 * 2)          == "edge 1 2"
show (swap 1 * 2 * swap 3) == "edges [(1,2),(3,2)]"
show (swap 1 * 2 + swap 3) == "overlay (leftVertex 3) (edge 1 2)"
    The Eq instance satisfies all axioms of undirected bipartite algebraic graphs:
    • overlay is commutative and associative:
       x + y == y + x
x + (y + z) == (x + y) + z
    • connect is commutative, associative and has empty as the identity:
       x * empty == x empty * x == x x * y == y * x x * (y
* z) == (x * y) * z
    • connect distributes over overlay:
      x * (y + z) ==
x * y + x * z (x + y) * z == x * z + y * z
    • connect can be decomposed:
      x * y * z == x * y + x * z +
y * z
    • connect has the same effect as overlay on vertices of the same part:
       leftVertex x * leftVertex y == leftVertex x +
leftVertex y rightVertex x * rightVertex y == rightVertex x +
rightVertex y
    The following useful theorems can be proved from the above set of axioms.
    • overlay has empty as the identity and is idempotent:
      x + empty == x empty + x == x x + x == x
    • Absorption and saturation of connect:
      x * y + x + y ==
x * y x * x * x == x * x
    When specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges of the graph, respectively. In addition, l and r will denote the number of vertices in the left and right parts of the graph, respectively.

  4. bimap :: (Ord a, Ord b, Ord c, Ord d) => (a -> c) -> (b -> d) -> AdjacencyMap a b -> AdjacencyMap c d

    algebraic-graphs Algebra.Graph.Bipartite.AdjacencyMap

    Transform a graph by applying given functions to the vertices of each part. Complexity: O((n + m) * log(n)) time. 

    bimap f g empty           == empty
bimap f g . vertex        == vertex . Data.Bifunctor.bimap f g
bimap f g (edge x y)      == edge (f x) (g y)
bimap id id               == id
bimap f1 g1 . bimap f2 g2 == bimap (f1 . f2) (g1 . g2)

  5. leftAdjacencyMap :: AdjacencyMap a b -> Map a (Set b)

    algebraic-graphs Algebra.Graph.Bipartite.AdjacencyMap

    The adjacency map of the left part of the graph: each left vertex is associated with a set of its right neighbours. Complexity: O(1) time and memory. 

    leftAdjacencyMap empty           == Map.empty
leftAdjacencyMap (leftVertex x)  == Map.singleton x Set.empty
leftAdjacencyMap (rightVertex x) == Map.empty
leftAdjacencyMap (edge x y)      == Map.singleton x (Set.singleton y)

  6. rightAdjacencyMap :: AdjacencyMap a b -> Map b (Set a)

    algebraic-graphs Algebra.Graph.Bipartite.AdjacencyMap

    The adjacency map of the right part of the graph: each right vertex is associated with a set of its left neighbours. Complexity: O(1) time and memory. 

    rightAdjacencyMap empty           == Map.empty
rightAdjacencyMap (leftVertex x)  == Map.empty
rightAdjacencyMap (rightVertex x) == Map.singleton x Set.empty
rightAdjacencyMap (edge x y)      == Map.singleton y (Set.singleton x)

  7. emap :: (e -> f) -> Graph e a -> Graph f a

    algebraic-graphs Algebra.Graph.Labelled

    Transform a graph by applying a function to each of its edge labels. Complexity: O(s) time, memory and size. The function h is required to be a homomorphism on the underlying type of labels e. At the very least it must preserve zero and <+>: 

    h zero      == zero
h x <+> h y == h (x <+> y)
    If e is also a semiring, then h must also preserve the multiplicative structure: 
    h one       == one
h x <.> h y == h (x <.> y)
    If the above requirements hold, then the implementation provides the following guarantees. 
    emap h empty           == empty
emap h (vertex x)      == vertex x
emap h (edge e x y)    == edge (h e) x y
emap h (overlay x y)   == overlay (emap h x) (emap h y)
emap h (connect e x y) == connect (h e) (emap h x) (emap h y)
emap id                == id
emap g . emap h        == emap (g . h)

  8. module Algebra.Graph.Labelled.AdjacencyMap

    Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details. This module defines the AdjacencyMap data type for edge-labelled graphs, as well as associated operations and algorithms. AdjacencyMap is an instance of the Graph type class, which can be used for polymorphic graph construction and manipulation.

  9. data AdjacencyMap e a

    algebraic-graphs Algebra.Graph.Labelled.AdjacencyMap

    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.

  10. adjacencyMap :: AdjacencyMap e a -> Map a (Map a e)

    algebraic-graphs Algebra.Graph.Labelled.AdjacencyMap

    The adjacency map of an edge-labelled graph: each vertex is associated with a map from its direct successors to the corresponding edge labels.

Page 1015 of many | Previous | Next