Geek Answers Handbook

Continuous (USA) state check

Given the list of states, as in the US states, I am trying to write an algorithm to determine whether states are adjacent. The order does not matter, and conditions can be reviewed.

Examples:

  • AZ, CA, OR, WA are adjacent
  • AZ, CA, NM, UT are adjacent
  • AZ, NM, OR, WA not adjacent

Assumptions:

  • I have a set of strings that represent states.

  • I have a collection of state connections.

     class StateConnection { public string OriginState { get; set; } public string ConnectingState { get; set; } }

This collection has entries in both directions:

  • OriginState = AZ, ConnectingState = CA
  • OriginState = CA, ConnectingState = AZ

What have i tried?

Attempt 1: For each state in the collection, make sure that there is at least one StateConnection with a different state in the list.

Why didn't it work? This allows you to make a third example, in which there are two separate adjacent ranges.

Attempt 2: Remove the states from the list of candidate connection states after checking them. This will require a complete path that affects each state once.

Why didn't it work? This does not allow us to make a second example, when one state acts as a hub for several states.

I did not solve any problems of graph theory after a while, so I'm a little rusty.

I am not looking for anything like the shortest route or the traveling salesman. I don't care which path is taken or how many moves are used. Everything I care about is there a gap.

I am writing this in C #, but feel free to give an answer in other languages.

+4
source share
3 answers

It seems like a better solution would be just a breadth-first search in the state graph. Something like (using the first list as an example):

  • Create a state queue for validation. For starters, it is empty.
  • Select a state from the list, for example. CA , add it to the queue.

Then follow these steps:

  • Cancel state from queue. Mark it as visible.
  • Check to see if there are any of his closest neighbors (who have not been visited) on the list. If so, add them to the queue.
  • eg. in the case of CA we found two lists: OR and AZ ; add them to the following state queue for verification. Later, studying OR , we will see that WA and CA are its neighbors and are in the list; but CA has already been visited, so we will add WA to the list of states to visit.

Continue until there are no more states to deactivate. If we visited all the states in the source list at this point, the list will be contiguous. Otherwise, it is not.

+2
source

Take a look at Flood Filling in graph theory. You would like to “draw” each connected node in your tree, and then at the end check to see if any of your states remain. It doesn’t matter how you go through the graph for drawing (BFS or DFS), but it will highlight spaces (or unrelated nodes).

+4
source

Create a connectivity matrix of a subset of the states under consideration (a N*N Boolean matrix that contains a row and column for each state in the subset, with m[i,j]==true if and only if states i and j are adjacent to each other) .

Run the following algorithm:

 for (int k=0 ; k != N ; k++) for (int i=0 ; i != N ; i++) for (int j=0 ; j != N ; j++) m[i,j] |= (m[i,k] && m[k,j]);

Make sure that all elements m[i,j] set to true after completing three loops. If any element is false , the states are not contiguous.

If you forgot what the “three-loop thing” is, this is the famous Floyd-Warsall algorithm for finding transitive closures of graphs.

+2
source

More articles:


All Articles