Probleme de la plus grande clique d'un graphe
konouz
Messages postés
8
Date d'inscription
samedi 28 février 2009
Statut
Membre
Dernière intervention
31 mai 2011
-
15 déc. 2009 à 12:16
cs_jojolemariole Messages postés 519 Date d'inscription mercredi 21 mars 2007 Statut Membre Dernière intervention 19 décembre 2016 - 12 janv. 2010 à 09:28
cs_jojolemariole Messages postés 519 Date d'inscription mercredi 21 mars 2007 Statut Membre Dernière intervention 19 décembre 2016 - 12 janv. 2010 à 09:28
7 réponses
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
15 déc. 2009 à 16:52
15 déc. 2009 à 16:52
Bonjour,
wikipedia :
http://en.wikipedia.org/wiki/Clique_(graph_theory)
définition :
"A clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two."
apparemment c'est un problème NP-complet :
"In computer science, the clique problem is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is NP-complete, one of Karp's 21 NP-complete problems (Karp 1972)."
A mon avis la solution la plus simple à mettre en oeuvre :
- tu testes tous les sous-ensembles de noeuds possibles (il y en a 2^n dans un graphe à n noeuds)
- pour chaque sous-ensemble de noeuds tu testes si c'est une clique
-> critère pour qu'un sous-ensemble soit une clique : tu testes si chaque noeuds est relié à tous les autres (hormis lui même)
- tu gardes la cardinalité du sous-ensemble de noeuds le plus grand qui soit une clique
Ca devrait tourner dans un temps raisonnable jusqu'à une vingtaine de noeuds.
wikipedia :
http://en.wikipedia.org/wiki/Clique_(graph_theory)
définition :
"A clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two."
apparemment c'est un problème NP-complet :
"In computer science, the clique problem is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is NP-complete, one of Karp's 21 NP-complete problems (Karp 1972)."
A mon avis la solution la plus simple à mettre en oeuvre :
- tu testes tous les sous-ensembles de noeuds possibles (il y en a 2^n dans un graphe à n noeuds)
- pour chaque sous-ensemble de noeuds tu testes si c'est une clique
-> critère pour qu'un sous-ensemble soit une clique : tu testes si chaque noeuds est relié à tous les autres (hormis lui même)
- tu gardes la cardinalité du sous-ensemble de noeuds le plus grand qui soit une clique
Ca devrait tourner dans un temps raisonnable jusqu'à une vingtaine de noeuds.
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
15 déc. 2009 à 17:17
15 déc. 2009 à 17:17
Voilà une implémentation de graphe non orienté qui pourrait te rendre service :
package graph;
import java.util.Set;
/**
* objet representant un graphe non-orienté a l'aide d'une simple matrice de
* booléens (dite matrice d'incidence)
*
* @author jojolemariole
*/
public class UndirectedGraph {
private boolean[][] edges;
/**
* crée un graphe non-orienté avec aucune arete initialement
*
* @param vertexCount nombre de sommets dans le graphe (par commodité, les
* sommets seront numérotés de 0 à vertexCount-1)
*/
public UndirectedGraph(int vertexCount) {
edges = new boolean[vertexCount][vertexCount];
}
/**
* ajoute une arete entre deux sommets dans le graphe
*
* @param vertex1 premier sommet de l'arete
* @param vertex2 deuxieme sommet de l'arete
*/
public void addEdge(int vertex1, int vertex2) {
edges[vertex1][vertex2] = true;
}
/**
* @param vertex1 premier sommet
* @param vertex2 deuxieme sommet
* @return true s'il y a une arete reliant les deux somments, false sinon
*/
public boolean isEdge(int vertex1, int vertex2) {
return edges[vertex1][vertex2];
}
/**
* @param vertices
* @return true si l'ensemble des sommets fournis forme une clique, false
* sinon
*/
public boolean testClique(Set vertices) {
/*
* on prends tous les couples possibles parmi l'ensemble de sommets
* fourni
*/
for (int vertex1 : vertices) {
for (int vertex2 : vertices) {
if (vertex1 != vertex2) {
if (!isEdge(vertex1, vertex2)) {
/*
* si les deux sommets ne sont pas relies pas une arete :
* le sous-ensemble de sommets fourni ne forme pas une
* clique
*/
return false;
}
}
}
}
/*
* si tous les couples de sommets possibles sont relies, le
* sous-ensemble de sommets fourni forme une clique
*/
return true;
}
}
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
16 déc. 2009 à 18:19
16 déc. 2009 à 18:19
re,
Pour ne pas t'induire en erreur, je rectifie mon code précédent.
CLIQUE :
GRAPHE NON-ORIENTE :
CLIQUE
Pour ne pas t'induire en erreur, je rectifie mon code précédent.
CLIQUE :
package graph;
import java.util.HashSet;
import java.util.Set;
/**
* objet representant une clique par un ensemble de sommets
*
* @author jojolemariole
*/
public class Clique {
/**
* clique qui n'en est pas une : constante pour signaler qu'il n'y a pas de
* clique
*/
public static final Clique NO_CLIQUE;
static {
NO_CLIQUE = new Clique(null, null);
}
private UndirectedGraph graph;
private Set vertices;
private int size;
/**
* @param graph graphe non-oriente contenant la clique
* @param vertices ensemble des sommets de la clique, on en fera une copie
*/
public Clique(UndirectedGraph graph, Set vertices) {
this.graph = graph;
if (vertices == null) {
size = -1;
} else {
this.vertices = new HashSet(vertices);
size = vertices.size();
}
}
/**
* @return le graph non-oriente contenant la clique
*/
public UndirectedGraph getGraph() {
return graph;
}
/**
* @return l'ensemble des sommets de la clique
*/
public Set getVertices() {
return vertices;
}
/**
* @return le nombre de sommets de la clique, -1 si this n'est pas une
* clique
*/
public int getSize() {
return size;
}
public String toString() {
String toString;
if (this == NO_CLIQUE) {
toString = "\nno clique";
} else {
toString = "\nvertices : " + vertices + "\nsize : " + size;
}
return toString;
}
}
GRAPHE NON-ORIENTE :
package graph;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* objet representant un graphe non-oriente a l'aide d'une simple matrice de
* booleens (dite matrice d'incidence)
*
* @author jojolemariole
*/
public class UndirectedGraph {
private int vertexCount;
private boolean[][] edges;
/**
* cree un graphe aleatoire
*
* @param vertexCount nombre de sommets du graphes (par commodite, les
* sommets seront numerotée de 0 à vertexCount-1)
* @param edgeProbability probabilite que 2 sommets soient relies entre eux,
* dans l'intervalle [0.0, 1.0]
*/
public UndirectedGraph(int vertexCount, double edgeProbability) {
this(vertexCount);
double random;
/*
* on parcourt tous les couples de sommets possibles
*/
for (int vertex1 = 0; vertex1 < vertexCount; vertex1++) {
for (int vertex2 = vertex1 + 1; vertex2 < vertexCount; vertex2++) {
/*
* pour chaque couple de sommet, on prend un double au hasard
* dans l'intervalle [0.0, 1.0[ si ce nombre est inferieur a la
* probabilite d'arete, on cree une arete entre les deux sommets
*/
random = Math.random();
if (random < edgeProbability) {
addEdge(vertex1, vertex2);
}
}
}
}
/**
* cree un graphe non-oriente avec aucune arete initialement
*
* @param vertexCount nombre de sommets dans le graphe (par commodite, les
* sommets seront numerotée de 0 à vertexCount-1)
*/
public UndirectedGraph(int vertexCount) {
this.vertexCount = vertexCount;
edges = new boolean[vertexCount][vertexCount];
}
/**
* ajoute une arete entre deux sommets dans le graphe
*
* @param vertex1 premier sommet de l'arete
* @param vertex2 deuxieme sommet de l'arete
*/
public void addEdge(int vertex1, int vertex2) {
edges[vertex1][vertex2] = true;
edges[vertex2][vertex1] = true;
}
/**
* @param vertex1 premier sommet
* @param vertex2 deuxieme sommet
* @return true s'il y a une arete reliant les deux sommets, false sinon
*/
public boolean isEdge(int vertex1, int vertex2) {
return edges[vertex1][vertex2];
}
/**
* @return la clique maximale du graphe
*/
public Clique getMaximumClique() {
/*
* on ajoute tous les sommets numerotes de 0 a vertexCount-1 dans une
* liste de sommets utilisables
*/
List usableVertices = new ArrayList(vertexCount);
for (int vertex = 0; vertex < vertexCount; vertex++) {
usableVertices.add(vertex);
}
/*
* on initialise un ensemble de sommets utilises a vide
*/
Set usedVertices = new HashSet();
/*
* on appelle la methode recursive qui va nous renvoyer la clique
* maximale
*/
return getMaximumClique(usableVertices, usedVertices);
}
/**
* @param usableVertices sommets disponibles, on peut les integrer ou non a
* la clique
* @param usedVertices sommets deja choisis pour former la clique
* @return la clique maximale formee en utilisant obligatoirement les
* sommets de usedVertices et en utilisant une partie des sommets de
* usableVertices
*/
private Clique getMaximumClique(List usableVertices, Set usedVertices) {
// la c'est a toi de faire le travail
}
/**
* @param vertices ensemble de sommets du graphe
* @return true si l'ensemble des sommets fournis forme une clique, false
* sinon
*/
public boolean testClique(Set vertices) {
/*
* on prends tous les couples possibles parmi l'ensemble de sommets
* fourni
*/
for (int vertex1 : vertices) {
for (int vertex2 : vertices) {
if (vertex1 < vertex2) {
if (!isEdge(vertex1, vertex2)) {
/*
* si les deux sommets ne sont pas relies pas une arete :
* le sous-ensemble de sommets fourni ne forme pas une
* clique
*/
return false;
}
}
}
}
/*
* si tous les couples de sommets possibles sont relies, le
* sous-ensemble de sommets fourni forme une clique
*/
return true;
}
}
CLIQUE
yousrat
Messages postés
1
Date d'inscription
samedi 14 février 2009
Statut
Membre
Dernière intervention
23 décembre 2009
23 déc. 2009 à 03:00
23 déc. 2009 à 03:00
salut,
J'ai essayée ton code c'est très intéressant mais me manque le main, vous pouvez m'aider stp. Merci d'avance
J'ai essayée ton code c'est très intéressant mais me manque le main, vous pouvez m'aider stp. Merci d'avance
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
4 janv. 2010 à 17:47
4 janv. 2010 à 17:47
Salut,
Bien sûr je n'ai pas mis le code en entier puisqu'il s'agissait d'un projet d'étude.
A priori la deadline est passée donc je propose le reste du code :
pour ce qui est du main, voici un petit exemple :
Voilà, bien sûr il y a matière à moult optimisation.
Bien sûr je n'ai pas mis le code en entier puisqu'il s'agissait d'un projet d'étude.
A priori la deadline est passée donc je propose le reste du code :
package graph;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* objet representant un graphe non-oriente a l'aide d'une simple matrice de
* booleens (dite matrice d'incidence)
*
* @author jojolemariole
*/
public class UndirectedGraph {
private int vertexCount;
private boolean[][] edges;
/**
* cree un graphe aleatoire
*
* @param vertexCount nombre de sommets du graphes (par commodite, les
* sommets seront numerotée de 0 à vertexCount-1)
* @param edgeProbability probabilite que 2 sommets soient relies entre eux,
* dans l'intervalle [0.0, 1.0]
*/
public UndirectedGraph(int vertexCount, double edgeProbability) {
this(vertexCount);
double random;
/*
* on parcourt tous les couples de sommets possibles
*/
for (int vertex1 = 0; vertex1 < vertexCount; vertex1++) {
for (int vertex2 = vertex1 + 1; vertex2 < vertexCount; vertex2++) {
/*
* pour chaque couple de sommet, on prend un double au hasard
* dans l'intervalle [0.0, 1.0[ si ce nombre est inferieur a la
* probabilite d'arete, on cree une arete entre les deux sommets
*/
random = Math.random();
if (random < edgeProbability) {
addEdge(vertex1, vertex2);
}
}
}
}
/**
* cree un graphe non-oriente avec aucune arete initialement
*
* @param vertexCount nombre de sommets dans le graphe (par commodite, les
* sommets seront numerotée de 0 à vertexCount-1)
*/
public UndirectedGraph(int vertexCount) {
this.vertexCount = vertexCount;
edges = new boolean[vertexCount][vertexCount];
}
/**
* ajoute une arete entre deux sommets dans le graphe
*
* @param vertex1 premier sommet de l'arete
* @param vertex2 deuxieme sommet de l'arete
*/
public void addEdge(int vertex1, int vertex2) {
edges[vertex1][vertex2] = true;
edges[vertex2][vertex1] = true;
}
/**
* @param vertex1 premier sommet
* @param vertex2 deuxieme sommet
* @return true s'il y a une arete reliant les deux sommets, false sinon
*/
public boolean isEdge(int vertex1, int vertex2) {
return edges[vertex1][vertex2];
}
/**
* @return la clique maximale du graphe
*/
public Clique getMaximumClique() {
/*
* on ajoute tous les sommets numerotes de 0 a vertexCount-1 dans une
* liste de sommets utilisables
*/
List usableVertices = new ArrayList(vertexCount);
for (int vertex = 0; vertex < vertexCount; vertex++) {
usableVertices.add(vertex);
}
/*
* on initialise un ensemble de sommets utilises a vide
*/
Set usedVertices = new HashSet();
/*
* on appelle la methode recursive qui va nous renvoyer la clique
* maximale
*/
return getMaximumClique(usableVertices, usedVertices);
}
/**
* @param usableVertices sommets disponibles, on peut les integrer ou non a
* la clique
* @param usedVertices sommets deja choisis pour former la clique
* @return la clique maximale formee en utilisant obligatoirement les
* sommets de usedVertices et en utilisant une partie des sommets de
* usableVertices
*/
private Clique getMaximumClique(List usableVertices, Set usedVertices) {
Clique maximumClique;
/*
* d'abord on regarde si l'ensemble des sommets utilises forment une
* clique
*/
boolean isClique = testClique(usedVertices);
if (!isClique) {
/*
* si les sommets utilises ne forment pas une clique, il est inutile
* d'essayer d'ajouter un nouveau sommet : on n'aura jamais de
* clique
*/
maximumClique = Clique.NO_CLIQUE;
} else if (usableVertices.isEmpty()) {
/*
* il n'y a plus de sommets utilisables :
*/
maximumClique = new Clique(this, usedVertices);
} else {
/*
* S'il reste des sommets utilisables, on prend le premier sommet
* utilisable et on relance la methode d'abord en utilisant le
* sommet, puis sans utiliser le sommet. Cette methode permet, par
* recursivite, de tester tous les sous-ensembles de sommets
* possibles.
*/
Integer vertex = usableVertices.remove(0);
Clique maximumCliqueWithThisVertex;
Clique maximumCliqueWithoutThisVertex;
/*
* on cherche la clique maximale avec le sommet choisi
*/
usedVertices.add(vertex);
maximumCliqueWithThisVertex = getMaximumClique(usableVertices, usedVertices);
/*
* on cherche la clique maximale sans le sommet choisi
*/
usedVertices.remove(vertex);
maximumCliqueWithoutThisVertex = getMaximumClique(usableVertices, usedVertices);
/*
* on regarde quelle est la methode qui permet de creer la clique
* maximale (avec ou sans le sommet choisi)
*/
if (maximumCliqueWithThisVertex.getSize() > maximumCliqueWithoutThisVertex.getSize()) {
maximumClique = maximumCliqueWithThisVertex;
} else {
maximumClique = maximumCliqueWithoutThisVertex;
}
/*
* on remet le sommet utilise dans la liste des sommets disponibles
*/
usableVertices.add(vertex);
}
return maximumClique;
}
/**
* @param vertices ensemble de sommets du graphe
* @return true si l'ensemble des sommets fournis forme une clique, false
* sinon
*/
public boolean testClique(Set vertices) {
/*
* on prends tous les couples possibles parmi l'ensemble de sommets
* fourni
*/
for (int vertex1 : vertices) {
for (int vertex2 : vertices) {
if (vertex1 < vertex2) {
if (!isEdge(vertex1, vertex2)) {
/*
* si les deux sommets ne sont pas relies pas une arete :
* le sous-ensemble de sommets fourni ne forme pas une
* clique
*/
return false;
}
}
}
}
/*
* si tous les couples de sommets possibles sont relies, le
* sous-ensemble de sommets fourni forme une clique
*/
return true;
}
}
pour ce qui est du main, voici un petit exemple :
package graph;
/**
* classe permettant de tester la creation d'un graphe non-oriente et la
* recherche d'une clique maximale dans ce graphe
*
* @author jojolemariole
*/
public class TestMaximumClique {
/**
* @param args inutilise
*/
public static void main(String[] args) {
/*
* on cree un graphe aleatoire avec un certain nombre de sommets et une
* certaine probabilite de creation d'arete
*/
UndirectedGraph graphe = new UndirectedGraph(20, 0.8);
/*
* on recherche la clique maximale et on mesure le temps de recherche
*/
Clique cliqueMaximale;
long tempsDebut = System.nanoTime();
cliqueMaximale = graphe.getMaximumClique();
long tempsFin = System.nanoTime();
/*
* temps de recherche en secondes
*/
double tempsRecherche = (double) (tempsFin - tempsDebut) / 1000000000;
/*
* affichage des resultats
*/
System.out.println("Clique maximale\n---------------\n" + cliqueMaximale);
System.out.println("\nTemps de recherche : "
+ String.valueOf(tempsRecherche).replace('.', ',') + "s");
}
}
Voilà, bien sûr il y a matière à moult optimisation.
konouz
Messages postés
8
Date d'inscription
samedi 28 février 2009
Statut
Membre
Dernière intervention
31 mai 2011
11 janv. 2010 à 17:01
11 janv. 2010 à 17:01
Slt merci pour votre aide votre programmme m'as aidez bcp mais maleuresement vous m'avez pas repondu à mes messages précedents j'ai voulais juste savoir quelles sont les algorithmes qui ont traité ce probleme de clique(un etat d'art sur les noms des algorithmes et leurs complexité).
Desolée si je vous derange encore.Merci d'avance
Desolée si je vous derange encore.Merci d'avance
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
12 janv. 2010 à 09:28
12 janv. 2010 à 09:28
Bonjour,
A mon tour d'être désolé, autant fournir une implémentation "naïve" (simple et peu efficace), je suis assez conciliant pour le faire mais effectuer un travail de recherche à ta place, je crois que tout le monde te répondra non. Par contre Google est ton ami : cliquez ici pour obtenir une aide.
A mon tour d'être désolé, autant fournir une implémentation "naïve" (simple et peu efficace), je suis assez conciliant pour le faire mais effectuer un travail de recherche à ta place, je crois que tout le monde te répondra non. Par contre Google est ton ami : cliquez ici pour obtenir une aide.
