Safe Haskell	None

InGraph

Contents

Types
Functions
Misc

Description

Ingress Graph module. The routines in this module support optimizing links between portals in the game Ingress.

Synopsis

Types

data Vector a

Constructors

Vec (a, a)

Instances

Functor Vector
Eq a => Eq (Vector a)
Num a => Num (Vector a)	Allow math to be used with a `Vector`
Show a => Show (Vector a)

type Portal = (String, Vector Float)

type PortalGraph = Gr Portal ()

type Hamiltonian = Float -> PortalGraph -> Float

Functions

Graph handling routines

emptyGraph :: PortalGraph

addPortals :: PortalGraph -> [Portal] -> PortalGraph

Add a list of portals to a portal graph

newNode :: PortalGraph -> Node

Determine the id of the next node to add

stripEdges :: PortalGraph -> PortalGraph

Remove all of the edges from a graph

Mathematical Utilities

mean :: (Real a, Fractional b) => [a] -> b

Arithmetic mean

std :: (Real a, Fractional b) => [a] -> b

Standard deviation

dot :: Num a => Vector a -> Vector a -> a

Vector dot product

norm :: Floating a => Vector a -> a

Vector length

cross2D :: Num a => Vector a -> Vector a -> a

Two dimensional cross product, used for link crossing

vecAngle :: Floating a => Vector a -> Vector a -> a

Vector angle

Graph queries

linksCross :: (Portal, Portal) -> (Portal, Portal) -> Bool

Determine whether or not links between two pairs of portals cross

adjFields

Arguments

:: PortalGraph	Graph to analyze
-> Node	Find fields with this node as a vertex
-> [(Node, Node)]	A list containing pairs of vertices that make a trianlge with the given reference vertex

Count the number of fields adjacent to a portal. Returns a list of endpoint pairs for each triangle. For instance:

>>> adjFields g 1
[(2,3),(3,4)]

Specifies that node 1 makes triangles (1,2,3) and (1,3,4).

getFields :: PortalGraph -> [[Node]]

Return a collection of fields present in a graph. Fields are returned as a list of node lists. Each node list contains the 3 nodes that make up a particular field.

portalVec :: PortalGraph -> Node -> Vector Float

Extract the position of a portal

isCoveredBy

Arguments

:: PortalGraph
-> Node	The portal node id
-> [Node]	Three element list of field vertices
-> Bool

Determine whether a portal is covered by a particular field

isCovered

Arguments

:: PortalGraph
-> Node	The portal node id
-> Bool

Determine whether a portal is covered by any field

countCoverings

Arguments

:: PortalGraph
-> Node	The portal node id
-> Int	Number of covering fields

Count how many fields are covering a portal

fieldArea :: Portal -> Portal -> Portal -> Float

Calculate the area covered by a field

fieldAreaG :: PortalGraph -> Node -> Node -> Node -> Float

Calculate the area covered by a field, using graph node numbers

makesCross

Arguments

:: PortalGraph
-> (Node, Node)	Tuple containing from and to portal ids
-> Bool

Determine whether a potential link would cross an existing link

Optimization

Hamiltonian Functions

hamiltonianFlynn :: Float -> PortalGraph -> Float

Hamiltonian for the "Save Flynn" event

hamiltonianFields :: Float -> PortalGraph -> Float

Hamiltonian for maximizing the number of fields. This function has a hard time when optimizing in link mode. For best results, use in field mode.

hamiltonianLinks :: Float -> PortalGraph -> Float

Hamiltonian for maximizing global number of links.

hamiltonianDegree :: Float -> PortalGraph -> Float

Hamiltonian for maximizing degree, while keeping the degree as constant as possible.

hamiltonianLinkDefense :: Float -> PortalGraph -> Float

Hamiltonian for maximizing portal defense due to links. There is a defensive boost to shields according to

 Boost = 4/9 * atan(L/exp(1))

where L is the number of links.

hamiltonianAP :: Float -> PortalGraph -> Float

Hamiltonian for maximizing AP due to creating links and fields

hamiltonianRatio :: Float -> PortalGraph -> Float

Hamiltonian for minimizing the ratio of AP to destroy to AP to create.

hamiltonianUCLA :: Float -> PortalGraph -> Float

Hamiltonian for maximizing the score at the UCLA Warp Break event

portalEnergy

Arguments

:: Float	Importance of making fields, 0 to 1
-> PortalGraph	The current graph
-> Node	Calculate the energy of this node
-> Float	Returns portal energy

Calculate the energy of a single portal. Energy is defined to be the ratio of AP due to destruction over AP due to creation. This is then scaled by the number of fields.

Optimizers

metropolisWith

Arguments

:: Hamiltonian	Hamliltonian function
-> StdGen	Random number generator
-> PortalGraph	Graph to optimize
-> Float	Importance of making fields, 0 to 1
-> Int	Maximum number of iterations
-> PortalGraph	Returns the optimized graph

Implement a simple metropolis algorithm for minimizing the hamiltonian of a portal graph

fieldMetropolisWith

Arguments

:: Hamiltonian	Hamliltonian function
-> StdGen	Random number generator
-> PortalGraph	Graph to optimize
-> Float	Importance of making fields, 0 to 1
-> Int	Maximum number of iterations
-> [[Node]]	List of fields
-> PortalGraph	Returns the optimized graph

Implement a simple metropolis algorithm for minimizing the hamiltonian of a portal graph

randomField :: PortalGraph -> StdGen -> [Node]

Generate a random field

perturbGraphFields :: (StdGen, Gr Portal (), [[Node]]) -> (StdGen, PortalGraph, [[Node]])

Create a random modification to a graph, at the level of fielids Pick 3 random nodes If legal, add it to a list of fields in the graph. If illegal, remove a field and repeat

graphFromFields :: PortalGraph -> [[Node]] -> PortalGraph

perturbGraph :: (StdGen, PortalGraph) -> (StdGen, PortalGraph)

Create a random modification to a graph. Pick a link to toggle on or off. Continue toggling links until one of the toggles adds a link. This is because the hamiltonian will nearly always judge removal of a link as a higher energy state.

graphOptimizeWith

Arguments

:: Hamiltonian	Hamiltonian function
-> Float	fieldGain: Importance of making fields, from 0 to 1
-> Int	maxIter: Maximum optimzation iterations
-> PortalGraph	portalGraph: Graph to optimize
-> PortalGraph	Returns optimized graph