Method of determining graph isomorphism in polynomial-time

• US 20070179760A1
• Filed: 01/06/2006
• Published: 08/02/2007
• Est. Priority Date: 01/06/2006
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Smith, Joshua
• Application Number:
  US11/326,971
• Publication Number:
  US 20070179760A1
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]

Abstract

Generating a complete graph invariant may be accomplished by initializing each card of an initial message deck to an identity matrix, propagating messages to form a first iteration message deck using a message propagation rule, generating a first iteration codebook using the first iteration message deck, recoding the first iteration message deck using the first iteration codebook, repeating the propagating, generating, and recoding steps for at least a second iteration, concatenating the message decks elementwise to form a final message deck, row sorting the final message deck to form a row sorted message deck, sorting rows of the row sorted message deck to form a table sorted message deck, and sorting cards of the table sorted message deck to form the invariant.

Claims

1. A computer-implemented method of generating a complete invariant for a graph comprising:

initializing each card of an initial message deck to an identity matrix;

propagating messages to form a first iteration message deck using a message propagation rule;

generating a first iteration codebook using the first iteration message deck;

recoding the first iteration message deck using the first iteration codebook;

repeating the propagating, generating, and recoding steps for at least a second iteration;

concatenating the message decks elementwise to form a final message deck;

row sorting the final message deck to form a row sorted message deck;

sorting rows of the row sorted message deck to form a table sorted message deck; and

sorting cards of the table sorted message deck to form the invariant.

2. The computer-implemented method of claim 1, wherein each message deck comprises an array of cards, each card comprises a two dimensional array of strings, the invariant comprises a three dimensional array of strings, and the length of each array comprises the number of vertices in the graph.

3. The computer-implemented method of claim 1, wherein the message propagation rule used to form the first iteration message deck uses an adjacency matrix corresponding to the graph.

4. The computer-implemented method of claim 3, wherein the message propagation rule is:

${\underset{\_}{U}}_{\mathrm{mij}}^{z+1}<br><br>\left(A\right)=\left(\left(U_{\mathrm{mim}}^z,A_{\mathrm{mj}}\right),\underset{k=\left\{1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>n\right\}<br><br>\backslash <br><br>m}{\bigcup <br><br>}<br><br>\left\{\left(U_{\mathrm{mik}}^z,A_{\mathrm{kj}}\right)\right\}\right)$

where U^z is the message deck at iteration z, A is the adjacency matrix, n is the number of vertices in the graph, and m, i, and j are indices of the three dimensions of the message deck.

5. The computer-implemented method of claim 1, wherein generating a codebook comprises computing:

${\hat{U}}^z=\underset{m=1}{\overset{n}{\bigcup <br><br>}}<br><br>\underset{i=1}{\overset{n}{\bigcup <br><br>}}<br><br>\underset{j=1}{\overset{n}{\bigcup <br><br>}}<br><br>{\underset{\_}{U}}_{\mathrm{mij}}^z$

where Û

^z is the codebook at iteration z, n is the number of vertices in the graph, and m, i, and j are indices of the three dimensions of the message deck at iteration z.

6. The computer-implemented method of claim 1, wherein row sorting the final message deck comprises computing:

$R_{\mathrm{mi}}<br><br>\left(A\right)=U_{\mathrm{mim}}<br><br>\left(A\right)<br><br>U_{\mathrm{mii}}<br><br>\left(A\right)<br><br>\underset{j=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>\left\{i,m\right\}}{\bigcup <br><br>}<br><br>U_{\mathrm{mij}}<br><br>\left(A\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\ne <br><br>m\right)$ $R_{\mathrm{mm}}<br><br>\left(A\right)=U_{\mathrm{mmm}}<br><br>\left(A\right)<br><br>\underset{j=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>m}{\bigcup <br><br>}<br><br>U_{\mathrm{mmj}}<br><br>\left(A\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i.e.\text{\hspace{1em}<br><br>}<br><br>i=m\right)$

where R is the row sorted message deck, U is the final message deck, A is the adjacency matrix for the graph, n is the number of vertices in the graph, and m, i, and j are indices of the three dimensions of the final message deck.

7. The computer-implemented method of claim 1, wherein sorting rows of the row sorted message deck comprises computing:

$T_m<br><br>\left(A\right)=R_{\mathrm{mm}}<br><br>\left(A\right)<br><br>\underset{i=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>m}{\bigcup <br><br>}<br><br>\left\{R_{\mathrm{mi}}<br><br>\left(A\right)\right\}$

where T is the table sorted message deck, R is the row sorted message deck, A is the adjacency matrix for the graph, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the row sorted message deck.

8. The computer-implemented method of claim 1, wherein sorting cards of the table sorted message deck comprises computing:

$V<br><br>\left(A\right)=\underset{m=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}}{\bigcup <br><br>}<br><br>\left\{T_m<br><br>\left(A\right)\right\}$

where V is the invariant, A is the adjacency matrix for the graph, T is the table sorted message deck, n is the number of vertices in the graph, and m is an index of the cards of the table sorted message deck.

9. The computer-implemented method of claim 3, further comprising storing the invariant and the adjacency matrix in as an ordered pair.

10. An article comprising:

a machine accessible medium containing instructions;

which when executed, result in generating a complete invariant for a graph by

initializing each card of an initial message deck to an identity matrix;

propagating messages to form a first iteration message deck using a message propagation rule;

generating a first iteration codebook using the first iteration message deck;

recoding the first iteration message deck using the first iteration codebook;

repeating the propagating, generating, and recoding steps for at least a second iteration;

concatenating the message decks elementwise to form a final message deck;

row sorting the final message deck to form a row sorted message deck;

sorting rows of the row sorted message deck to form a table sorted message deck; and

sorting cards of the table sorted message deck to form the invariant.

11. The article of claim 10, wherein each message deck comprises an array of cards, each card comprises a two dimensional array of strings, the invariant comprises a three dimensional array of strings, and the length of each array comprises the number of vertices in the graph.

12. The article of claim 10, wherein the message propagation rule used to form the first iteration message deck uses an adjacency matrix corresponding to the graph.

13. The article of claim 12, wherein the message propagation rule is:

${\underset{\_}{U}}_{\mathrm{mij}}^{z+1}<br><br>\left(A\right)=\left(\left(U_{\mathrm{mim}}^z,A_{\mathrm{mj}}\right),\underset{k=\left\{1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>n\right\}<br><br>\backslash <br><br>m<br><br>\text{\hspace{1em}<br><br>}}{\bigcup <br><br>}<br><br>\left\{\left(U_{\mathrm{mik}}^z,A_{\mathrm{kj}}\right)\right\}\right)$

where U^z is the message deck at iteration z, A is the adjacency matrix, n is the number of vertices in the graph, and m, i, and j are indices of the three dimensions of the message deck.

14. The article of claim 10, wherein instructions to generate a codebook comprise instructions to compute:

${\hat{U}}^z=\underset{m=1}{\overset{n}{\bigcup <br><br>}}<br><br>\underset{i=1}{\overset{n}{\bigcup <br><br>}}<br><br>\underset{j=1}{\overset{n}{\bigcup <br><br>}}<br><br>{\underset{\_}{U}}_{\mathrm{mij}}^z$

where Û

^z is the codebook at iteration z, n is the number of vertices in the graph, and m, i, and j are indices of the three dimensions of the message deck at iteration z.

15. The article of claim 10, wherein instructions to row sort the final message deck comprise instructions to compute:

$R_{\mathrm{mi}}<br><br>\left(A\right)=U_{\mathrm{mim}}<br><br>\left(A\right)<br><br>U_{\mathrm{mii}}<br><br>\left(A\right)<br><br>\underset{j=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>\left\{i,m\right\}}{\bigcup <br><br>}<br><br>U_{\mathrm{mij}}<br><br>\left(A\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\ne <br><br>m\right)$ $R_{\mathrm{mm}}<br><br>\left(A\right)=U_{\mathrm{mmm}}<br><br>\left(A\right)<br><br>\underset{j=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>m}{\bigcup <br><br>}<br><br>U_{\mathrm{mmj}}<br><br>\left(A\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i.e.\text{\hspace{1em}<br><br>}<br><br>i=m\right)$

where R is the row sorted message deck, U is the final message deck, A is the adjacency matrix for the graph, n is the number of vertices in the graph, and m, i, and j are indices of the three dimensions of the final message deck.

16. The article of claim 10, wherein instructions to sort rows of the row sorted message deck comprise instructions to compute:

$T_m<br><br>\left(A\right)=R_{\mathrm{mm}}<br><br>\left(A\right)<br><br>\underset{j=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>m}{\bigcup <br><br>}<br><br>\left\{R_{\mathrm{mi}}<br><br>\left(A\right)\right\}$

where T is the table sorted message deck, R is the row sorted message deck, A is the adjacency matrix for the graph, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the row sorted message deck.

17. The article of claim 10, wherein instructions to sort cards of the table sorted message deck comprise instructions to compute:

$V<br><br>\left(A\right)=\underset{m=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}}{\bigcup <br><br>}<br><br>\left\{T_m<br><br>\left(A\right)\right\}$

where V is the invariant, A is the adjacency matrix for the graph, T is the table sorted message deck, n is the number of vertices in the graph, and m is an index of the cards of the table sorted message deck.

18. A system for testing isomorphism of two graphs comprising:

an invariant generation module to accept an adjacency matrix for each graph and produce an invariant for each graph; and

an invariant comparison module coupled to the invariant generation module to accept the invariants, to compare the invariants, and to produce an isomorphism indicator;

wherein the invariant generation module is adapted to perform the following for each graph

initialize each card of an initial message deck to an identity matrix;

propagate messages to form a first iteration message deck using a message propagation rule;

generate a first iteration codebook using the first iteration message deck;

recode the first iteration message deck using the first iteration codebook;

repeat the propagating, generating, and recoding steps for at least a second iteration;

concatenate the message decks elementwise to form a final message deck;

row sort the final message deck to form a row sorted message deck;

sort rows of the row sorted message deck to form a table sorted message deck; and

sort cards of the table sorted message deck to form the invariant for the graph.

19. The system of claim 18, wherein each message deck comprises an array of cards, each card comprises a two dimensional array of strings, the invariant comprises a three dimensional array of strings, and the length of each array comprises the number of vertices in the graph.

20. The system of claim 18, wherein the message propagation rule used to form the first iteration message deck uses an adjacency matrix corresponding to the graph.

21. The system of claim 20, wherein the message propagation rule is:

${\underset{\_}{U}}_{\mathrm{mij}}^{z+1}<br><br>\left(A\right)=\left(\left(U_{\mathrm{mim}}^z,A_{\mathrm{mj}}\right),\underset{k=\left\{1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>n\right\}<br><br>\backslash <br><br>m<br><br>\text{\hspace{1em}<br><br>}}{\bigcup <br><br>}<br><br>\left\{\left(U_{\mathrm{mik}}^z,A_{\mathrm{kj}}\right)\right\}\right)$

where U^z is the message deck at iteration z, A is the adjacency matrix, n is the number of vertices in the graph, and m, i, and j are indices of the three dimensions of the message deck.

22. A computer-implemented method of generating a complete invariant for a graph comprising:

initializing each card of an initial message deck to an identity matrix;

propagating messages to form a first iteration message deck using a message propagation rule;

generating a first iteration codebook using the first iteration message deck;

recoding the first iteration message deck using the first iteration codebook;

repeating the propagating, generating, and recoding steps for at least a second iteration;

concatenating the message decks elementwise to form a final message deck;

row sorting the final message deck to form a row sorted message deck;

recoding the row sorted message deck to form a transform and a transform codebook;

row sorting the transform to form a row sorted transform; and

sorting rows of the row sorted transform to form the invariant.

23. The computer-implemented method of claim 22, wherein forming the transform codebook comprises computing:

$\hat{S}=\underset{m=1}{\overset{n}{\bigcup <br><br>}}<br><br>\underset{i=1}{\overset{n}{\bigcup <br><br>}}<br><br>R_{\mathrm{mi}}$

where Ŝ

is the transform codebook, R is the row sorted message deck, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the row sorted message deck.

24. The computer-implemented method of claim 22, wherein forming the transform comprises computing:

S_mi=E_Ŝ

{R_mi}

where S is the transform, S is the transform codebook, and E is a recoding operator that recodes R according to codebook Ŝ

.

25. The computer-implemented method of claim 22, wherein sorting the rows of the row sorted transform comprises computing:

$V^{\mathrm{\prime <br><br>}}<br><br>\left(A\right)=\underset{m=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}}{\bigcup <br><br>}<br><br>\left\{S_{\mathrm{mm}}<br><br>\left(A\right)<br><br>\underset{i=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>m<br><br>\text{\hspace{1em}<br><br>}}{\bigcup <br><br>}<br><br>\left\{S_{\mathrm{mi}}<br><br>\left(A\right)\right\}\right\}$

where V′

is the invariant, A is the adjacency matrix for the graph, S is the transform, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the transform.

26. The computer-implemented method of claim 25, further comprising storing the invariant and the adjacency matrix as an ordered pair.

27. The computer-implemented method of claim 22, further comprising storing the invariant and the transform as an ordered pair.

28. An article comprising:

a machine accessible medium containing instructions, which when executed, result in generating a complete invariant for a graph by

initializing each card of an initial message deck to an identity matrix;

propagating messages to form a first iteration message deck using a message propagation rule;

generating a first iteration codebook using the first iteration message deck;

recoding the first iteration message deck using the first iteration codebook;

repeating the propagating, generating, and recoding steps for at least a second iteration;

concatenating the message decks elementwise to form a final message deck;

row sorting the final message deck to form a row sorted message deck;

recoding the row sorted message deck to form a transform and a transform codebook;

row sorting the transform to form a row sorted transform; and

sorting rows of the row sorted transform to form the invariant.

29. The article of claim 28, wherein instructions to form the transform codebook comprise instructions to compute:

$\hat{S}=\underset{m=1}{\overset{n}{\bigcup <br><br>}}<br><br>\underset{i=1}{\overset{n}{\bigcup <br><br>}}<br><br>R_{\mathrm{mi}}$

where Ŝ

is the transform codebook, R is the row sorted message deck, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the row sorted message deck.

30. The article of claim 28, wherein instructions to form the transform comprise instructions to compute:

S_mi=E_Ŝ

{R_mi}

where S is the transform, Ŝ

is the transform codebook, and E is a recoding operator that recodes R according to codebook Ŝ

.

31. The article of claim 28, wherein instructions to sort the rows of the row sorted transform comprise instructions to compute:

$V^{\mathrm{\prime <br><br>}}<br><br>\left(A\right)=\underset{m=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}}{\bigcup <br><br>}<br><br>\left\{S_{\mathrm{mm}}<br><br>\left(A\right)<br><br>\underset{i=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>m<br><br>\text{\hspace{1em}<br><br>}}{\bigcup <br><br>}<br><br>\left\{S_{\mathrm{mi}}<br><br>\left(A\right)\right\}\right\}$

where V′

is the invariant, A is the adjacency matrix for the graph, S is the transform, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the transform.

32. A system for testing isomorphism of two graphs comprising:

an invariant generation module to accept an adjacency matrix for each graph and produce an invariant for each graph; and

an invariant comparison module coupled to the invariant generation module to accept the invariants, to compare the invariants, and to produce an isomorphism indicator;

wherein the invariant generation module is adapted to perform the following for each graph

initializing each card of an initial message deck to an identity matrix;

propagating messages to form a first iteration message deck using a message propagation rule;

generating a first iteration codebook using the first iteration message deck;

recoding the first iteration message deck using the first iteration codebook;

repeating the propagating, generating, and recoding steps for at least a second iteration;

concatenating the message decks elementwise to form a final message deck;

row sorting the final message deck to form a row sorted message deck;

recoding the row sorted message deck to form a transform and a transform codebook;

row sorting the transform to form a row sorted transform; and

sorting rows of the row sorted transform to form the invariant.

33. The system of claim 32, wherein the invariant generation module is adapted to form the transform codebook by computing:

$\hat{S}=\underset{m=1}{\overset{n}{\bigcup <br><br>}}<br><br>\underset{i=1}{\overset{n}{\bigcup <br><br>}}<br><br>R_{\mathrm{mi}}$

where Ŝ

is the transform codebook, R is the row sorted message deck, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the row sorted message deck.

34. The system of claim 32, wherein the invariant generation module is adapted to form the transform by computing:

S_mi=E_Ŝ

{R_mi}

where S is the transform, S is the transform codebook, and E is a recoding operator that recodes R according to codebook Ŝ

.

35. The system of claim 32, wherein the invariant generation module is adapted to sort the rows of the row sorted transform by computing:

$V^{\mathrm{\prime <br><br>}}<br><br>\left(A\right)=\underset{m=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}}{\bigcup <br><br>}<br><br>\left\{S_{\mathrm{mm}}<br><br>\left(A\right)<br><br>\underset{i=\left\{1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n\right\}<br><br>\backslash <br><br>m}{\bigcup <br><br>}<br><br>\left\{S_{\mathrm{mi}}<br><br>\left(A\right)\right\}\right\}$

where V″

is the invariant, A is the adjacency matrix for the graph, S is the transform, n is the number of vertices in the graph, and m and i are indices of two of the dimensions of the transform.