Discussion :

[anna0510]

Bonjour,
je suis débutante en programmation, et je voudrais faire une fonction qui décompose un graphe en tout les sous graphes possible (structurellement). mon graphe n'est pas orienté.

c'est a dire si j'ai un graphe a 4 noeuds et 4 arc (graphe formant un carré), les sous graphes seront : un graphe a 1 noeud, un graphe a 2 noeud et 1 arc, un graphe a 3 noeuds et 2 arc.. tout les possiblités de sous graphes appartenant a mon graphe.

l'idée que j'ai eu c'est de partir du graphe complet et d'une liste vide ou je stocke mes sous graphes. je retire un arc a chaque fois, et je met le sous graphe dans la liste.

cela entraîne deux problèmes:

1. tester si un graphe appartient déjà a la liste et donc ne pas l'ajouter, mais comment comparer deux graphe ?????

2. en enlevant un arc je peux isoler deux sous graphes

????

une autre idée c'est de faire une approche par construction, c'est a dire de partir d'un seul noeud d'ajouter a la liste puis visiter ces voisin, ajouter un autre noeud et mettre dans la liste. mais cette deuxième idée je n'ai pas su mettre en place l'algorithme

Est ce que quelqu'un peut m'aider ?? existe t il un algo qui fait cette décomposition simplement ??
est ce qu'il y a un autre moyens pour décomposer un graphe??
quelqu'un pourrait m'aider a écrire l'algorithme ?
je suis perdue

Je vous remercie infiniment.

Anna

[Freem]

Il faudrait déjà savoir comment tu as représenté tes graphes en terme d'objet.

De ce que j'ai compris (je ne connaît de la théorie des graphes que le nom), on à 3 "types" de données qui se dégagent de ton énoncé:
_ graphe
_ noeud
_ arc

Il semble qu'un graphe contienne au moins un noeud, et que dès lors que l'on ajoute un noeud, on ajoute un arc.
Si on avait 1 graphe=n noeuds+n arcs, ce serait plus simple à modéliser... Ce n'est pas le cas il semble que ce soit plutôt 1 graphe= n noeuds+(n-1) arcs, mais à lire ton énoncé, j'ai l'impression qu'en fait, chaque noeud supplémentaire possède un arc vers un noeud de référence. Je sais que tu as précisé qu'ils ne sont pas orientés, mais peu importe pour le moment.
Si je transforme un peu cette phrase, je peux obtenir: 1 graphe=n noeuds ; 1 noeud=1 noeud primitif + 1 arc ; 1 arc = 1 pointeur vers un noeud.
Du coup, je pourrai avoir 1 graphe=n noeuds = n noeuds primitifs + n pointeurs vers un noeud.
Si on met le 1er arc (celui qui appartiens au noeud originel ) à null (il ne relie rien après tout) on à effectivement N noeuds et (N-1) arcs.

En fait, c'est exactement une liste chaînée simple.
Mais pour moi ce modèle possède un problème, il n'est pas souple, et n'inclut pas la notion de sous-graphe.
Quand on parle de trucs et de sous-trucs, on finit souvent par avoir des sous-sous-trucs et ce, avec n "sous". Et pour ça, il existe un design pattern excessivement utile: design pattern composite.
En gros, c'est: 1 contenant est un contenu qui possède d'autres contenus. En terme de classes, ça fait 2 classes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
class Contenu
{
};
class Contenant: public Contenu
{
  std::vector<Contenu*> m_contenus;
};

Si je combine ce DP avec mon modèle précédent qui s'apparentait à la liste chaînée simple, j'aurai:
graphe <= Contenant
noeud <= Contenu (enfin, si on peut considérer qu'un graphe possède une relation de type EST-UN avec noeud... Comme je l'ai dis, je n'y connaît rien en graphes)
arc <= rien. Rien, parce que vu qu'on a utilisé un vector, il suffit d'estimer qu'entre chaque enfant, on à un noeud.

Ce n'est qu'une piste, je ne sais pas trop ce que tu veux faire de tes noeuds et graphes après tout... Mais je te conseille de commencer par créer les classes qui pourront contenir les données avant de penser aux algorithmes. En fait, j'ai remarqué que souvent, une fois les données bien modélisées, l'algo le plus utile, c'est : for_each.
Très sérieusement, quand les données sont modélisées au point de ne plus pouvoir les diviser/encapsuler, l'algorithme ne se situe plus dans un algorigramme, mais dans le diagramme des classes. Et il devient enfantin à écrire.
Bien sûr, c'est pas nécessairement le plus optimisé en terme de ressources, mais il faut s'avoir qu'un programme qui fonctionne lentement va plus loin qu'un programme qui bug vite (cf la fable de lafontaine avec la tortue et le lièvre )

[MABROUKI]

bonjour anna0510
comme dit par Freem

Il faudrait déjà savoir comment tu as représenté tes graphes en terme d'objet.

Il faut avoir une structure de donnees adequate pour un graph .
Regarde cet article MSDN intitule "An Extensive Examination of Data Structures Part 5: From Trees to Graphs" avec code downloadable en CSharp...

http://www.google.fr/url?sa=t&rct=j&...k9v7kaXCVImkYw
Les projets qui te concernent sont :
-GraphTester :Winform pour tester le class Graph
-skmDataStructures\Graph :contient le class Graph

Apres au cours de la construction de ton graphe "G" avec les "data" à chaque etape -k- (ajout d'un arc):
-tu crees un sous -graphe "Gk" par copie des donnees de "G" et tu ajoutes le "Gk" à ta liste de graphes...
-tu passes à l'etape k+1 suivante normalement....

bon code............