Non-backtracking line graph example

#=
Non-backtracking line graph's adjacency matrix and row/column-selecting matrices, based on https://tatsuya.haddow.dev/articles/the-exact-non-backtracking-walk-problem-part-1. You can copy the entire contents of this file into Julia's REPL to set up the definitions in your session.

The adjacency matrix is laid out in alphabetical order of each edge's traversal directions. Based on how the non-backtracking line graph is constructed, an entry in the matrix is 1 if the edge traversal denoted by the row can be followed by the edge traversal denoted by the column, and 0 otherwise. For example, A->B can be followed by B->C, B->E, and B->G, but not B->A as that would be backtracking:

   AB BA BC BE BG CB CD DC DF EB EF FD FE FI GB GH HG HI IF IH
AB 0  0  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
BA 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
BC 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0
BE 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0
BG 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0
CB 0  1  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
CD 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0
DC 0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
DF 0  0  0  0  0  0  0  0  0  0  0  0  1  1  0  0  0  0  0  0
EB 0  1  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
EF 0  0  0  0  0  0  0  0  0  0  0  1  0  1  0  0  0  0  0  0
FD 0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0
FE 0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0
FI 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
GB 0  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
GH 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0
HG 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0
HI 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0
IF 0  0  0  0  0  0  0  0  0  0  0  1  1  0  0  0  0  0  0  0
IH 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0

The row/column-selecting matrices simply selects specific rows from the adjacency matrix. Ones that start with "from_" will choose all rows that start with the given vertex (e.g. from_C chooses CB and CD), and ones that start with "to_" will choose all columns that end with the given vertex (e.g. to_B chooses AB, CB, EB, and GB).

To evaluate non-backtracking walks of length k, raise A_NB to the power of k-1 (see the article for the explanation). From there you can left-multiply by the "from_" matrix and right-multiply by the "to_" matrix to determine walks from/to specific vertices:

julia> # Walk of length 11 from B to D
julia> from_B * A_NB^10 * to_D
4×2 Matrix{Int64}:
 0  0
 0  0
 0  0
 0  1

The resulting matrix is a trimmed-down version of the adjacency matrix, selecting only rows and columns relevant to the chosen vertices. For the example above, it can be understood as:
        end with... C->D F->D
start with... B->A  0    0
              B->C  0    0
              B->E  0    0
              B->G  0    1
=#

A_NB = [0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0; 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0; 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]

from_A = [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
from_B = [0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
from_C = [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
from_D = [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
from_E = [0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
from_F = [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0]
from_G = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
from_H = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
from_I = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]

to_A = [0; 1; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
to_B = [1 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 0; 0 1 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 1 0; 0 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 1; 0 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 0]
to_C = [0 0; 0 0; 1 0; 0 0; 0 0; 0 0; 0 0; 0 1; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0]
to_D = [0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 1 0; 0 0; 0 0; 0 0; 0 0; 0 1; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0]
to_E = [0 0; 0 0; 0 0; 1 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 1; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0]
to_F = [0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 1 0 0; 0 0 0; 0 1 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0 1; 0 0 0]
to_G = [0 0; 0 0; 0 0; 0 0; 1 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 1; 0 0; 0 0; 0 0]
to_H = [0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 1 0; 0 0; 0 0; 0 0; 0 1]
to_I = [0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 0 0; 1 0; 0 0; 0 0; 0 0; 0 1; 0 0; 0 0]