/fvs-algorithm

Primary LanguageJavaMIT LicenseMIT

Feedback Vertex Set

De quoi s'agit-il ?

Un 'feedback vertex set' (FVS) d'un graphe est un sous ensemble de sommets qui contient au moins un sommet de chaque cycle dans le graphe. Le but est donc de trouver un 'feedback vertex set' de taille minimum. Nous travaillons sur un graphe non-orienté. Cette page présente une implémentation de l' algorithme Bafna-Berman-Fujito. Le langage Java est utilisé.

Execution

Le projet contient un build.xml avec les commandes suivantes :

  • compile : compilation de l'interface de test et de l'algorithme
  • run : lance l'interface de test de l'algorithme

Implementation

Nous expliquons ici la structure de l'implémentation ainsi que des choix techniques effectués (structure de données..)

Classe DefaultTeam

Cette class contient l'algorithme principal ainsi que les différentes méthodes nécessaires à son implémentation.

public ArrayList<Point> calculFVS( ArrayList<Point> points )

Méthode appelée par le GUI de test.

Parametres :

  • points : les sommets du graphe

Retour : Un minimum feedback vertex set du graphe.

public ArrayList<Point> bbfAlgo( ArrayList<Point> points )

Implémentation de l'algorithme tel que décrit dans l'article

Une HashMap est utilisée pour associer un poids à un sommet. Ainsi l'obtention du poids d'un sommet se fait en 0(1). La structure de donnée HashSet de java est utilisée pour représenter des ensembles de sommets ( par exemple pour l'ensemble F). Cette structure de donnée offre des opérations d'ajout, suppression et d'appartenance en temps constant. De cette façon nous pouvons facilement tester l'appartenance d'un point particulier à cet ensemble en O(1).

Parametres :

  • points : les sommets du graphe

Retour : Un minimum feedback vertex set du graphe.

public double min( ArrayList<Point> v , Map<Point , Double> weight )

Parametres :

  • v : les sommets du graphe
  • weight : les poids des sommets du graphe

Retour : min{weight(u) : u∈v}

public double min2( ArrayList<Point> v , Map<Point , Double> weight )

Parametres :

  • v : les sommets du graphe
  • weight : les poids des sommets du graphe

Retour : min{weight(u)/(d(u)−1) | u∈v}

public int d( Point p , ArrayList<Point> vertices )

Permet d'obtenir le degré d'un sommet du graphe.

Parametres :

  • p : le sommet du graphe
  • vertices : les sommets du graphe Retour : le degré de p dans vertices
public void cleanUp( ArrayList<Point> v )

Suppression de tous les sommets du graphe de degrés au plus 1. Correspond à la procedure Cleanup de l'article

Parametres :

  • v : les sommets du graphe
public ArrayList<Point> semiDisjoint( ArrayList<Point> vertices )

Cherche un cycle semidisjoint C dans le graphe. C est semidisjoint si, pour chaque sommet u de C, d(u) = 2, avec au plus 1 exception. Etapes de la fonction :

  • recherche d'un cycle dans le graphe
  • Analyse du degré des sommets du cycle (si cycle il y a)

Parametres :

  • vertices : les sommets du graphe

Retour : Un cycle semidisjoint s'il existe, null sinon

public ArrayList<Point> getCycle( ArrayList<Point> vertices )

Cherche un cycle dans le graphe. C'est un algorithme de parcours en profondeur récursif.

  • Un HashSet est utilisé pour marquer les sommets visités. (test d'appartenance aux sommets visités effectué en temps constant grace à cette structure de données).
  • Une pile Deque est utilisé pour 'sortir' le cycle trouvé à la fin de l'algorithme.

Parametres :

  • vertices : les sommets du graphe

Retour : Un cycle

private boolean dfs( ArrayList<Point> g , Point v , Point father , Set<Point> visited , Deque<Point> stack )

Fonction appelée récursivement pour le parcours en profondeur du graphe.

Parametres :

  • g : les sommets du graphe
  • v : le sommet courant
  • father : le dernier père visité du sommet courant
  • visited : l'ensemble des sommets visités
  • stack : contient le cycle à la fin de l'execution de l'algorithme s'il existe

Retour : Vrai si un cycle est détecté, faux sinon

Classe Evaluation

Cette classe utilitaire contient des fonctions permettant d'évaluer la validité du FVS produit par l'algorithme.

private static boolean isMember( ArrayList<Point> points , Point p )

Permet de déterminer si un point p appartient à une liste de points

Parametres :

  • p : le point à cherche
  • points : l'ensemble de points à chercher

Retour : Vrai si p appartient à points, faux sinon

public static boolean isValide( ArrayList<Point> origPoints , ArrayList<Point> fvs )

Permet de tester si fvs est un fvs dans origPoints

Parametres :

  • origPoints : l'ensemble de points
  • fvs : le fvs à tester

Retour : Vrai si fvs est un minimum feedback vertex set dans origPoints.

public static ArrayList<Point> neighbor( Point p , ArrayList<Point> vertices )

Permet d'obtenir les voisins de p dans le graphe de vertices

Parametres :

  • p : le point dont on souhaite obtenir les voisins
  • vertices : les sommets du graphe

Retour : Une liste de points qui sont les voisins de p

Exemples

Voici le résultat (à droite) de l'algorithme appliqué sur un graphe (à gauche).

Historique de développement

Versions Description
1.0 Implémentation de l'algorithme Bafna-Berman-Fujito

Références