Hoogle Search
Within LTS Haskell 24.6 (ghc-9.10.2)
Note that Stackage only displays results for the latest LTS and Nightly snapshot. Learn more.
module Algebra.Graph.
AdjacencyIntMap 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 AdjacencyIntMap data type and associated functions. See Algebra.Graph.AdjacencyIntMap.Algorithm for implementations of basic graph algorithms. AdjacencyIntMap is an instance of the Graph type class, which can be used for polymorphic graph construction and manipulation. See Algebra.Graph.AdjacencyMap for graphs with non-Int vertices.
-
algebraic-graphs Algebra.Graph.AdjacencyIntMap 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) 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 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 :: AdjacencyIntMap Int) == "empty" show (1 :: AdjacencyIntMap Int) == "vertex 1" show (1 + 2 :: AdjacencyIntMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyIntMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyIntMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyIntMap Int) == "overlay (vertex 3) (edge 1 2)"
The Eq instance satisfies all axioms of algebraic graphs:- overlay is commutative and associative:
x + y == y + x x + (y + z) == (x + y) + z
- connect is associative and has empty as the
identity:
x * empty == x empty * x == 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
- 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
- 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
empty <= x x <= x + y x + y <= x * y
- overlay is commutative and associative:
adjacencyIntMap :: AdjacencyIntMap -> IntMap IntSetalgebraic-graphs Algebra.Graph.AdjacencyIntMap 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.empty adjacencyIntMap (vertex x) == IntMap.singleton x IntSet.empty adjacencyIntMap (edge 1 1) == IntMap.singleton 1 (IntSet.singleton 1) adjacencyIntMap (edge 1 2) == IntMap.fromList [(1,IntSet.singleton 2), (2,IntSet.empty)]
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
toAdjacencyIntMap :: ToGraph t => t -> AdjacencyIntMapalgebraic-graphs Algebra.Graph.ToGraph Convert a value to the corresponding AdjacencyIntMap.
toAdjacencyIntMap == foldg empty vertex overlay connect
toAdjacencyIntMapTranspose :: ToGraph t => t -> AdjacencyIntMapalgebraic-graphs Algebra.Graph.ToGraph Convert a value to the corresponding AdjacencyIntMap and transpose the result.
toAdjacencyIntMapTranspose == foldg empty vertex overlay (flip connect)
fromAdjacencyIntMap :: AdjacencyIntMap -> GraphKL Intalgebraic-graphs Data.Graph.Typed Build GraphKL from an AdjacencyIntMap. If fromAdjacencyIntMap g == h then the following holds:
map (fromVertexKL h) (vertices $ toGraphKL h) == toAscList (vertexIntSet g) map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g toGraphKL (fromAdjacencyIntMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])] toGraphKL (fromAdjacencyIntMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])]
getIntMap :: MonadGet m => m Int -> m a -> m (IntMap a)haskoin-core Haskoin.Util.Helpers Read as a list of pairs of int and element.
putIntMap :: MonadPut m => (Int -> m ()) -> (a -> m ()) -> IntMap a -> m ()haskoin-core Haskoin.Util.Helpers No documentation available.