Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2237 connectés 

  FORUM HardWare.fr
  Programmation
  Java

  [Java][projet] Graphes planaires...

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[Java][projet] Graphes planaires...

n°137436
Tetedeienc​h
Head Of God
Posté le 11-05-2002 à 11:22:30  profilanswer
 

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 !


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v9 OUT ! 5 tests : 2 CPU, 2 GPU, 1 Alim ! 2 Benchmarks : CPU and Me
mood
Publicité
Posté le 11-05-2002 à 11:22:30  profilanswer
 

n°137442
[SDF]Poire
Vive Grumly
Posté le 11-05-2002 à 11:33:51  profilanswer
 

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

n°137448
darklord
You're welcome
Posté le 11-05-2002 à 12:05:12  profilanswer
 

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?


---------------
Just because you feel good does not make you right
n°137449
darklord
You're welcome
Posté le 11-05-2002 à 12:06:03  profilanswer
 

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.


---------------
Just because you feel good does not make you right
n°137451
verdoux
And I'm still waiting
Posté le 11-05-2002 à 12:10:03  profilanswer
 

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

n°137458
Tetedeienc​h
Head Of God
Posté le 11-05-2002 à 12:42:27  profilanswer
 

Verdoux : d'enfer le lien :love: 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 :love:


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v9 OUT ! 5 tests : 2 CPU, 2 GPU, 1 Alim ! 2 Benchmarks : CPU and Me
n°137477
[SDF]Poire
Vive Grumly
Posté le 11-05-2002 à 13:47:37  profilanswer
 

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  :D  
Suite de discution en PV si suite


---------------
Des bons sites pour Delphi? http://forum.hardware.fr/forum2.php3?post=16838&cat=10 -- informaticien -- http://www.z0rglub.com/phpwebgallery/ -- Delphi :love:
n°137481
benou
Posté le 11-05-2002 à 13:49:44  profilanswer
 

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 ?


---------------
ma vie, mon oeuvre - HomePlayer
n°137573
darklord
You're welcome
Posté le 11-05-2002 à 18:02:29  profilanswer
 

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

n°137575
darklord
You're welcome
Posté le 11-05-2002 à 18:02:58  profilanswer
 

[SDF]Poire a écrit a écrit :

 
Prouve le  :D  
Suite de discution en PV si suite  




 
si tu veux. Que veux tu savoir exactement?

mood
Publicité
Posté le 11-05-2002 à 18:02:58  profilanswer
 

n°137609
[SDF]Poire
Vive Grumly
Posté le 11-05-2002 à 19:15:43  profilanswer
 

DarkLord a écrit a écrit :

 
 
si tu veux. Que veux tu savoir exactement?  




En private le topic a rien à voir avec ça


---------------
Des bons sites pour Delphi? http://forum.hardware.fr/forum2.php3?post=16838&cat=10 -- informaticien -- http://www.z0rglub.com/phpwebgallery/ -- Delphi :love:
n°137615
Tetedeienc​h
Head Of God
Posté le 11-05-2002 à 19:46:48  profilanswer
 

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 ;)


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v9 OUT ! 5 tests : 2 CPU, 2 GPU, 1 Alim ! 2 Benchmarks : CPU and Me
n°137617
Tetedeienc​h
Head Of God
Posté le 11-05-2002 à 19:49:01  profilanswer
 

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 :)


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v9 OUT ! 5 tests : 2 CPU, 2 GPU, 1 Alim ! 2 Benchmarks : CPU and Me
n°137793
benou
Posté le 12-05-2002 à 12:58:56  profilanswer
 

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.


---------------
ma vie, mon oeuvre - HomePlayer
n°137794
darklord
You're welcome
Posté le 12-05-2002 à 13:00:06  profilanswer
 

benou >>>  :jap:


---------------
Just because you feel good does not make you right
n°137797
benou
Posté le 12-05-2002 à 13:08:51  profilanswer
 

Tetedeiench a écrit a écrit :

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.




arrête de parler de struct : t'es pas en C ! :o ;)
 
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]


---------------
ma vie, mon oeuvre - HomePlayer
n°137805
verdoux
And I'm still waiting
Posté le 12-05-2002 à 13:19:43  profilanswer
 

Tetedeiench a écrit a écrit :

Et comparer l'égalité de deux graphes, avec la struct, c sympa a programmer... je m'y risquerai moyen.




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]

n°137857
benou
Posté le 12-05-2002 à 15:55:57  profilanswer
 

benou a écrit a écrit :

comparer l'égalité avec la classe que je t'ai proposé, c'est pas bien compliqué ...




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


---------------
ma vie, mon oeuvre - HomePlayer

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Java

  [Java][projet] Graphes planaires...

 

Sujets relatifs
[JAVA] comment utilise-t-on "package" ???[JAVA] Stockage constantes dans un tableau Object[]
[java] comment separé l affichage du traitement[java-script] validation enter
[RESOLU][java] recupérer la taille d'un fichier[ Unix Java ] socket - transfert limité à 256 octets ?!!!
[java] peut etre con mais j aimerai comprendre[java] afficher une page html à l'intérieur d'une applet
[JAVA]probleme de transtypage de Object vers autre chose[JAVA] Créer un jar exécutable
Plus de sujets relatifs à : [Java][projet] Graphes planaires...


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR