Hello
 
On est sur un projet en java consistant a déterminer si un graphe est planaire... le but étant d'optimiser le programme a fond pour avoir le truc le + efficace possible.
 
Un graphe, c'est betement des sommets (des points quoi) reliés entre eux par des segments, et le but est de déterminer si on peux dessiner legraphe sans qu'aucun des segments se croise.
 
On pensait utiliser principalement la recherche de K5 et K3,3 pour démonrer qu'il l'est  qu'il ne l'est pas .
 
Pour modéliser nos graphes, contrairement aux autres qui ont tous fait des struct de fous avec des pointeurs, nous on utilise juste... des matrices.
 
Si il y a 5 sommet on utilise une matrice 5x5 et si il y a un 1 dans la case (2,4) ca signifie que les sommets 2 et 4 sont reliés... ca nous semble bcp  pratique pur la suite.
 
Pourriez vous nous aider :
 
-A trouver des algorithmes efficaces pour savoir si un graphe est connexe, biparti ?
 
-Nous filer quelques idées d'optimisation sympa pour éviter de dérouler des algos trop gros Style teste d'abord si il est machin car si il est il est pas planaire, etc
 
Ca nous aiderai grandement
 
Et aussi une petite question : on a fait une classe java implémentant des graphes de base, et on est obligé d'en faire une pour bosser sur des graphes biparti... en partant de la première.
 
Et la ou je me paume tjs, c'est dans l'utilisation d'extends ou d'implement...
 
Faudrait faire comment ? Sachant qu'un graphe biparti n'est finalement qu'un cas particulier du premier
 
Merci d'avance !

ID d'optimisation : Changer de langage    
Ok je sors... de toute façon moi et le java....
 

Dans ce genre de problèmes, le choix de la structure de données est cruciale et aura des conséquences sur l'ensemble de la réalisation du problème.
 
En ce qui concerne les optimisations, c'est assez indépendant de Java et tu devrais jeter un oeil sur les fonctions mathématiques qui te permet de jouer avec des graphes et en faire une algorithme précise. Basé sur ces optimisations il y a des petits trucs qui te permettront en Java d'améliorer les choses mais ce ne sera pas transcendant.
 
Pour implements et extends c'est très simple. Lorsque tu utilises implementens cela veut dire que tu implémente une interface (une façette publique pour une fonctionnalité donnée). Extends lui est utilisé lorsque tu veut SPECIALISER le comportement d'un objet (d'une classe).
 
Par exemple Carre extends Rectangle parce qu'un carré est un rectangle particulier.
 
Est ce plus clair?

et pour la réflexion de poire t'es bien peu au courant pour dire encore que Java est lent
 
La boite dans laquelle je travaille a un système en production full Java.

Un petit article sur un des algos:
http://130.179.24.217/G&G/articles/Planarity.pdf

Verdoux : d'enfer le lien je vais potasser ca
 
Darklord : tres clair, donc nous on doit faire un extends, c bien ce qui me semblait (et merci pour les explications).
 
notre structure est évidemment pas mal facile a utiliser car pour enlever un sommet et tous ses arcs suffit de virer une ligne & une colonne a ntore matrice... ou dire au programme de l'ignorer
 
Pour ne ps avoir de recopie de l'objet
 
Merci tous, si d'autres ont des super liens comme celui de verdoux, je suis vraiment preneur

DarkLord a écrit a écrit : et pour la réflexion de poire t'es bien peu au courant pour dire encore que Java est lent   La boite dans laquelle je travaille a un système en production full Java.

Prouve le    
Suite de discution en PV si suite

Tetedeiench a écrit a écrit : Hello Pour modéliser nos graphes, contrairement aux autres qui ont tous fait des struct de fous avec des pointeurs, nous on utilise juste... des matrices.

ca me parait super simple ...
 
public class Sommet {
   private Set liaison;
 
   ...
 
   public lier(Sommet s) {
      liaison.add(s);
   }
   ...
}
 
ca c'est pour un sommet d'un graphe tout bête avec liaisons unidirectionnelles. C'est à peine plus complqieuer d'en faire un bi-directionnel.
 
Ca me parait plus simple à manipuler que ta matrice, nan ?

benou >>> absolument. Ca c'est une véritable architecture objet

[SDF]Poire a écrit a écrit :   Prouve le     Suite de discution en PV si suite

 
si tu veux. Que veux tu savoir exactement?

En private le topic a rien à voir avec ça

benou a écrit a écrit :   ca me parait super simple ...   public class Sommet {    private Set liaison;      ...      public lier(Sommet s) {       liaison.add(s);    }    ... }   ca c'est pour un sommet d'un graphe tout bête avec liaisons unidirectionnelles. C'est à peine plus complqieuer d'en faire un bi-directionnel.   Ca me parait plus simple à manipuler que ta matrice, nan ?

 
C'est vachement moins pratique...
 
Tu supprimes un sommet, tu va niquer ta struct, et tu va devoir te balader dans toutes tes autres structs pour enlever les occurences des arcs allant sur l'objet que tu as créé... ou admettre les "trous", enfin chainons ne voulant rien dire, dans ta liste chainée.
 
Nous, on prends la matrice, on lui enleve une ligne et une colonne, et fini.
 
Pareil, si tu veux savoir tous ceux qui sont reliés a ton sommet, tu va devoir te balader dans ta liste chainée... nous on renvoie betement une ligne de notre matrice

Le but du projet n'est pas trop de faire de la prog objet (deja faite en TP, maitrisée, c bon on a compris...)
 
c'est plus de la complexité ce projet... d'ou les techniques les + simples possibles
 
La struct est magnifique je suis d'accord et ca a été mon premier reflexe car ct + "joli". mais la matrice, bien que bcp + formelle, est aussi bcp + efficace...
 
Et comparer l'égalité de deux graphes, avec la struct, c sympa a programmer... je m'y risquerai moyen.
 
Avec ma solution, c'est permuter des lignes/colonnes et trouver une matrice identique... quitte a faire toutes les permutations possibles.
 
Et ca, c'est deja + sympa a programmer

Tetedeiench a écrit a écrit :   Tu supprimes un sommet, tu va niquer ta struct, et tu va devoir te balader dans toutes tes autres structs pour enlever les occurences des arcs allant sur l'objet que tu as créé... ou admettre les "trous", enfin chainons ne voulant rien dire, dans ta liste chainée. Pareil, si tu veux savoir tous ceux qui sont reliés a ton sommet, tu va devoir te balader dans ta liste chainée... nous on renvoie betement une ligne de notre matrice

bha nan ... si tu veux supprimer un sommet, tu as juste à délier tous les sommets auxquels sont liés ce sommet. Hors, ton graphe a des liaisons bi-directionnels, donc tu as juste à demander à chaque sommet qu'il y a dans la liste de liason de supprimer la liaison vers le sommet à supprimer.  
 
ensuite, si tu veux savoir quels sont les sommets liés à un sommet, tu as juste à retourner ton Set ...
 
franchement, je crois que tu t'embête pour rien.
 
En plus, pour parler de liste chainées, tu dois être un ex-programmeur C. Ca explique un peu ton raisonnement : en C on se fait vachement chier avec la représentation mémoire des types. En Java, c'est bcp plus simple :  
 
Un sommet c'est quoi ? => un "truc" qui est relié à un ensemble d'autres  "trucs"
En Java, un sommet c'est quoi ? => un objet référençant un ensemble d'objet du même type.

benou >>>  

arrête de parler de struct : t'es pas en C !
 
comparer l'égalité avec la classe que je t'ai proposé, c'est pas bien compliqué ...
 
Sinon, tu as pensé à l'occupation mémoire de ta matrice ? Si tu commence à gérer des graphe de plusieurs milliers de sommets, ta matrice va être plutot gourmande en mémoire ...

[jfdsdjhfuetppo]--Message édité par benou le 12-05-2002 à 13:12:13--[/jfdsdjhfuetppo]

Et si on fait une permutation circulaire du nommage des sommets, la matrice va être différente alors que le graphe est identique, non ?

[jfdsdjhfuetppo]--Message édité par Verdoux le 12-05-2002 à 15:59:11--[/jfdsdjhfuetppo]

après réflexion, c'est pas si simple que ca ... mais avec ta matrice, je ne pense pas que ca le soit plus ...