Contiguous (USA) State Check

Question

Given a list of States, as in USA States, I am trying to write an algorithm to tell whether or not the States are contiguous. The order does not matter and states can be revisited.

Examples:

AZ, CA, OR, WA are contiguous
AZ, CA, NM, UT are contiguous
AZ, NM, OR, WA are not contiguous

Assumptions:

I have a collection of strings that represent the states.

I have a collection of state connections.

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

This collection has records in both directions:

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

What have I tried?

Attempt 1: For each state in the collection, check that there is at least one StateConnection with another state in the list.

Why it didn't work? This allows the 3rd example, where there are two separate contiguous ranges to pass.

Attempt 2: Remove states from the list of candidate connecting states after they are checked. This will require a complete path that touches every state once.

Why it didn't work? This does not allow the 2nd example, where one state acts as a hub for multiple states.

I haven't solved any graph theory problems in a while, so I'm a bit rusty.

I am not looking to anything like a shortest path or traveling salesman. I don't care what path is taken or how many moves are used. All I care about whether or not there is a gap.

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

score 4 · Answer 1 · edited May 23 '17 at 12:22

4

Have a look at Flood Filling in graph theory. You would want to "paint" each connected node in your tree and then at the end check if any of your states remain unconnected. It doesn't matter how you traverse the graph to do the painting (BFS or DFS) but this would highlight gaps (or unconnected nodes).

edited May 23 '17 at 12:22

Community

1
1

answered Jul 27 '12 at 15:02

John Mitchell

9,653
9
57
91

score 2 · Accepted Answer · answered Jul 27 '12 at 15:04

It sounds like the best solution would be just a breadth-first search through the graph of states. Something like (using the first list as an example):

Create a queue of states to examine. To start, it is empty.
Pick the a state on the list, e.g. CA, add it to the queue.

Then loop as follows:

Dequeue a state from the queue. Mark it off as visisted.
Check whether any of its immediate neighbours (that have not been visited) are on the list. If yes, add them to the queue.
E.g. in case of CA, we found two neightbours on the list: OR and AZ; add them to a queue of next states to examine. Later, when examining OR, we'll see that WA and CA are its neighbours and are on the list; but CA was already visited, so we'll only add WA to the list of states to visit.

Continue until there are no more states to dequeue. If we've visited all states on the initial list by that point, then the list is contiguous. Otherwise it's not.

score 2 · Answer 3 · answered Jul 27 '12 at 15:04

Create a connectivity matrix of the subset of states in question (a N*N boolean matrix that includes a row and a 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).

The 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]);

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

In case you have forgotten what is "that three-loop thing", it's the famous Floyd-Warshall algorithm for finding transitive closures of graphs.

Contiguous (USA) State Check

3 Answers3