Comparing Two Adjacency Matrices for Graph Equality

I'm currently working on a project that partially involves graphs. One of the problems I'm tackling is determining whether two given matrices represent the same graph.

So given two different adjacency matrices, we want to determine whether they represent the same graph $G$. If they do, the difference is only in the vertex labeling.

For example, consider the V graph:

$$ V_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} $$

If we swap labels $1$ and $2$, the rows change to:

$$ V_2 = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} $$

We can represent any relabeling as a bijective function $f : X \to X$, where $X = \{1, 2, 3,..,n\}$. For V case:

$$ f(1) = 2, \quad f(2) = 1, \quad f(3) = 3 $$

The V graph has three unique matrix representations (i call them instances):

$$ V_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}, \quad V_2 = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}, \quad V_3 = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} $$

Now, consider the instance $I_i$ of graph $G$ and the quantity $S_i$, related to $I_i$:

$$ S_i = \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{j=1}^{n} q_{abj} = \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{j=1}^{n} (e_{aj} + e_{bj} + e_{ja} + e_{jb}) e_{bj} e_{aj} $$

Here, $e_{aj}$ is the element at position $[a][j]$ in matrix $I_i$. Define:

• $\nu_{abj} = e_{bj} e_{aj}$
• $\mu_{abj} = e_{aj} + e_{bj} + e_{ja} + e_{jb}$
• $q_{abj} = \mu_{abj} \nu_{abj}$

These define a 7-tuple:

$$ \vec{q}_{abj} = (e_{aj}, e_{bj}, e_{ja}, e_{jb}, \nu_{abj}, \mu_{abj}, q_{abj}) $$

Now consider another instance $I_p$ of graph $G'$ with corresponding quantity $S_p$:

$$ S_p = \sum_{a'=1}^{n} \sum_{b'=1}^{n} \sum_{j'=1}^{n} q_{a'b'j'} = \sum_{a'=1}^{n} \sum_{b'=1}^{n} \sum_{j'=1}^{n} (e_{a'j'} + e_{b'j'} + e_{j'a'} + e_{j'b'}) e_{b'j'} e_{a'j'} $$

Let the mapping be $f(a) = a'$, $f(b) = b'$, $f(j) = j'$ where $a, b, j, a', b', j' \in X$. Then:

$$ \vec{q}_{f(a)f(b)f(j)} = \vec{q}_{a'b'j'} $$

If $I_p$ and $I_i$ represent the same graph, then:

$$ \vec{q}_{abj} - \vec{q}_{a'b'j'} = \vec{q}_0 = (0, 0, 0, 0, 0, 0, 0) $$

If they do not, then at least one such subtraction will be nonzero

$$ \vec{q}_{abj} - \vec{q}_{a'b'j'} \ne \vec{q}_0 $$

Example: let’s use the V graph, the case where $f(1) = 2$, $f(2) = 1$, $f(3) = 3$.

Then:

$$ q_{123} = (e_{13} + e_{23} + e_{31} + e_{32}) e_{23} e_{13} $$

With:

$$ V_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \Rightarrow \vec{q}_{123} = (0, 1, 0, 1, 0, 2, 0) $$

According to the mapping:

$$ q_{213} = (e_{23} + e_{13} + e_{32} + e_{31}) e_{13} e_{23} $$

With:

$$ V_2 = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} \Rightarrow \vec{q}_{213} = (0, 1, 0, 1, 0, 2, 0) $$

So:

$$ \vec{q}_{123} - \vec{q}_{213} = \vec{q}_0 $$

However, if $V_2$ is changed to $K_3$:

$$ K_3 = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \Rightarrow \vec{q}_{213} = (1, 1, 1, 1, 1, 4, 4) $$

Then:

$$ \vec{q}_{123} - \vec{q}_{213} \ne \vec{q}_0 $$

I've tested it on some challenging cases like Johnson graphs, and it worked, but I haven't tested it on all possible cases. It would be especially helpful if someone could point out any exceptions or edge cases where the algorithm might fail. I can't see any!

The $main$ function

function representSameGraph(inst1, inst2){
    if(inst1.length !== inst2.length){
        return false
    }
    const qs1= getQs(inst1)
    const qs2 = getQs(inst2)
    return compareQs(qs1, qs2)
}

has three stages:

1/ If the instances are not with the same size, then they are not the same (one of them has more vertices)

if(inst1.length !== inst2.length){
   return false
}

2/ Get all $q's$ for the first instance and for the second one, separated on two bulks ($qs1$, $qs2$)

function getQs(AM){
    const qs = []
    for (let a = 0; a < AM.length; a++) {
        for (let b = 0; b < AM.length; b++) {
            for (let j = 0; j < AM.length; j++) {
                const e_aj = AM[a][j]
                const e_bj = AM[b][j]
                const e_ja = AM[j][a]
                const e_jb = AM[j][b]
                const m = (e_aj + e_bj + e_ja + e_jb)
                const q = m*(e_bj*e_aj)
                const v = (e_bj*e_aj)
                const q_v = `${e_aj}${e_bj}${e_ja}${e_jb}${v}${m}${q}`
                qs.push(q_v)
            }
        }
    }
    return qs
}

3/ Comparing $qs1$ and $qs2$

function compareQs(qs1, qs2){ 
    let qs1copy = [...qs1]
    let qs2copy = [...qs2]
    let same = true

    for (let i = 0; i < qs1.length; i++) {
        const j = qs2copy.indexOf(qs1[i])
        if (j > -1){
            qs1copy[i] = "*"
            qs2copy[j] = "*"
        }
        else { 
            same = false
            break
        }
    }
    return same
}

If the two instance represent the same graph, then every $\vec{q}_{abj}$ will exist in $qs2$, which is equivalent to: $\vec{q}_{abj} = \vec{q}_{a'b'j'}$. If $\vec{q}_{abj}$ is found, we indicate that by $*$. At the end, if every $\vec{q}_{abj}$ is found, then $qs1copy = qs2copy = [*,*,*,*, … ,*]$ and $same$ variable will remain $true$. The total complexity of the main function is $O(n^6)$, where $n$ is the length of the instance.