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.
emap :: (Eq f, Monoid f) => (e -> f) -> AdjacencyMap e a -> AdjacencyMap f aalgebraic-graphs Algebra.Graph.Labelled.AdjacencyMap Transform a graph by applying a function h to each of its edge labels. Complexity: O((n + m) * log(n)) time. 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)
fromAdjacencyMaps :: (Eq e, Monoid e, Ord a) => [(a, Map a e)] -> AdjacencyMap e aalgebraic-graphs Algebra.Graph.Labelled.AdjacencyMap Construct a graph from a list of adjacency sets. Complexity: O((n + m) * log(n)) time and O(n + m) memory.
fromAdjacencyMaps [] == empty fromAdjacencyMaps [(x, Map.empty)] == vertex x fromAdjacencyMaps [(x, Map.singleton y e)] == if e == zero then vertices [x,y] else edge e x y overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs ++ ys)
gmap :: (Eq e, Monoid e, Ord a, Ord b) => (a -> b) -> AdjacencyMap e a -> AdjacencyMap e balgebraic-graphs Algebra.Graph.Labelled.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 e x y) == edge e (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g)
module Algebra.Graph.NonEmpty.
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 data type AdjacencyMap for graphs that are known to be non-empty at compile time. To avoid name clashes with Algebra.Graph.AdjacencyMap, this module can be imported qualified:
import qualified Algebra.Graph.NonEmpty.AdjacencyMap as NonEmpty
The naming convention generally follows that of Data.List.NonEmpty: we use suffix 1 to indicate the functions whose interface must be changed compared to Algebra.Graph.AdjacencyMap, e.g. vertices1.-
algebraic-graphs Algebra.Graph.NonEmpty.AdjacencyMap 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) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))
Note: the signum method of the type class Num cannot be implemented and will throw an error. Furthermore, 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 (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices1 [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges1 [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"
The Eq instance satisfies the following laws of algebraic graphs:- overlay is commutative, associative and idempotent:
x + y == y + x x + (y + z) == (x + y) + z x + x == x
- connect is associative:
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 satisfies absorption and saturation:
x * y + x + y == x * y x * x * x == x * x
- Compare the number of vertices. In case of a tie, continue.
- Compare the sets of vertices. In case of a tie, continue.
- Compare the number of edges. In case of a tie, continue.
- Compare the sets of edges.
vertex 1 < vertex 2 vertex 3 < edge 1 2 vertex 1 < edge 1 1 edge 1 1 < edge 1 2 edge 1 2 < edge 1 1 + edge 2 2 edge 1 2 < edge 1 3
Note that the resulting order refines the isSubgraphOf relation and is compatible with overlay and connect operations:isSubgraphOf x y ==> x <= y
x <= x + y x + y <= x * y
- overlay is commutative, associative and idempotent:
gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap balgebraic-graphs Algebra.Graph.NonEmpty.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 (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)
gmap :: Ord b => (a -> b) -> Relation a -> Relation balgebraic-graphs Algebra.Graph.Relation 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 Relation. 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)
gmap :: Ord b => (a -> b) -> Relation a -> Relation balgebraic-graphs Algebra.Graph.Relation.Symmetric 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 Relation. 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)
adjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSetalgebraic-graphs Algebra.Graph.ToGraph The adjacency map of a graph: each vertex is associated with a set of its direct successors. Like adjacencyMap but specialised for graphs with vertices of type Int.
adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMap
adjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSetalgebraic-graphs Algebra.Graph.ToGraph The transposed adjacency map of a graph: each vertex is associated with a set of its direct predecessors. Like adjacencyMapTranspose but specialised for graphs with vertices of type Int.
adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMapTranspose