How to compute adjacency matrix of people seating next to each other in a stadium?

Question

Consider an $|R| \times |S|$ matrix where $S$ and $R$ are sets of seat numbers and row names, respectively, for seats at a stadium. Not all seats are occupied by people. Entry $(r, s)$ of the matrix equals one when a person is siting at seat $s$ on row $r$, and zero otherwise. I want to compute the adjacency matrix of people seating next to each other at the stadium. What algorithm can I use?

Example Matrix:

        row_name
seat_num A B C D E F G K L M N O
      1  0 0 0 1 0 0 0 0 0 0 1 0
      2  0 0 0 0 0 0 0 0 0 0 1 0
      3  0 0 0 0 0 0 1 0 0 0 0 0
      5  1 0 0 0 0 0 1 0 0 0 0 0
      6  0 0 1 0 0 0 0 0 0 0 0 0
      7  1 0 0 0 0 0 1 0 0 0 0 0
      8  1 0 0 0 0 0 0 0 0 0 0 0
     10  0 0 0 1 0 0 0 0 0 0 0 0

Answer 1

Naive approach. Let $T$ be the total number of seats at the stadium.

1. Create an $T \times T$ matrix with all zeroes; call it $A$.
2. Stablish a bijection between all the $(r, s)$ pairs and the numbers $\{1, 2, 3, \ldots, T\}$. The former will serve as indeces for the entries of $A$.
3. Iterate over all seats $(r, s)$ at the stadium.
   • If seat $(r, s)$ isn't empty, then do the following:
     1. Compute index $i$ for seat $(r, s)$.
     2. Iterate over the neighbouring seats $(m, n)$ of $(r, s)$.
        • If seat $(m, n)$ isn't empty, then: compute index $j$ for seat $(m, n)$, and assign $A(i,j) = 1$.

Of course, this algorithm could use some improvements, as leting $A(j,i) = A(i,j) = 1$ in the innermost step, since $A$ is symmetric; but then we will need a way to avoid comparing neighbouring non-empty seats twice.

Slightly improved approach. Assume the row names and seat numbers are just successive integers starting at $1$ (and that matrix indexing also starts at $1$), for simplicity; then the bijection $(r, s) \mapsto (r-1)|S| +s$ represents an inherent left-to-right, top-to-bottom ordering of the seat. Iterating over all seats $(r, s)$ in this fashion (third outermost step above), allows revisions over "neighbouring seats $(m, n)$" to be simplified as over "forward neighbouring seats $(m, n)$" only, then leting $A(j,i) = A(i,j) = 1$ in the innermost step.