Logisim circuit similarity algorithm based on maximum connected subgraph
Kengyi Fang · 2023
Logisim is a cross-platform educational tool for designing and simulating digital logic circuits, and it is widely used in experiments for courses such as computer organization in universities. As Logisim is widely used, tasks such as plagiarism detection require the calculation of Logisim circuit similarity, and the Logisim circuit similarity algorithm becomes very important. Logisim can represent circuits as text in XML format or render circuits as RGB images, which means that Logisim circuit similarity can be calculated using both text similarity algorithms and image similarity algorithms. However, due to the characteristics of Logisim circuits, text similarity algorithms and image similarity algorithms cannot achieve good results. In this paper, we propose a Logisim circuit similarity algorithm based on the maximum connected subgraph. We first represent the Logisim circuit as a collection of maximum connected subgraphs, then calculate the proportion of nodes with the same type, similar location and isomorphic local subgraphs in maximum connected subgraphs as the similarity of maximum connected subgraphs, and finally calculate the proportion of maximum connected subgraphs whose maximum similarity exceeds a threshold as the similarity of the collection of maximum connected subgraphs (i.e., Logisim circuits). We construct two Logisim similar circuit datasets based on real-world data. The experimental results on these datasets show that our method outperforms well-known text similarity algorithms and image similarity algorithms.