ALGORITHMES POUR GRAPHIQUE POLYÉDRAL (Graphique Planar 3 connectés) Isomorphisme?

Question

J'ai mis des recherches sur le thème de l'isomorphisme graphique pour les graphiques connectés à 3 plans, mais il existe une abondance d'algorithmes de restriction différente, de complexité théorique et de fréquence d'utilisation et de trouver des difficultés qui se tientcomme:

• facile à comprendre
• peut être implémenté avec une clarté maximale
• bonnes performances pratiques sur de petits graphiques (jusqu'à des sommets dans les dizaines)

Il est difficile de savoir sans comprendre les différents algorithmes moi-même, que je sois meilleur avec l'un des algorithmes plus anciens et plus spécialisés pour ce problème ou les plus récents, plus généraux. Parmi tous les candidats possibles, lequel est / celles-là sont la meilleure solution?

Answer 1

Je pense que l'algorithme de Weinberg convient à la facture.

• facile à comprendre: calculez systèmes de rotation pour g et h comme sous-produits d'un algorithme de test de planarité. Étant donné que G et H sont connectés à 3, ces systèmes de rotation sont isomorphes jusqu'à l'interchangeage dans le sens des aiguilles d'une montre et dans le sens anti-horaire si et uniquement si g et h sont isomorphes. Choisissez une fléchette (= bord avec une direction indiquée) D en G et essayez de la mapper à toutes les fléchettes E dans H (et répétez pour l'autre orientation de H). Étant donné que G est connecté, toutes les autres fléchettes d 'peuvent être atteintes de D en composant les deux opérations du système de rotation pour G. Appliquer les opérations correspondantes à E et vérifier s'il existe un isomorphisme.

• Clarté maximale: mis à part le test de planarité, ce qui précède est une page de code. Peut-être que vous pourriez réutiliser le test de planarité de quelqu'un d'autre? Il y en a un à Boost, par exemple. Sinon, je pense toujours que la mise en œuvre de vôtre est plus facile que de réécrire Nauty.

• bonnes performances pratiques sur de petits graphiques: après le test de planerie, l'algorithme de Weinberg est essentiellement deux traverser les premiers profondeurs synchronisés pour chaque fléchette. L'heure de fonctionnement totale est O (| V | ^{2 ) sans grande constantes qui se cachent.}