Can this graph search be optimized?

Question

I have the following which searches my graph to see if a vertex is reachable from the first vertex, which everything should be connected to. I do this to ensure there are no disconnected parts.

Unfortunately it is very slow.

Is there something I could do or store to optimize this?

I want to learn about graphs and generated cities so Im not using a real graph library.

private void removeDisconnectedSquares()
{
 for(int i = 0; i < getNumXNodes(); ++i)
 {
 for(int j = 0; j < getNumYNodes(); ++j)
 {
 //removeDisconnectedSquare(i, j);
 visitedNodes.clear();
 if(!isNodeReachableFrom(getNodeAt(i, j), getNodeAt(0, 0)))
 {
 removeVertex(i, j);
 }
 }
 }
}
private boolean isNodeReachableFrom(GraphNode node, GraphNode target)
{
 if(node == null)
 {
 return false;
 }
 if(visitedNodes.contains(node))
 {
 return false;
 }
 else
 {
 visitedNodes.add(node);
 }
 if(node == target)
 {
 return true;
 }
 if(node.contains(target))
 {
 return true;
 }
 for(int i = 0; i < node.getSize(); ++i)
 {
 if(isNodeReachableFrom(node.at(i), target))
 {
 return true;
 }
 }
 return false;
}

Answer 1

Rather than using recursion (which is pretty slow), you can for this using a Set of all reachable nodes, and a Queue of nodes you still haven't searched. This is a basic implementation of Breadth-First Search.

private boolean isNodeReachableFrom(GraphNode start, GraphNode target) {
 // These are GraphNodes who's connected GraphNodes we haven't looked at yet.
 // Maybe the target is connected to one of these!
 Queue nodesToSearch = new LinkedList<GraphNode>();
 nodesToSearch.add(start);
 // These are GraphsNodes which we have proved are reachable from the given node.
 // If we are ever about to add the given target to this list, we return true.
 Set reachableNodes = new HashSet<GraphNode>();
 // As long as there are still nodesToSearch, we could still find our target.
 while (nodesToSearch.peek() != null) {
 GraphNode node = nodesToSearch.remove();
 // If we have already seen this node, we don't want to look at its connected
 // nodes again, because we could get stuck in a cycle.
 boolean isNewNode = reachableNodes.add(node);
 // If this is a new node, see if the target is connected. If it is, we are
 // done successfully. Otherwise, add all of the connected nodes to our
 // list of nodesToSearch.
 if (isNewNode) {
 for (GraphNode connectedNode : getConnectedNodes(node)) {
 if (connetedNode.equals(target)) {
 return true;
 }
 nodesToSearch.add(connectedNode);
 }
 }
 }
 // There are no nodes we haven't searched, so the target is not reachable.
 return false;
}

Note: I made up getConnectedNodes(node) because your code didn't show me how to do this with the GraphNode object.

Note that this is an implementation of isNodeReachableFrom. However, you seem to want to figure out the list of nodes which aren't reachable from a starting node. Notice that we build up the list of all reachableNodes in the call above, which is probably what you really want. You could write a function to return that reachableNodes structure, which would reuse the above logic without the target sections. Something like this:

public Set<GraphNode> getReachableNodes(GraphNode start) { ... }