Ingraph is a tool for determining the best way to link portals together in the game Ingress. Briefly, portals exist at various coordinates on a map, and these portals can be linked together. Linking three portals together to form a triangle creates a field.
Links and fields are worth a certain number of points (AP) to create, and a different number of points to destroy. One way to optimize links is to maximize points due to creation while minimizing points due to destruction.
I thought, it should be possible to write a little program that does this optimization and tells you what portals to link together. One could even do the optimization in a fun physics-y way. So that's what you find here.
Using the metric described above, specifically the ratio of creation AP to destruction AP, this tool decides which portal links will give you the best result. It also takes into account how badly you'd like to make fields, but for those details see Algorithm below. Since that initial idea, I've added several other optimization functions, which you can choose between.
I should also note that in terms of actual game-play, this optimization probably has no useful effect, or an effect that's too small to notice. But it was a fun exercise!
Screenshots
0.9
0.5
Downloads
Source 
To compile sources, unpack the source archive and from the unpacked directory run cabal configure and cabal build. That should also pull in any dependencies ingraph needs. Note that wxWidgets libraries must be available for wxhaskell to be installed. One can optionally also run cabal install to copy files to system directories.
Binaries
These are provided for convenience, but I haven't been able to test on many platforms. They work for me, but I don't know how they'll do with your setup. Building from source is always best if you can manage. If you have problems with these, or have other binaries you'd like to contribute, please email me at stepp@atistar.net.
 |
ingraph-0.10 (64 Bit, wxWidgets 2.8.12, GHC 7.6.2) |
| ingraph-0.5 (64 Bit, wxWidgets 2.8.12, GHC 7.6.2) | |
 |
ingraph-0.10 (64 Bit, only tested on Windows XP) |
| ingraph-0.3.1 (64 Bit, only tested on Windows XP) |
Documentation
Documentation for the source is available here.
Algorithm
The graph optimzation algorithm is loosely based on an Ising model, in which links on the graph are either present or not. There is the additional restriction that links may not cross. A Hamiltonian energy function is computed for a graph, and is minimized using a simple version of the Metropoplis algorithm.
The AP Ratio Hamiltonian is given by
\[
E = \sum_i \frac{187 L_i+750 F_i}{313 L_i+1250 F_i} \frac{1}{1-G+G \tanh{\left(1+F_i\right)}}
\]
where for each portal $i$, $L_i$ is the number of links connected to the portal and $F_i$ is the number of fields adjacent to the portal. The gain parameter $G$ conveys how desirable fields should be considered.
A small modification is made to the usual Metropolis algorithm. When perturbing a graph, a link is either added or removed. If a link is removed, the hamiltonian almost always goes up, meaning that links tend to be added until no free links are possible. Essentially each optimization quickly finds a local minimum.
In order to avoid this situation, graph perturbations are repeated until a link is added. This way, it's possible to remove several links so that a better link can be attempted.
Other Hamiltonians
- Link Defense:
- Goal: Best defense due to links for each portal \[ E = -\sum_i { \tfrac{4}{9} \arctan{ \left( \frac{L_i}{e} \right) } } \]
- Global Links:
- Goal: Most links between any portals \[ E = -\sum_i L_i \]
- Equal Links:
- Goal: Link so that each portal has the same number of links \[ \bar{L} = \frac{1}{n}\sum_i^n L_i\\ s^2 = \frac{\sum_i^n \left( L_i - \bar{L} \right)^2}{n-1}\\ E = \frac{1+s^2}{\sum_i^n L_i} \]
- AP:
- Goal: Total AP to link and field \[ E = -\left( 313 L + 1250 F \right) \] where $L$ and $F$ are the total number of links and fields, respectively.
- "Save Flynn" Event:
-
This is an example of a very specific hamiltonian. The Save Flynn Event was scored according to a set of rules. One point for each portal, 5 points for each link, and 10 points for each field.