Gegeven een simpele graaf \(G=(V,E)\) (geen dubbele bogen of lussen). Een kliek in \(G\) is een subset \(C\subseteq V\) zodat elke twee toppen in \(C\) verbonden zijn door een boog. We zijn op zoek naar de grootst mogelijke kliek in \(G\).

Implementeer hiervoor de interface CliqueFinder¹ in een klasse BBCliqueFinder. Deze vereist een methode Collection<Integer> maxClique(UndirectedGraph<Integer> graph), die de nummers van de toppen van een grootste kliek berekent. Gebruik hiervoor een snoeifunctie op basis van topkleuringen. De meegegeven graaf mag je niet wijzigen.

De graaf is van het type UndirectedGraph<Integer>, uit de grafenbibliotheek graphlib². De API van deze bibliotheek vind je hier³. Intern mag je natuurlijk overgaan op een andere voorstelling, als dat efficiënter zou zijn. De toppen van de gegeven graaf zijn namelijk steeds \(\{0,\dots, n-1\}\).

Zorg ervoor dat je zoekfunctie op tijd snoeit en zo niet verderzoekt naar oplossingen die zeker niet optimaal kunnen zijn. Implementeer eventueel ook een heuristiek die snel een goede startoplossing kan vinden.

Met behulp van SimpleTest⁴ kan je jouw oplossing lokaal uittesten.