Hoogle Search

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

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
```

algebraic-graphs	Algebra.Graph.AdjacencyIntMap

algebraic-graphs	Algebra.Graph.AdjacencyIntMap

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

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)
```
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
```
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.

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)

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)
```

Page 1013 of many | Previous | Next