Hoogle Search

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

module Algebra.Graph.Acyclic.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 and for acyclic graphs, as well as associated operations and algorithms. To avoid name clashes with Algebra.Graph.AdjacencyMap, this module can be imported qualified:
```
import qualified Algebra.Graph.Acyclic.AdjacencyMap as Acyclic
```
data AdjacencyMap a

algebraic-graphs Algebra.Graph.Acyclic.AdjacencyMap

The AdjacencyMap data type represents an acyclic graph by a map of vertices to their adjacency sets. Although the internal representation allows for cycles, the methods provided by this module cannot be used to construct a graph with cycles. The Show instance is defined using basic graph construction primitives where possible, falling back to toAcyclic and Algebra.Graph.AdjacencyMap otherwise:
```
show empty                == "empty"
show (shrink 1)           == "vertex 1"
show (shrink $ 1 + 2)     == "vertices [1,2]"
show (shrink $ 1 * 2)     == "(fromJust . toAcyclic) (edge 1 2)"
show (shrink $ 1 * 2 * 3) == "(fromJust . toAcyclic) (edges [(1,2),(1,3),(2,3)])"
show (shrink $ 1 * 2 + 3) == "(fromJust . toAcyclic) (overlay (vertex 3) (edge 1 2))"
```
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.
- Compare the number of edges. In case of a tie, continue.
- Compare the sets of edges.
Note that the resulting order refines the isSubgraphOf relation:
```
isSubgraphOf x y ==> x <= y
```
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.
data AdjacencyIntMap

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
```
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 in the graph, respectively. 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.
- Compare the number of edges. In case of a tie, continue.
- Compare the sets of edges.
Here are a few examples:
```
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
```

algebraic-graphs	Algebra.Graph.Acyclic.AdjacencyMap

adjacencyIntMap :: AdjacencyIntMap -> IntMap IntSet

algebraic-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)]

fromAdjacencyMap :: AdjacencyMap Int -> AdjacencyIntMap

algebraic-graphs Algebra.Graph.AdjacencyIntMap

Construct an AdjacencyIntMap from an AdjacencyMap with vertices of type Int. Complexity: O(n + m) time and memory.
```
fromAdjacencyMap == stars . AdjacencyMap.adjacencyList
```
gmap :: (Int -> Int) -> AdjacencyIntMap -> AdjacencyIntMap

algebraic-graphs Algebra.Graph.AdjacencyIntMap

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 AdjacencyIntMap. 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)
```
module Algebra.Graph.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 and associated functions. See Algebra.Graph.AdjacencyMap.Algorithm for basic graph algorithms. AdjacencyMap is an instance of the Graph type class, which can be used for polymorphic graph construction and manipulation. Algebra.Graph.AdjacencyIntMap defines adjacency maps specialised to graphs with Int vertices.
data AdjacencyMap a

algebraic-graphs Algebra.Graph.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 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     :: AdjacencyMap Int) == "empty"
show (1         :: AdjacencyMap Int) == "vertex 1"
show (1 + 2     :: AdjacencyMap Int) == "vertices [1,2]"
show (1 * 2     :: AdjacencyMap Int) == "edge 1 2"
show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: AdjacencyMap 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
```
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 in the graph, respectively. 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.
- Compare the number of edges. In case of a tie, continue.
- Compare the sets of edges.
Here are a few examples:
```
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
```

adjacencyMap :: AdjacencyMap a -> Map a (Set a)

algebraic-graphs	Algebra.Graph.AdjacencyMap

The adjacency map of a graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory.

adjacencyMap empty      == Map.empty
adjacencyMap (vertex x) == Map.singleton x Set.empty
adjacencyMap (edge 1 1) == Map.singleton 1 (Set.singleton 1)
adjacencyMap (edge 1 2) == Map.fromList [(1,Set.singleton 2), (2,Set.empty)]

Page 1014 of many | Previous | Next