Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
This module contains helper functions for games that can be modeled as graphs.
It contains a few functions for creating graphs of different shapes and with
different properties. hexHexGraph
, paraHexGraph
, rectOctGraph
, and more.
It also contains a few functions that can automatically implement
PositionalGame
for most cases. These are named after the function
they implement, prefixed with coloredGraph
and the addition of how the
implement them. For example coloredGraphGetVertexPosition
and
coloredGraphSetBidirectedEdgePosition
.
Synopsis
- type ColoredGraph i a b = Map i (a, Map i b)
- class ColoredGraphTransformer i a b g | g -> i, g -> a, g -> b where
- toColoredGraph :: g -> ColoredGraph i a b
- fromColoredGraph :: g -> ColoredGraph i a b -> g
- hexHexGraph :: Int -> ColoredGraph (Int, Int) Position (Int, Int)
- paraHexGraph :: Int -> ColoredGraph (Int, Int) Position (Int, Int)
- rectOctGraph :: Int -> Int -> ColoredGraph (Int, Int) Position (Int, Int)
- triHexGraph :: Int -> ColoredGraph (Int, Int) Position (Int, Int)
- completeGraph :: Int -> ColoredGraph Int () ()
- mapValues :: Ord i => (a -> c) -> ColoredGraph i a b -> ColoredGraph i c b
- mapEdges :: Ord i => (b -> c) -> ColoredGraph i a b -> ColoredGraph i a c
- filterValues :: Ord i => (a -> Bool) -> ColoredGraph i a b -> ColoredGraph i a b
- filterEdges :: (b -> Bool) -> ColoredGraph i a b -> ColoredGraph i a b
- filterG :: Ord i => ((a, Map i b) -> Bool) -> ColoredGraph i a b -> ColoredGraph i a b
- components :: (Eq i, Ord i) => ColoredGraph i a b -> [[i]]
- anyConnections :: Ord i => (Int -> Bool) -> [[i]] -> ColoredGraph i a b -> Maybe [i]
- edgePath :: [a] -> [(a, a)]
- inARow :: (Ord i, Eq b) => (Int -> Bool) -> b -> ColoredGraph i a b -> Maybe [i]
- values :: ColoredGraph i a b -> [a]
- winningSetPaths :: Ord i => ColoredGraph i a b -> [i] -> [i] -> [[i]]
- winningSetPaths' :: Ord i => ColoredGraph i a b -> Map i Bool -> i -> Map i Bool -> Tree (Bool, i)
- coloredGraphVertexPositions :: (ColoredGraphTransformer i a b g, Ord i) => g -> [a]
- coloredGraphSetVertexPosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> i -> a -> Maybe g
- coloredGraphGetVertexPosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> i -> Maybe a
- coloredGraphEdgePositions :: (ColoredGraphTransformer i a b g, Ord i) => g -> [b]
- coloredGraphGetEdgePosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> (i, i) -> Maybe b
- coloredGraphSetEdgePosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> (i, i) -> b -> Maybe g
- coloredGraphSetBidirectedEdgePosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> (i, i) -> b -> Maybe g
Documentation
type ColoredGraph i a b = Map i (a, Map i b) Source #
A Graph with colored vertices and edges. The key of the map is i
, the
"coordinates". The value of the map is a tuple of vertices color a
, and
a list of edges. The edges are tuples of edge color b
and
"target coordinate" i
.
class ColoredGraphTransformer i a b g | g -> i, g -> a, g -> b where Source #
A utility class for transforming to and from ColoredGraph
.
New-types of ColoredGraph
can derive this using the
GeneralizedNewtypeDeriving
language extension.
toColoredGraph :: g -> ColoredGraph i a b Source #
Extracts the ColoredGraph
from a container type.
fromColoredGraph :: g -> ColoredGraph i a b -> g Source #
Inserts the ColoredGraph
into an already existing container type.
Instances
ColoredGraphTransformer i a b (ColoredGraph i a b) Source # | |
Defined in Boardgame.ColoredGraph toColoredGraph :: ColoredGraph i a b -> ColoredGraph i a b Source # fromColoredGraph :: ColoredGraph i a b -> ColoredGraph i a b -> ColoredGraph i a b Source # |
hexHexGraph :: Int -> ColoredGraph (Int, Int) Position (Int, Int) Source #
Creates a hexagon shaped graph of hexagon vertices (each vertex has six outgoing edges) with the given radius.
The "coordinates" of the graph will be '(Int, Int)' where '(0, 0)' is at the center. The color of edges will also be a '(Int, Int)' tuple that shows the "direction" of the edge.
paraHexGraph :: Int -> ColoredGraph (Int, Int) Position (Int, Int) Source #
Creates a parallelogram shaped graph of hexagon vertices (each vertex has six outgoing edges) with the given side length.
The "coordinates" of the graph will be '(Int, Int)' where '(0, 0)' is at the center. The color of edges will also be a '(Int, Int)' tuple that shows the "direction" of the edge.
rectOctGraph :: Int -> Int -> ColoredGraph (Int, Int) Position (Int, Int) Source #
Creates a rectangular shaped graph of octagon vertices (each vertex has eight outgoing edges) with the given width and height.
The "coordinates" of the graph will be '(Int, Int)' where '(0, 0)' the top left vertex. The color of edges will also be a '(Int, Int)' tuple that shows the "direction" of the edge.
triHexGraph :: Int -> ColoredGraph (Int, Int) Position (Int, Int) Source #
Creates a triangular shaped graph of hexagon vertices (each vertex has six outgoing edges) with the given side length.
The "coordinates" of the graph will be '(Int, Int)' where '(1, n-1)', '(n-1, 1)' and '(n-1, n-1)' are the 3 corners. The color of edges will also be a '(Int, Int)' tuple that shows the "direction" of the edge.
completeGraph :: Int -> ColoredGraph Int () () Source #
Creates a complete graph with n vertices.
mapValues :: Ord i => (a -> c) -> ColoredGraph i a b -> ColoredGraph i c b Source #
Maps the values of vertices with the given function.
mapEdges :: Ord i => (b -> c) -> ColoredGraph i a b -> ColoredGraph i a c Source #
Maps the values of edges with the given function.
filterValues :: Ord i => (a -> Bool) -> ColoredGraph i a b -> ColoredGraph i a b Source #
Filters out any vertices whose value is not accepted by the predicate.
filterEdges :: (b -> Bool) -> ColoredGraph i a b -> ColoredGraph i a b Source #
Filters out any edges whose value is not accepted by the predicate.
filterG :: Ord i => ((a, Map i b) -> Bool) -> ColoredGraph i a b -> ColoredGraph i a b Source #
Filters out any vertices whose value, and their outgoing edges with values, is not accepted by the predicate.
components :: (Eq i, Ord i) => ColoredGraph i a b -> [[i]] Source #
A list of all vertices grouped by connected components.
anyConnections :: Ord i => (Int -> Bool) -> [[i]] -> ColoredGraph i a b -> Maybe [i] Source #
For every component of G, count how many groups of nodes they overlap with and check if the predicate holds on the count. If it matches on any component then return that component. We also try to return only the parts of the component that are necessary for our predicate to hold.
edgePath :: [a] -> [(a, a)] Source #
Takes a path of vertices and returns a path of edges. Where the edges are pairs of from and to vertices.
inARow :: (Ord i, Eq b) => (Int -> Bool) -> b -> ColoredGraph i a b -> Maybe [i] Source #
Is there a component along edges with value dir
that has a length
accepted by pred
? If there is we return a subset of that component that
matches the predicate
values :: ColoredGraph i a b -> [a] Source #
Returns a list of vertex values from the given graph.
winningSetPaths :: Ord i => ColoredGraph i a b -> [i] -> [i] -> [[i]] Source #
Returns the winning sets representing paths from one set of nodes to another on a graph.
winningSetPaths' :: Ord i => ColoredGraph i a b -> Map i Bool -> i -> Map i Bool -> Tree (Bool, i) Source #
Returns a tree representing all paths from a starting node too any node in the goal. The paths do not "touch" themselves and they only use a set of allowed nodes. That they don't touch means that we generate exactly the minimum set of winning sets that cover reaching from our starting node to the goal.
coloredGraphVertexPositions :: (ColoredGraphTransformer i a b g, Ord i) => g -> [a] Source #
A standard implementation of positions
for games
with an underlying ColoredGraph
played on the vertices.
For ColoredGraph
s, this is a synonym of values
.
coloredGraphSetVertexPosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> i -> a -> Maybe g Source #
A standard implementation of setPosition
for games
with an underlying ColoredGraph
played on the vertices.
coloredGraphGetVertexPosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> i -> Maybe a Source #
A standard implementation of getPosition
for games
with an underlying ColoredGraph
played on the vertices.
coloredGraphEdgePositions :: (ColoredGraphTransformer i a b g, Ord i) => g -> [b] Source #
A standard implementation of positions
for games
with an underlying ColoredGraph
played on the edges.
coloredGraphGetEdgePosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> (i, i) -> Maybe b Source #
A standard implementation of getPosition
for games
with an underlying ColoredGraph
played on the edges.
coloredGraphSetEdgePosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> (i, i) -> b -> Maybe g Source #
A standard implementation of setPosition
for games
with an underlying ColoredGraph
played on the vertices.
coloredGraphSetBidirectedEdgePosition :: (ColoredGraphTransformer i a b g, Ord i) => g -> (i, i) -> b -> Maybe g Source #
Like coloredGraphSetEdgePosition
but sets the value to the edges in both
directions.