# Find sub-graphs in a graph

The initial problem I'm trying to solve is for pac-man, but of course there must be thousands of other situations with the same problem. I consider the pac-man grid to be a graph (two ways of doing this: either each grid square is a vertex, OR each "intersection" is a vertex and the "hallways" are the edges), and try to find a path that eats all the food (not worrying about ghosts for the moment).

I've noticed that certain grids can be clearly separated into sub-grids, where there is a single bottleneck that must be crossed in order to get into/out of the sub-grid. This of course translates into being able to partition the graph into two sub-graphs that share a single node and no edges.

What algorithms exist for finding these sorts of sub-graphs (that are "pinched off" from the rest of the graph by a single vertex)? I'm looking for a quick run-down of what's out there, as a starting point for further research.

-

Keeping things simple

I don't know the exact context of your problem, but I give below the most accurate solution possible given the specific question you've asked. However, if you want to keep things simple, it is better to construct the graph yourself. In that way, there is no need for you to identify subgraphs, since in creating them within a larger planar surface (the bounds of the maze) and inserting them into that "template" supergraph, you already know what the subgraphs are... similar to how Diablo builds its levels. The only (minor) problem there is that you are using a planar grid, so you would need to be sure that the supergraph can accommodate each subgraph as you place it, and that they connect door-to-door.

You need to look into toplogical graph minors, graph isomorphism, and how to find Hamiltonian cycles, since cycles are, in fact, the sub-graphs you are seeking (see explanation below). The basic problem of cycle detection is not too hard, but is costly to calculate, O(n^2). These links should indicate to you the basis of intelligently identifying the subgraphs you mention. However see my long answer for more detail, because graph theory is quite demanding.

I think you are oversimplifying and/or underspecifying the problem.

Consider any graph that is:

1. Homogenous, i.e. its nodes and edges are equal in every sense, no weighting for instance;
2. Acyclic, i.e. a tree.
3. Purely topological. (I like to think of topology-only graphs as bits of snapped elastic band connected together in a certain way. It has variable embeddings and/or directedness, depending on how you hold it up, and the lengths of individual sections are variable -- it's the sequences of connections that is important.)

With such a graph, I think you will see that it becomes impossible to identify subgraphs easily without much more specific criteria than you've given; an example might be, "seek subgraphs in v where at least one edge connects to a leaf node".

One factor that tends to make subgraphs identifiable (i.e. the clumping you see) to the human mind, is cycles. (Another factor is branches on a treelike structure, but only if the embedding can be recognised visually, as being treelike.) For instance, this maze is (ambiguously) acyclic, and you will notice no real clumping here, except for at the top right:

....If considered as a pure grid, then the area beneath the entrance at the top right would be considered a cycle of 4 vertices (grid cells); but if you considered the maze in a purely topological sense, you might consider that to be a simple dead end, and thus non-cyclic. Already, you may be beginning to see how your identification and elimination process must work.

...In Pacman, it immediately becomes clear where you are seeing subgraphs -- and there are a great many of them. In fact it's much like the IQ questions where you are asked, "How many triangles are there in this picture?"

So, algorithm? Through a conservative edge-reduction approach on a planar, 4-connected 2D grid, one quickly ends up with a graph like Pacman's, containing cycles. Cycles, or clumps of cycles (since a cycle may contain subcycles) are the "sub-grids" which you mention, connected by bottlenecks or chokepoints, depending on your chosen terminology. We first identify these cycles, then reduce them down to a single vertex which acts as a placeholder. Rinse, repeat. What this then gives you is a "skeleton" graph where each cyclic minor is reduced down to a single derived vertex. (Please see diagrams here, I cannot link SVG) However, because you may now have long chains of 2-connected vertices, you can take this a step further, by eliminating redundant vertices and edges in the resultant chains, resulting in the complete toplogical minor (or in layman's terms, essential connective/structural essence) of your original supergraph. This basically tightens up the "pinch points"you mention. Whether you will need this additional step or not, depends on what you are trying to achieve.

The wikipedia link diagrams the two-step process I outline above, using the dotted lines to show cycle-removal, and grey lines to show redundant edge removal. It also dips a toe into discussion of algorithm to find minors, but bear in mind as you read that: From what I understand of your problem, you will wish to seek and eliminate/excise any cyclic minors within your supergraph, which is a far simpler problem than looking for more specific subgraphs in a given supergraph, such as seeking non-planar Kuratowski subgraphs to ensure graph planarity, the latter being something you will never have to attempt if you start with a maximally connected 2D grid and simply reduce from there.

-
Oh, here we go... can someone kindly un-make this community wiki? Would be much appreciated after all the effort. –  Arcane Engineer Dec 13 '11 at 12:58
Wow - that's a lot to look at, and I'll definitely check it out. However, a fairly small amount of digging landed me on the wiki article for "articulation vertex", which claims that the biconnected components of a graph can be found in linear time. How does this fit in with the rest of your response? –  Kelsey Rider Dec 13 '11 at 13:28
I would say articulation vertices (which I knew previously as "cutpoints") are probably a more efficient approach. Mine is more generalised and would be more useful in assisting manipulation of the level by subgraph, as opposed to simple identification which I think you want. This looks like a good source for that. It really works along the same general principle; any graph search is one of walking and marking those nodes walked, in applicable ways according to the problem at hand. Instead of seeking cycles, it directly seeks cutpoints. –  Arcane Engineer Dec 13 '11 at 13:39