## Some Tools You May Need For P.I.

Planetary interaction is coming, and needless to say I’m frigging pumped to planet spin! Some of you may not feel the same way, but I know for a fact most of you will at-least Try P.I. Its another thing to do, to profit from, and to master. In eve online, mastering something is all about optimization. Weather your an Industrialist working to make the most profit from the least amount of “stuff” or a Combat pilot finagling your fit to push out the most tank and dps your ship will allow, you are optimizing. I have a feeling that this will stay constant in PI. If you want to know how to optimize ANYTHING you talk to a computer scientist, lucky for you, I am one. From what I have seen of PI, it will consist of points, connected by routes. You show that to a computer scientist, chances are they will say “HEY thats a directed Graph!!!” and what do you know, we study graph theory.

Although I don’t know for sure if they will be of use, I’m pretty certain that these four algorithms will help you optimize your planetary networks, and they are something that you should at least familiarize your self with.

**Some Terms To Know**

**Tree**– An acyclic graph contained within a graph.**Acyclic –**The only way back to a point you are coming from is to backtrack the same path you took to get there.

The first two algorithms are for finding the “minimum spanning tree.” In simple terms, they find the tree within a graph that will hit all points, with the least amount of distance overall.

**PRIMS ALGORITHM**

Complements of the fabled Wikipedia….

**Kruskals Algorithm** –

Another minimum spanning tree algorithm, and once again this table is complements of wikipedia.

** **

Next we have an algorithm to solve the **Shortest Path Tree – **This is a tree that is created from a single point, and it connects all other points to it in the shortest way possible.

**Dijkstra’s Algorithm – **

**Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step-by-step.**

- Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
- Mark all nodes as unvisited. Set initial node as current.
- For current node, consider all its unvisited neighbors and calculate their distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
- When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
- If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next “current node” and continue from step 3.

Here is a image demonstrating Dijkstras

Now for my last and final algorithm we have one to solve the problem of **Maximum Flow**. Its called several different things, but for low lets just call it the augmenting path algorithm. This solves how to get the maximum amount of Stuff from one point to another, while visiting all points, with constraints on the amount of “Stuff that can flow through the tubes.” This diagram is somewhat self explanatory, although a few things are worth noting. the #,#+ or #,#- may seem a bit odd. The first number represents the amount of additional flow that can be brought from the source to that vertex. The second number is the name of the vertex that flows into the one being labeled. If this seems a bit unclear, spend a bit looking at the process worked out and see if you can get a feeling for it.

Well I hope this helps in some way, or at the very least introduced you to the wild and exciting world of graph theory. Although some of these concepts may be a bit fuzzy to you, with a bit of practice and some critical thinking, you may be able to use them to set up your P.I. colonies for maximum efficiency. If you need anything explained in more detail, or just cleared up in general feel free to leave a comment and I will get back to you as quickly as I can,

(p.s Watch this space, there may be a colony lay-0ut optimizer program in the works once Tyrannis is released)

April 27, 2010 at 2:17 am

This blog post makes me giddy-happy that I have a kindred geek spirit out there.

Though I haven’t started to research the PI mechanics yet, so I don’t yet know what graph optimization has to do with production efficiency… >.>

April 27, 2010 at 8:38 am

The Problem that comes closer to the one found in PI is the Steiner Tree Problem.

http://en.wikipedia.org/wiki/Steiner_tree_problem

May 16, 2010 at 8:50 pm

hello

i’m so happy that i saw this page. that article was so helpful. thanks again i saved this site.

are you planning to write similar posts?

June 15, 2010 at 3:45 pm

[…] Faint Resolution’s PI Directed Graphs Algorithm […]