Prufer Coding: A Vectorization Method for Undirected Labeled Graph

Abstract

Prufer algorithm is a powerful method for topology vectorization, but the traditional prufer algorithm method can only encode a rootless labeled tree, and no prior work has studied the method of applying it to the graph vectorization. This paper proposes a vectorization method for undirected labeled graphs based on the prufer algorithm, including graph encoding and decoding algorithms. A particular case was discovered by preliminary experiments, which will reduce the accuracy of the coding algorithm (when the node size reaches more than 150, the accuracy can only reach about 60%), so a connectivity check mechanism that based on the Warshall algorithm is proposed and added to the coding algorithm. A large number of experimental verifications show that the accuracy of the coding algorithm can reach 100% after introducing this mechanism. Then the length of the vector generated by the coding algorithm is analyzed, and the results show that graph vectorization can improve the efficiency of partial topology calculation. Finally, the defects of the algorithm are discussed. The most significant defect is that the length of the vector generated by the encoding algorithm is uncertain, which will prevent it from being applied to more topological calculations.

Keywords

• Graph vectorization
• topology calculation
• prufer algorithm
• Warshall algorithm
• algorithm design