How can I incrementally generate an graph?

Question

I just started a new project in which I'd like the game world to consist of procedurally-generated locations connected by teleporters. After a bit of research, I've discovered this to be called either "graph theory" or "bloody complicated", depending on who is discussing it. Unfortunately, I've found very little information on generating graphs; most of the tools I've seen are directed toward examining existing graphs.

Assuming I have the terminology correctly sorted out, my requirements are that the graph be:

• simple — no location (vertex) should have a teleporter (edge) which connects back to itself, nor should two vertices have multiple edges connecting them
• connected — it should be possible to travel between any two vertices in the graph (though I don't foresee ever needing to find the path; simply knowing the player could find one if they chose to is sufficient)
• cyclic — there should be more than one path between any two vertices
• undirected — all edges can be traveled in either direction
• infinite — if the player so wishes, they should be able to travel indefinitely, with the graph continuing to generate incrementally as they approach its outermost unexplored vertices
• locally finite — a vertex's degree should never change after the player has visited it
• stably labelled — each vertex represents a location which will itself be procedurally generated from a seed; the same seed must be assigned to a vertex regardless of what path the player used to travel there or how large the graph is when they do

I've had some ideas (which I've not yet tried to implement) regarding using the local maxima of 2D perlin noise as vertices (the input x and y could then be used as its label), but that feels clunky and overcomplicated.

Is there a better way to generate a graph like this? I'm developing in Python 2.6 using Panda3D and numpy, and would of course be willing to look at including other libraries if they'll help with this problem!

Edit

I think I've done a poor job explaining some of my requirements, so it's illustration time! Hopefully, this will clear things up.

What I mean by having stable labels is that I want, for example, Player A to be able to do a bunch of exploring and find, among other things, a cyclic path back to their starting location and a mountain that looks like a cat. His game now looks something like the following (vertices are numbered with their seed and edges with the order in which the player traversed them). He started on vertex 8329 (green) and Happycat Mountain is in vertex 6745 (blue).

Player A's good friend Player B is a fan of cats, so he wants to show it to her. He gives her the root seed for his world and directions along the shorter route to the mountain of interest. Her game should now look like this:

The problem I'm currently having the most difficulty with is "How do I generate the same seeds for Player B when her exploration hasn't followed the same path?" That's what led me to the idea of using Perlin noise — as long as the same root seed is used, the maxima won't move, so their coordinates could be used as stable vertex seeds.

Answer 1

You can't make an infinite graph. Your memory is finite, thus the numbers of vertices and edges are also finite. What you can do is make a finite graph then add more to it. You seem to have realized this but I think it is important it be explicitly stated so you don't go down a dead end path.

You must be very careful when talking about "outermost vertices". A graph is a set of vertices, a set of edges, and a function that relates the two. There is no set geometric interpretation unless you apply one. For example: both of these pictures show the exact same graph. In the first image, vertex 2 could be considered an "outermost" vertex, yet in the second image vertex 2 would not be considered "outermost". If you considered three dimensions, you could say all vertices are "outermost".

This means you must have some other information for you to be able to know what an "outermost" vertex is. You could use (x,y) pairs as that would give you an easy to visualize geometric representation, however I don't think you need to go that far. From what you say, all you need to know is what vertices are in the graph already.

If you ran this every time you visited a vertex:

if(this.needsNeighbours)
{
    List<int> connections = genRandomNumbers(n);
    foreach (int connection in connections)
    {
        //Simple graph
        if(connection == this.seed || this.hasNeighbour(connection))
        {
            continue;
        }
        //Connections to already existing, unvisited vertices
        else if(nodeMap.containsKey(connection) && 
                nodeMap.getByKey(connection).needsNeighbours)
        {
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
        //Grow graph with new vertices
        else
        {
            nodeMap.add(connection, new Node(connection));
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
    }
    this.needsNeighbours = false;
}

your graph would satisfy all your requirements except for being cyclic. I don't know if you actually need a guarantee. If you do then you could specifically select an unvisited node and make a connection, that would guarantee a path between the current node and an already visited node as all unvisited nodes are connected to at least one visited node and since you had to have visited a visited node to get where you are there are now at least two paths.

It is simple because there is an explicit check for it, connected because all new nodes get at least one connection, locally finite because edges are only added before you visit or on your first visit, and only to unvisited nodes. Technically its not undirected, but functionally it is the same as you create a directional edge in both directions. You can label the node anything you want, I use the random number generated, but you could add other parameters to the constructor, one being your seed.

Answer 2

One method:

init:
  root = generateLocation using random seed
  store root's seed
  place player in root location

when the player enters a new location:
  release the memory used by locations that are further than 1 edge away, but keep their seeds
  generate some neighbors for the new location. for every neighbor n:
    gen.seed(getSeed(n))
    n = generateLocation using n's random seed
    numCyclicEdges = gen.randint(0, 1)
    create numCycleEdges edges to existing locations

getSeed(n):
  if(n already has a seed) return n's seed
  else return randomSeed()

There are lots of details I left out, but this should capture the general idea. You may want to keep neighbors in memory that are more edges away from the current location, depending on how much world-distance there is between portals, much available memory there is, etc.