Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #=
- 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]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement