Discussion :

[ecthelion]

Bonjour,

Je dispose de fichiers textes de cette forme la:


CHEMIN 12 34 455
CHEMIN 34 67 87 123 345 345
CHEMIN 12 34
....


Chaque ligne correspond à un chemin. Chaque nombre correspond a un noeud dans un réseau. Par exemple, la premiere ligne signifie que pour aller du noeud 12 au noeud 455 il faut passer par le noeud 34. Cela signifie aussi qu'il y a un lien (une connectivité) entre 12 et 34 puis entre 34 et 455.

La deuxieme ligne possède deux fois le même noeud (345) mais, pour des raisons que je n expliquerai pas ici cela est similaire a si il y n y avait qu'une fois 345 (ces cas de figure sont presents dans mes fichiers txt)

Grace a ce fichier texte, je dois déterminer combien de liens il y a dans l'ensemble du réseau (donc l'ensemble du fichier txt) et déterminer la densité de chaque noeud (la densité correspond au nombre de liens que possède un noeud).

Débutant seulement depuis 2 semaines en perl, je ne vois pas du tout comment faire....

Selon moi il faut que je parcours chaque couple de noeud et les stocker quelque part(une hashtable?) pour ensuite compter combien de lien il y a. Dois je utiliser une hashtable ou un tableau classique? En fait je ne vois même pas comment parcourir chaque couple de noeud pour les traiter. En effet pour la premiere ligne il faut que je traite le lien 12-34 puis ensuite le lien 34-455 et avec une boucle for ca me semble difficile puisqu on ne parcours pas la ligne (ou le vecteur) un par un...

En esperant que vous ayez compris mon probleme, je vous remercie d avance pour votre aide!

[Jedai]

Le problème n'est pas tant Perl ici que de l'algorithmique... Cependant il serait préférable que tu précise certains points : quel est le poid de tes fichiers textes ? s'agit-il d'un graphe orienté ou non ?

En supposant que le graphe soit orienté et que le fichier texte fasse moins de 200 Mo disons :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#! /usr/bin/perl
use strict; use warnings;
 
my %graph;
 
while(<>){
  chomp;
  s/CHEMIN//;
  s/^\s*|\s*$//g
  my @nodes = split;
  for my $i (0..($#nodes - 1)){
    $graph{$nodes[$i]}{"$nodes[$i]-$nodes[$i+1]"} = 1;
  }
}
 
# nombre de liens :
my $links_num = 0;
for my $node (keys %graph){
  $links_num += keys %{$graph{$node}};
}
print "Le graphe a $links_num liens.\n";
 
# densité sortante pour chaque noeud (bien que je doute que ce soit ce
# que tu veux, sois plus précis)
for my $node (sort {$a <=> $b} keys %graph){
  print "Densité sortante pour $node : ".(keys %{$graph{$node}}).".\n";
}
 
# pour la densité entrante, il faut modifier légèrement la structure de %graph

--
Jedaï

[ecthelion]

Merci Jedai pour ta réponse,

Mes fichiers textes sont très gros et peuvent aller jusqu'a 5 Go...
Le graphe est non orienté, donc pour le degré ce serait uniquement le nombre de liens qui partent et viennent d'un noeud.

En revanche je n'ai pas compris ton code. Pourrais tu m'expliquer quelques points?

Je vais reprendre ton code et t'expliquer ce que j'ai compris:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
 
#! /usr/bin/perl
use strict; use warnings;
 
my %graph;
 
while(<>){
  chomp;
  s/CHEMIN//;
  s/^\s*|\s*$//g #je n'ai pas compris cette ligne...
  my @nodes = split;#jusque la tu met l'ensemble des noeuds dans un tableau (@nodes) en virant CHEMIN
  for my $i (0..($#nodes - 1)){
    $graph{$nodes[$i]}{"$nodes[$i]-$nodes[$i+1]"} = 1;
  }# tu parcours tous le tableau noeud par noeud mais la je ne comprends pas ce que tu fais avec la hashtable (le fait qu il y ait deux {} deja me perturbe beaucoup...
}
 
# nombre de liens :
my $links_num = 0;
for my $node (keys %graph){
  $links_num += keys %{$graph{$node}};
}# tu parcours toutes les clefs de la hashtable mais comme je ne sais pas vraiment ce qu'il y a dedans, je ne sais pas tellement ce que compte links_num
print "Le graphe a $links_num liens.\n";
 
 
for my $node (sort {$a <=> $b} keys %graph){#tri du graphe mais encore je ne sais pas exactement quel genre de tri
  print "Densité sortante pour $node : ".(keys %{$graph{$node}}).".\n";
}

En tout cas j'ai testé ton code et il marche presque mais pas dans tous les cas.

Par exemple pour:

CHEMIN 12956 22364 10937
CHEMIN 12956 22364 10937
CHEMIN 12956 22364 10937 2
CHEMIN 2686 1889
CHEMIN 2686 1889

il trouve 4 liens (ce qui est bon ce qui je compte bien )

mais pour:


CHEMIN 12956 22364 10937
CHEMIN 12956 22364 10937 23
CHEMIN 12956 22364 10937 2
CHEMIN 2686 1889
CHEMIN 2686 1889

il en trouve toujours 4 liens alors qu il devrait y en avoir 5 par le rajout du noeud 23

et pour:

CHEMIN 12956 22364 10937
CHEMIN 12956 22364 10937 23 23 23 23 23 23
CHEMIN 12956 22364 10937 2
CHEMIN 2686 1889
CHEMIN 2686 1889

il trouve 9 liens alors qu'il y en a toujours 5, de même il trouve une densité sortante de 5 pour 23 alors qu elle de 0 comme si il ne prenait pas en compte le fait que 23 ait été sité plusieurs fois.


Bon je sais que ca fait beaucoup de questions pour un seul post...

Merci encore pour ta réponse!

[Jedai]

Bon il manque un ; dans mon script, je ne sais même pas comment tu peux le lancer comme ça, et une fois le ; ajouté, je n'obtiens pas les mêmes résultats que toi...

CHEMIN 12956 22364 10937
CHEMIN 12956 22364 10937 23
CHEMIN 12956 22364 10937 2
CHEMIN 2686 1889
CHEMIN 2686 1889

me donne 5 liens

CHEMIN 12956 22364 10937
CHEMIN 12956 22364 10937 23 23 23 23 23 23
CHEMIN 12956 22364 10937 2
CHEMIN 2686 1889
CHEMIN 2686 1889

me donne 6 liens (ce qui est correct dans mon estimation, évidemment ça n'a pas l'air de correspondre à ce que tu veux)

Donc pour un graphe non-orienté et dans lequel on ne peut pas avoir de lien de i à i :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#! /usr/bin/perl
use strict; use warnings;
 
my %graph;
 
while(<>){
  chomp;
  s/CHEMIN//;
  # juste une substitution pour supprimer tous les espaces superflus éventuels qui gênerait la suite
  s/^\s*|\s*$//g;
  my @nodes = split;
  for my $i (0..($#nodes - 1)){
    if ( $nodes[$i] != $nodes[$i+1]){
      $graph{$nodes[$i+1]}{$nodes[$i]} = 1;
      $graph{$nodes[$i]}{$nodes[$i+1]} = 1;
    }
  }
}
 
# nombre de liens :
my $links_num = 0;
for my $node (keys %graph){
  $links_num += keys %{$graph{$node}};
}
$links_num /= 2;
print "Le graphe a $links_num liens.\n";
 
# degré pour chaque noeud
for my $node (sort {$a <=> $b} keys %graph){
  print "Degré pour $node : ".(keys %{$graph{$node}}).".\n";
}

%graph est la clé du code, il s'agit d'un hash de hash : les clés de %graph sont les noeuds du graphes et la valeur associé au noeud i est un hash dont les clés sont les noeuds auquel i est lié.

Pour ce qui est de la taille de tes fichiers, ils me semblent un peu gros... Essaie avec ce script et reviens nous voir s'il y a un problème.

--
Jedaï

[ecthelion]

Bonjour Jedai,

En fait, je n'avais pas testé ton code directement comme cela, je l'avais adapté à mon code et a cause d'une erreur de ma part je n'avais pas les bon resultats. Tes codent marchent parfaitement et je t'en remercie beaucoup.

Le temps de compilation sont corrects (environ 1 minutes pour un fichier d' 1Go) donc ca le fait.

Par contre g un peu du mal a comprendre ton code. Je me permet donc de te poser une questions:

Que font exactement ces deux lignes:

Code :

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

1
2
3
 
$graph{$nodes[$i+1]}{$nodes[$i]} = 1;
$graph{$nodes[$i]}{$nodes[$i+1]} = 1;

Je ne comprends pas très bien comment est utilisé la hashtable et a quoi correspond l'égalité à 1


Merci encore!

[Jedai]

Le hash %graph contient en fait tous les chemins du graphe. Il s'agit d'un hash à deux étages dans lequel $graph{i}{j} et $graph{j}{i} n'existent que si il y a un chemin de i à j. A vrai dire le 1 n'est qu'une valeur prise au hasard, l'important c'est que ces clés du graphe soient initialisées.

Une fois la boucle terminée, %graph contient tous les chemins du graphes, et il suffit alors de regarder les clés du hash $graph{i} pour savoir à quel noeuds i est relié.

--
Jedaï