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

  FORUM HardWare.fr
  Programmation
  Java

  [JAVA]graphe+liste d'adjacence+tri topologique

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[JAVA]graphe+liste d'adjacence+tri topologique

n°382042
dorf54
Posté le 04-05-2003 à 22:27:03  profilanswer
 

en fait j'ai deja l'algo et je dois le traduire en java
probleme: -pcart en java??
          -type sommet=entier et non sommet:entier
merci pour votre aide

mood
Publicité
Posté le 04-05-2003 à 22:27:03  profilanswer
 

n°382044
Taiche
(╯°□°)╯︵ ┻━┻
Posté le 04-05-2003 à 22:28:56  profilanswer
 

Gné ? :heink:  
Tu peux la refaire en français, steuplé ? Nan passke là j'ai rien compris du tout :lol:


---------------
Everyone thinks of changing the world, but no one thinks of changing himself  |  It is the peculiar quality of a fool to perceive the faults of others and to forget his own  |  Early clumsiness is not a verdict, it’s an essential ingredient.
n°382046
dorf54
Posté le 04-05-2003 à 22:31:09  profilanswer
 

en c++ on peut faire des structures avec le pcart
j'aimerais savoir comment on fait en java
et puis j'ai un type sommet=ENTIER
idem j'aimerais savoir coment traduire ca en java

n°382049
dorf54
Posté le 04-05-2003 à 22:34:40  profilanswer
 

:??:

n°382050
Taiche
(╯°□°)╯︵ ┻━┻
Posté le 04-05-2003 à 22:36:51  profilanswer
 

Euh baaa... le pcart, je sais pas c'que c'est donc je peux pas répondre.
Par contre pour les sommets, en C++, tu faisais int sommet; Bin en Java c'est pareil [:xp1700]


---------------
Everyone thinks of changing the world, but no one thinks of changing himself  |  It is the peculiar quality of a fool to perceive the faults of others and to forget his own  |  Early clumsiness is not a verdict, it’s an essential ingredient.
n°382051
dorf54
Posté le 04-05-2003 à 22:38:38  profilanswer
 

ca je sais c'est la le probleme
c'es tu ntype sommet=ENTIER(algo)
et non  comme tu le dis sommet :entier(algo)
PS:pcart(produit cartésien=typedef en c++
 :hello:

n°382056
dorf54
Posté le 04-05-2003 à 22:43:01  profilanswer
 

typedef int Sommet ; // Les sommets sont repérés par leur numéro
j'aimerais une  traduction javaiene
 :hello:

n°382058
Taiche
(╯°□°)╯︵ ┻━┻
Posté le 04-05-2003 à 22:45:02  profilanswer
 

Ah ba non, les typedef en Java ça existe pas [:spamafote]


---------------
Everyone thinks of changing the world, but no one thinks of changing himself  |  It is the peculiar quality of a fool to perceive the faults of others and to forget his own  |  Early clumsiness is not a verdict, it’s an essential ingredient.
n°382060
dorf54
Posté le 04-05-2003 à 22:46:23  profilanswer
 

on fait comment alors en java?
nouvelle classe?
ou...

n°382064
Taiche
(╯°□°)╯︵ ┻━┻
Posté le 04-05-2003 à 22:51:29  profilanswer
 

Ba on utilise des int [:spamafote]
Si vraiment t'as rien d'autre à faire, tu peux t'amuser à créer une classe qui s'utilise comme un entier, m'enfin y a pas tellement d'intérêt.
Pourquoi t'as besoin de définir le type sommet comme un entier ? C'est juste pour la lisibilité du code ?


---------------
Everyone thinks of changing the world, but no one thinks of changing himself  |  It is the peculiar quality of a fool to perceive the faults of others and to forget his own  |  Early clumsiness is not a verdict, it’s an essential ingredient.
mood
Publicité
Posté le 04-05-2003 à 22:51:29  profilanswer
 

n°382066
dorf54
Posté le 04-05-2003 à 22:54:17  profilanswer
 

bah disons qu'apparemment faut faire comme ca pour un graphe ave c liste d'adjacence dans le but d'effectuer un tri topologique
je vais reessayé
je repasserai plus tard
si desfois tu as deja fait ca en java fais moi signe(lol)
@+

n°382132
Taz
bisounours-codeur
Posté le 05-05-2003 à 00:02:24  profilanswer
 

moi j'ai pas compris un traitre mot de Dorf :heink:
 
sauf le C++, evidemment

n°382133
dorf54
Posté le 05-05-2003 à 00:04:41  profilanswer
 

le plus simple serait peut etre que j'inscrive le code à l'ecran et voir ce qui cloche

n°382137
dorf54
Posté le 05-05-2003 à 00:07:44  profilanswer
 

[class graph]
 
public class graph
{
     
 noeud_tete []g;
    int n;
    int MAX_SOMMETS=15;
    int N_sommets=0;
 
 
 
 
 
 
 graph(int N_sommets)
 {n=N_sommets;
  g=new noeud_tete[n];
  for(int i=0; i<n;i++)
  g[i]=null;
   
 }
 
 public void tritop(graph g,int n)
 {Sommet i,j,k,top;
   
   
  Ptr_noeud ptr;
  top=-1;
  for(i=1;i<n;i++)
  {if(g[i].count==0)
     {g[i].count=top;
   top=1;
     }
  }
  for(i=1;i<n;i++)
  {if(top==-1)
   {System.out.println("Pas de tri topologique: Présence de cycle(s) !" );}
   else {j=top;
   top=g[j].count;
   System.out.println(j);
   ptr=g[j].lien;
   while(ptr!=null)
   {k=ptr.vertex;
    g[k].count=g[k].count-1;
    if(g[k].count==0)
    {g[k].count=top;
     top=k;
    }
    ptr=ptr.lien;
     
   }
         }
  }
 }
   
   
   
   
 
 
 
 public static void main (String[] args)
 {int n;
  graph g;
  g=new graph(10);
  //n=N_sommets;
  g.tritop(g,10);
   
   
  }
}
 
[class Sommet]
 
public class Sommet
{int Sommet;
 
 public Sommet()
 {Sommet=0;}
 
 public int acces_Sommet()
 {return Sommet;}
 
 
 
 
}
 
[class noeud]
 
public class noeud
{Sommet vertex;
 float duree;
 Ptr_noeud lien;
 
 public noeud()
 { vertex=null;
   duree=0;
   lien=null;}
 
 
public Sommet acces_vertex()
{return vertex;}
 
public float acces_duree()
{return duree;}
 
public Ptr_noeud acces_lien()
{return lien;}
 
}
 
[class noeud_tete]
 
public class noeud_tete
{int count;
 Ptr_noeud lien;
 
 public noeud_tete()
 {count=0;
  lien=null;
 }
 
 
 public Ptr_noeud acces_lien()
{return lien;}
 
 
 public int acces_count()
 {return count;}
 
[class Ptr_noeud]
 
public class Ptr_noeud
{Sommet vertex;
 Ptr_noeud lien;
 
 public Ptr_noeud()
 { vertex=null;
   lien=null;}
 
 
public Sommet acces_vertex()
{return vertex;}
 
 
public Ptr_noeud acces_lien()
{return lien;}

n°382142
Taz
bisounours-codeur
Posté le 05-05-2003 à 00:09:11  profilanswer
 

et alors?

n°382149
dorf54
Posté le 05-05-2003 à 00:12:08  profilanswer
 

ca marche pas et je comprends pas
enfin si tu connais un site qui a un prog en java sur le tri topologique  dans un graphe à liste d'adjacence je suis preneur
 :hello:

n°382151
Taz
bisounours-codeur
Posté le 05-05-2003 à 00:13:10  profilanswer
 

ben tu prends googgle et tu fais une recherche d'algo


Message édité par Taz le 05-05-2003 à 00:13:17
n°382156
dorf54
Posté le 05-05-2003 à 00:16:41  profilanswer
 

j'ai l'algo!!!
tout le probleme est la
d'ou mes questions de structure,pcart....

n°382158
dorf54
Posté le 05-05-2003 à 00:17:47  profilanswer
 

Le choix de représentation par les listes d'adjacence est imposé ici.
CONSTANTE:    MAX_SOMMETS = 15
DEFINITION DE TYPE:  Sommet = ENTIER
VARIABLES (GLOBALES)
 Ptr_noeud: REFERENCE/POINTEUR sur noeud
 noeud: P_CART( vertex: Sommet,
   Durée: REEL, // optionnel si réseaux avec sommets
      // à activités  
   lien: Ptr_noeud)
 noeud_tête: P_CART(  count: ENTIER,  
        // count = demi-degré intérieur du sommet courant
    lien: Ptr_noeud)
 graph: TABLEAU[1 ... MAX_SOMMETS] de noeud_tête
 N_sommets: ENTIER  
  // Nombre de sommets effectifs pour un graphe G donné
  // N_sommets <= MAX_SOMMETS
Algorithme:
----------
PROCEDURE créer_graph639()
DEBUT
 /*  A COMPLETER  cf. Fig. 6.39 de Horowitz et al. comme exemple */
 N_sommets <-- 6
FIN
PROCEDURE tritop(DR G: TABLEAU[1...MAX_SOMMETS] de noeud_tête, D N: ENTIER)
// on développe l'algorithme général du cours avec N = N_sommets à l'appel
DEBUT
 i, j, k, top: Sommets
 ptr: Ptr_noeud
 top <-- (-1) //crée une pile de sommets sans prédécesseurs
 POUR i DE 1 A N  FAIRE
  SI (G.count = 0)  ALORS
   G[i].count <-- top
   top <-- i; FSI
 FPOUR
 POUR i DE 1 A N  FAIRE
  SI (top = -1)  ALORS
   ECRIRE('Pas de tri topologique: Présence de cycle(s) !';)
  SINON
   j <-- top // dépile un sommet
   top <-- G[top].count
   ECRIRE('S',j,';  ';)
   ptr <-- G[j].lien
   TANT QUE (ptr <> NIL) FAIRE
    // décrémente le nb. de sommets successeurs de Sj
    k <-- (ptr->vertex)
    G[k].count <-- G[k].count-1  
    SI (G[k].count =  0) ALORS
     // ajoute Sk à la pile
     G[k].count <-- top
     top <-- k
    FSI
    ptr <-- (ptr -> lien)
   FTQUE
  FSI
 FPOUR
FIN  // de la procédure 'tritop'
 
// Un module appelant possible:
DEBUT
 n: ENTIER
 G: graph
 créer_graph639()
 n <-- N_sommets
 tritop(G, n)
FIN
 

n°382162
Taz
bisounours-codeur
Posté le 05-05-2003 à 00:19:44  profilanswer
 

tu te rends compete que et toncode et ton algo sont illisibles ? (tu pourrais déjà améliorer les choes en utilisant les balises code et fixed et en indentant)
apres si tu dis pas ou se situe ton problème... ça compile? ça plante, ça quoi?

n°382168
dorf54
Posté le 05-05-2003 à 00:25:03  profilanswer
 

désolé c'est une version beta(lol)
l'algo vient du prof
ca compile pas
cannot convert "int" to Sommet
[]cannot be applied to a value of type'graph'

n°382174
Taz
bisounours-codeur
Posté le 05-05-2003 à 00:27:46  profilanswer
 

Dorf54 a écrit :

désolé c'est une version beta(lol)
l'algo vient du prof
ca compile pas
cannot convert "int" to Sommet
[]cannot be applied to a value of type'graph'

en Java y a pas d'appel implicite d'un cosntructeur
donc il faut faire de l'explciit
 
truc=new Sommet(i)
 
et ta fonction tritop, j'ay comprends rien, elle à l'air d'etre membre, mais elle a un graphe en paramètre qui porte le meme nom qu'un membre... ça me parait pas tres serieux*µ. tu ferais bien de réfléchir tranquillement à tout ça
 
edit: bref va te coucher, on verra ça plus tard


Message édité par Taz le 05-05-2003 à 00:29:21
n°382177
dorf54
Posté le 05-05-2003 à 00:30:40  profilanswer
 

tu as raison
merci pour ton aide
bonne nuit
 :hello:

mood
Publicité
Posté le   profilanswer
 


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

  [JAVA]graphe+liste d'adjacence+tri topologique

 

Sujets relatifs
[JAVA] Connection à un ftp[JAVA] Socket UDP et InputStream, probleme de read
Java : Envoyer un mail protocole mapi[JAVA] L'équivalent d'un #define en java ?
[Java] Introspection et instancesImprimer un fichier (HTML) en JAVA
[Java][Livre] Apprendre ![JAVA]Plein de questions de débutant
demande aide surr une question tres precise en java(servlet)Executer une commande en JAVA
Plus de sujets relatifs à : [JAVA]graphe+liste d'adjacence+tri topologique


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