Integracija algoritmov za problem podgrafnega izomorfizma v okolje R

POPOVIČ, NIKOLAJ (author), Mihelič, Jurij (mentor), Čibej, Uroš (co-mentor)

V tem diplomskem delu obravnavamo integracijo algoritma SICS v programsko okolje R. Gre za algoritem namenjen reˇsevanju problema podgrafenga izomorfizma, ki se nanaˇsa na iskanje vzorcev manjˇsega grafa v veˇcjem. Algoritem je na testiranjih dosegel boljˇse rezultate od predhodnih algoritmov za reˇsevanje tega problema. Implementiran je v jeziku C++, kar mu omogoˇca hitrejˇse izvajanje. Ker smo ˇzeleli algoritem uporabljati v programskem okolju R smo ga morali tja integrirati. Rezultat te integracije je paket SICS, ki se nahaja na Githubu in je javno dostopen. Deluje tako, da ga namestimo v naˇse razvojno okolje, nato pa ga uporabljamo kot knjiˇznico z eno funkcijo. Funkcija kot vhod sprejme dva grafa in razliˇcne parametre za izvajanje, kot izhod pa vrne seznam s preslikavami vozliˇsˇc med vhodnima grafoma.

• Language: Slovenian
• Keywords: integracija, izomorfizem, graf
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2022
• PID: 20.500.12556/RUL-139601
• COBISS.SI-ID: 120516611
• Publication date in RUL: 05.09.2022

Secondary language

• Language: English
• Title: Integration of algorithms for subgraph isomorphism problem into the R environment

Abstract

In this diploma thesis we will deal with integration of algorithm SICS into R program environment. This algorithm was created for solving the problem of subgraph isomorphism, which refers to pattern matching problem between smaller and bigger graph. In the benchmarks an algorithm performed better the previous algorithms for solving this problem. Algorithm is implemented in C++ programming language which enables him to perform faster. Since we wanted to use the algorithm in R software environment, we had to integrate it there. The result of this integration is the SICS package which is located on Github and is publicly available. It works such that we install it first in our development environment and from then on we use it as a library with single function. The function accepts two and various execution parameters graphs as input , and returns a list with node mappings between the input graphs as an output.

• Keywords: integration, isomorphism, graph