Plagiaat detecteren in programmeeroefeningen is een onderzoeksveld op zich waarbij verschillende disciplines gecombineerd worden: statische analyse van programmacode, stringmatching, statistiek, … enzovoort. Maar om het kopieergedrag van groepen studenten in kaart te brengen, is de studie van grafen uitermate geschikt.

Zo’n plagiaatdetectiesoftware werkt meestal als volgt: aan elk paar van indieningen die geanalyseerd wordt, wordt een probabiliteit toegekend die aangeeft hoe waarschijnlijk het is dat één van de twee studenten de andere heeft geplagieerd.

Nu kunnen we een graaf maken met als toppen de indieningen. We verbinden twee toppen met een boog als deze probabiliteit hoger is dan een bepaalde drempel. De resulterende graaf noemen we een plagiaatgraaf.

Je merkt dat er verschillende groepen gevormd worden die onderling verbonden zijn. Zo’n groep noemen we een plagiaatgroep. Als we dit willen definiëren met de terminologie uit de grafentheorie, dan is een plagiaatgroep een samenhangscomponent met minstens twee toppen. Bijvoorbeeld: onderstaande graaf heeft twee samenhangscomponenten.

We zoeken nu naar een manier om de drempelwaarde van de plagiaatgraaf zo te leggen dat er zo veel mogelijk plagiaatgroepen zijn. Als er meerdere drempelwaarden zijn die hetzelfde aantal geven, zoeken we naar die waarde waarbij het minst aantal personen in een plagiaatgroep zitten.

Je kan daarvoor een simpel algoritme volgen:

• Maak een graaf met voor elke indiening een top en voor elk paar indieningen een boog met de probabiliteit als gewicht.
• We starten met elke top in een aparte groep. Elke groep heeft maar één top; aangezien deze niet meetellen zijn er dus nog geen plagiaatgroepen.
• Overloop de bogen in dalende volgorde van gewicht:
  • Verbind de twee toppen van de volgende bogen met hetzelfde gewicht met elkaar.
  • Controleer of het aantal groepen veranderd is: zodra twee of meer toppen in dezelfde groep zitten, spreken we van een plagiaatgroep.
  • Vergelijk met het maximaal aantal groepen dat je tot nu toe gezien hebt, en pas die indien nodig aan naar de huidige groepen.
• Uiteindelijk zijn alle toppen met een probabiliteit groter dan 0 verbonden met elkaar. Als de oorspronkelijke graaf samenhangend was, is er nu één grote plagiaatgroep.
• Geef de maximale plagiaatgroepen terug.

Nu is het aan jou om dit te implementeren. Let daarbij op om dit efficiënt te doen, want het aantal toppen en bogen kan groot zijn.

Implementeer de interface GraafMaker¹ in een klasse genaamd PlagiaatGraafMaker. Hiervoor schrijf je twee methoden:

• UndirectedGraph<Indiening> maakPlagiaatgraaf(Collection<Indiening> indieningen, PlagiaatDetector detector); die een collectie van Indiening² records en een PlagiaatDetector³ object als argumenten neemt en de plagiaatgraaf teruggeeft waarbij twee toppen verbonden zijn als de probabiliteit hoger is 0.
• Collection<? extends Collection<Indiening>> maximalePlagiaatGroepen(UndirectedGraph<Indiening> plagiaatgraaf); die de maximale plagiaatgroepen teruggeeft.

Deze interface voorziet ook een methode plagiaatGroepen die deze twee methoden combineert. Deze methode is echter al geïmplementeerd en hoef je dus niet zelf te implementeren.

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib⁴. Deze bevat onder meer de klassen UndirectedGraph en Node. De API van deze bibliotheek vind je hier⁵. Neem eerst en vooral eens de API door en stel eventueel vragen hierover voor je begint te programmeren.

Gebruik de testklasse SimpleTest⁶ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.

Opmerking: je kan een nieuwe boog tussen toppen i1 en i2 met gewicht w toevoegen aan een plagiaatgraaf met de volgende code:

graaf.addEdge(new UndirectedEdge<>(graph.getNode(i1), graph.getNode(i2), w));

Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in IntelliJ, moet je het bestand graphlib.jar⁷ toevoegen aan je project. Hiervoor ga je naar File -> Project Structure… Vervolgens kies je Libraries en klik je op de knop met het plusteken (+). Kies voor Java en navigeer naar het gedownloade bestand graphlib.jar.