Collecting all nodes within reach

I've got an array of interconnected nodes which looks like this.



The representation I have of these nodes in PHP looks like this. Where each node has a key in the array, which is associated with an array of connected node keys.



What I would like to do, is given a key K for a starting point SP, and a number N for the maximum "jumps", return an array of K which are within N jumps from SP.

Currently I'm using the following, which basically counts down from N and merges anything connected to the K already in the result array until N is zero.



It returns results. For 1 jump it returns the expected nodes. However it's a tad daunting to verify whether it returns the correct results for more than 1 jump because the results grow pretty fast. Off the top of my head, I can also tell I should optimize this in some way so that each iteration of the while loop doesn't continually re-check past nodes.

Any and all [constructive] input is welcome. If you're wondering what this is for, the data set I'm using is the "mapSolarSystemJumps" table from Eve Online's database dump.

I switched to the following loops. The earlier code timed out after 30 seconds with $maxJumps set to 20, whereas this new code finds about 1200 nodes within reach of 20 jumps in 1 second tops. (including the time it takes to build the page and my browser to render it)

Graph problems like this are a lot easier if you work within traditional graph theory, that is, labeling both vertices and edges. Then associating each vertex with its neighbors and finding paths, walks, and loops becomes much simpler.

You went right over my head with that answer. Can you show me a quick example of what you mean by labeling vertices and edges ?

Sure:

A vertex (plural: vertices) is a point in a graph. The lines connecting them are called edges. If you were to give a unique identifier to all vertices (i.e. v1, v2, etc.) and to all edges (i.e. e1, e2, etc.), then you can model the graph as a collection of vertices, each containing a collection of edges.



In the example above, we have a graph containing 5 vertices and 5 edges. We can give each vertex a collection of edges. We use the notation E(vi) to say "the collection of edges having "vi" as an endpoint:



Now, to find all nodes that are a certain number of jumps away, we just take the starting node, iterate through it's list of edges to grab the neighbors of the vertex, and repeat until we're far enough out.

The real benefit of this can be seen if you program this in an object-oriented fashion, where vertices and edges are all objects.

Of course, if you're into matrix algebra, you can run even crazier algorithms on the adjacency matrix of the graph to obtain even more information.

At the moment the only two results I need from this data are the set I'm working on now, being the set which tells me the systems which are within N jumps of any given system, and the shortest path between two systems, which I already have working.

Here are the tables I have to work with. The table I work with primarily is the mapSolarSystemJumps table, which has 14,334 rows.

EVE, nice, I'm trying to quit, quite an addiction. Are you aware of this? http://www.eve-icsc.com/jumptools/jumpplanner.php Or are you trying to make something like it?

I'm not in anything that uses jump drives, I have to play connect the dots with jump gates.

I do a bit of trading. I like to buy stuff in other regions through contracts so sometimes I need to know the shortest route from a solar system to any one of that regions entry point systems in order to bid on the contract. So I pull all of the entrypoint systems in that region and calculate the shortest path to all of them before returning the shortest path.

I plan on using the thing I started this thread for to find systems close to high priced buy orders. I'm constantly buying minerals priced below market value in systems out in the middle of nowhere for cheap because some miner doesn't want to haul them to a market hub and waiting for someone to want them at a premium either in that system, or a system within N jumps some time later.

Yeah I've actually done that a lot. It looks like this guy tried to accomplish something similar, but it looks like a failure... http://games.chruker.dk/eve_online/shor ... region.php (BTW, the rest of his site is an amazing resource)

I hope you don't waste too much time on this man, because there are a lot of resources out there that you can make due with. Once you get to know the game more, you'll start just knowing which routes are shortest and get to know places. There's only so many high sec routes in and out of regions, especially the further out they are. Those are usually the best isk makers too for that kind of trading. Check this map out, I love it: http://www.ombeve.co.uk/

Damn this doesn't help me, I'm still trying to quit.

Yeah I've seen that first link. I believe it works if you're ingame and give the site trust so it receives HTTP request headers with your current location.

I'm a bit paranoid about using tools that can give away my planned location or tip off the author to my activities.

My "shortest path to region" is two textboxes and a submit button. The first textbox is autofilled with my current system, the second is pretty good about interpreting what I mean if I type in "sink liazon" it will use SOUNDEX() to figure out I meant "Sinq Liason". It utilizes the IGB javascript API to set destinations. Tells me how many jump gates are in each system in the route so I know to keep a lookout for gatecamps in corridors. I add other information as needed, for instance I'll probably add a station count sooner or later.