Κοίταξε να δεις... Η αλήθεια είναι ότι εξακολουθώ να έχω ορισμένες απορίες ως προς το τι εννοείς "συσχέτιση" και "μεταβατική ιδιότητα" (αρχικό post). Δεν είμαι ειδικός πάνω στο θέμα και όπως είναι φυσικό ψάχνομαι μαζί σου. Οπότε μη θεωρήσεις αυτά που γράφω ως "τελεσίδικα" και όποιος έχει ασχοληθεί με το αντικείμενο, καλόν είναι να κάνει ένα post για να με διορθώσει αν γράφω ανακρίβειες.
Το σημείο που πρέπει να προσέξεις στον Bron–Kerbosch είναι ο όρος complete connectivity: Από τα λίγα που καταλαβαίνω, αυτό σημαίνει ότι για να συμπεριληφθεί ένα subgraph ως αποτέλεσμα, πρέπει - εκτός από τα περιμετρικά σημεία - να συνδέονται μεταξύ τους και όλες οι διαγώνιοι. Στο αρχικό post αναφέρεις ένα τετράγωνο με όλες του τις διαγωνίους σαν αποτέλεσμα της ζητούμενης συσχέτισης (Α-Β, Α-Γ, Α-Δ, Β-Γ, Β-Δ, Γ-Δ). Όμως, ακριβώς από πάνω γράφεις ότι ισχύει, Β-Δ:0. Αν δεν έχει γίνει λάθος στην πληκτρολόγηση, τότε ο Bron-Kerbosch δεν είναι ο αλγόριθμος που ψάχνεις. Μάλλον, ζητάς έναν αλγόριθμο που να σου δίνει όλες τις κλειστές διαδρομές (cycles).
Τώρα, ο clique αλγόριθμος που αναφέρεις είναι ερευνητικός. Πουθενά δεν τεκμηριώνεται ότι θα δώσει όλα τα maximal cliques. Δεν το λέω εγώ, αλλά αυτοί που τον έφτιαξαν, στην παράγραφο sufficiency:
"The algorithm may be applied to any simple graph and will always terminate in polynomial-time, finding many maximal cliques. The propositions below establish sufficient conditions on the input graph which guarantee that the algorithm will find maximal cliques of a certain size."
Ειλικρινά, το implementation σε Java που σου πρότεινα δεν κάθισα να το ελέγξω. Και για να λέει ο Παναγιώτης ότι έχει bugs, τότε έχει (οπότε και σου ζητώ συγγνώμη). Δεν έχω, όμως, κάτι άλλο υπόψη μου. Όπως και δεν γνωρίζω αν υπάρχει αλγόριθμος που να δίνει όλα τα cycles. Αν θέλεις, κάνε ένα post για να απαντήσεις στις απορίες μου και να με διορθώσεις όπου δεν έχω καταλάβει κάτι σωστά.
Ακόμα κι ένας άνθρωπος μπορεί ν' αλλάξει τον κόσμο. Μη θέλεις να κυβερνήσεις. Απλά δείξε το μονοπάτι κι ο κόσμος θ' ακολουθήσει!!