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….

Image	Description
	This is our original weighted graph. The numbers near the edges indicate their weight.
	Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
	The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the arc DF.
	The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
	In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away from B, and G is 11 away from F. E is nearest, so we highlight the vertex E and the arc BE.
	Here, the only vertices available are C and G. C is 5 away from E, and G is 9 away from E. C is chosen, so it is highlighted along with the arc EC.
	Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight it and the arc EG.
	Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

Kruskals Algorithm –

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

Image	Description
	This is our original graph. The numbers near the arcs indicate their weight. None of the arcs are highlighted.
	AD and CE are the shortest arcs, with length 5, and AD has been arbitrarily chosen, so it is highlighted.
	CE is now the shortest arc that does not form a cycle, with length 5, so it is highlighted as the second arc.
	The next arc, DF with length 6, is highlighted using much the same method.
	The next-shortest arcs are AB and BE, both with length 7. AB is chosen arbitrarily, and is highlighted. The arc BD has been highlighted in red, because there already exists a path (in green) between B and D, so it would form a cycle (ABD) if it were chosen.
	The process continues to highlight the next-smallest arc, BE with length 7. Many more arcs are highlighted in red at this stage: BC because it would form the loop BCE, DE because it would form the loop DEBA, and FE because it would form FEBAD.
	Finally, the process finishes with the arc EG of length 9, and the minimum spanning tree is found.

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.

1. Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
2. Mark all nodes as unvisited. Set initial node as current.
3. 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.
4. 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.
5. 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)