# Hungarian Assignment Algorithm Implementation

I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows:

S(0) <- appropriately sized matrix filled with 1's
for k=1 to 10 do:
S(k) = Y*S(k-1)*X^T + Y^T*S(k-1)*X
k++
Apply Hungarian assignment algorithm on similarity matrix S.


where X^T means the transpose of the matrix X.

Basically, given two graphs G1, G2 (not necessarily the same # of vertices), create their adjacency matrices X and Y. Then, do this iterative process 10 times, and then apply the Hungarian assignment algorithm. The result would be a similarity matrix where entry (i,j) represents a real number between 0 and 1 that gives how "similar" vertex i is of G1 to vertex j of G2.

My question is: how would this algorithm be implemented? I looked up the algorithm on Wikipedia, and the explanation seems as though all entries in S would be integers, but what is expected is real numbers between 0 and 1.

• I don't get the question. What is your particular problem when implementing the algorithm? – Raphael Nov 8 '14 at 16:57
• There is no explanation I can find that details how the algorithm works nor an existing implementation of the algorithm. The only part that I can't find is about the Hungarian assignment part. – Ryan Nov 8 '14 at 16:58
• See page 13 of this slide deck. Per my understanding, the entries in $S$ need not be integral for the algorithm to still work. – apnorton Nov 8 '14 at 21:13
• Some context for the question, in case people were wondering: academia.stackexchange.com/questions/31410/… – apnorton Nov 8 '14 at 21:15

• @Ryan The Hungarian algorithm yields a selection of elements in $S$ such that their sum is maximal. (It does not return an integer.) Since each row/column in $S$ corresponds to a vertex in the first/second graph to compare, we can consider an entry in $S$ to provide a map from the first graph to the second graph. The row/columns of $S$ that are selected then generates a mapping between the two graphs. Does that help, or am I misunderstanding your question? – apnorton Nov 8 '14 at 22:12