Discussion :

[twilightZone]

Bonjour,

Je dois traiter un graphe simple, c.a.d. un graphe qui n'est pas cyclique et qui ne possède que des relations simple (sans poids et symétrique) entre ses nœuds.
Je dois trouver le nœud, le plus "central" de mon graphe qui me permettra d'y lâcher un virus et de contaminer le plus rapidement possible tous mes nœuds.
Dans l'exemple codé en dur dans mon code, le nœud le plus central est le nœud 1 qui contaminera tous les autres nœuds en 5 liaisons maximales.

Pour trouver le résultat, j'utilise l'algorithme de Floyd_Warshall qui me donne les plus courts chemins entres toutes les paires de sommets.
Ainsi dans la matrice calculées, je regarde la plus longue liaison. Dans mon exemple, il s'agit de
graphe[0][5] =graphe[5][0] = 10
Mon nœud se trouve donc entre le nœud 0 et le nœud 10 et le temps de propagation est 10/2 = 5

Mon programme fonctionne très pour 3000 liaisons et 3000 nœuds (quelques minutes de calcul), mais je dois pouvoir l'utiliser pour 200000 liaisons et 200000 nœuds.
Dans ce cas, mon algorithme ne fonctionne plus, rien que l'allocation en mémoire de la matrice est de plusieurs Gigas.

Quelles sont les pistes que je dois suivre, y a t-il un algorithme qui me permettent de découper mon graphe en sous-graphe et comment puis-je faire ??
Comme le graphe n'est pas bouclé, cela doit être possible.

Si vous avez des idées je suis preneur.

Merci

Code C++ :

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//
//  main.cpp
//  Floyd_Warshall
//
#include <stdio.h>
#include <limits.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */
using namespace std;    /* pour enlever std:: */
 
 
int main(int argc, const char * argv[])
{
    // on a 13 relations
     int n= 13;
 
    // on définit un vecteur de vecteurs qui contient les relations
    vector< vector<int> > vec(n, vector<int>(2));
 
    // le noeud 8 est relié avec le noeud 6 dans les 2 sens et sans poids
    vec[0]= {6, 8};
    vec[1]= {13, 1};
    vec[2]= {1, 12};
    vec[3]= {0, 3};
    vec[4]= {13, 11};
    vec[5]= {9, 13};
    vec[6]= {2, 5};
    vec[7]= {12, 10};
    vec[8]= {4, 9};
    vec[9]= {7, 2};
    vec[10]= {8, 7};
    vec[11]= {3, 4};
    vec[12]= {1, 6};
 
 
    // 0--3--4--9--13--1--6--8--7--2--5
    //              !  !
    //             11  12--10
 
 
 
    // la taille de la matrice (noeud 0 à noeud 13)
    int sizeArray = 14;
 
    // 999999999 est l'infini
    vector< vector<int> > graphe(sizeArray, vector<int>(sizeArray, 999999999));
 
    // la diagonale est forcément à 0
    for(int i=0; i < sizeArray; i++)
        graphe[i][i]=0;
 
 
    // on relit la liste de relation en les mettant dans le graphe
    int perso1, perso2;
 
    for (int i =0; i < n; i++) {
        perso1 = vec[i][0];
        perso2 = vec[i][1];
 
        // le poids des liaisons est uniforme (tjs 1)
        // la matrice est symétrique
        graphe[perso1][perso2] = 1;
        graphe[perso2][perso1] = 1;
    }
 
 
    // Floyd-Warshall
    for(int k = 0; k < sizeArray; k++)
        for(int i = 0; i < sizeArray; i++)
            for(int j = 0; j < sizeArray; j++)
                if(graphe[i][j]>graphe[i][k]+graphe[k][j])
                    graphe[i][j]=graphe[i][k]+graphe[k][j];
 
 
    // Impression de la matrice finale
    for(int i = 0; i < sizeArray; i++){
        for(int j = 0; j < sizeArray; j++)
            cout << graphe[i][j] << " ";
        cout << endl;
    }
 
    // la matrice résultat
    /*
     0  5  9  1  2 10  6  8  7  3  7  5  6  4
     5  0  4  4  3  5  1  3  2  2  2  2  1  1
     9  4  0  8  7  1  3  1  2  6  6  6  5  5
     1  4  8  0  1  9  5  7  6  2  6  4  5  3
     2  3  7  1  0  8  4  6  5  1  5  3  4  2
    10  5  1  9  8  0  4  2  3  7  7  7  6  6
     6  1  3  5  4  4  0  2  1  3  3  3  2  2
     8  3  1  7  6  2  2  0  1  5  5  5  4  4
     7  2  2  6  5  3  1  1  0  4  4  4  3  3
     3  2  6  2  1  7  3  5  4  0  4  2  3  1
     7  2  6  6  5  7  3  5  4  4  0  4  1  3
     5  2  6  4  3  7  3  5  4  2  4  0  3  1
     6  1  5  5  4  6  2  4  3  3  1  3  0  2
     4  1  5  3  2  6  2  4  3  1  3  1  2  0
     */
 
    return 0;
}

[DonQuiche]

Bonjour. D'abord je rechercherais les bords du graphe (noeuds n'ayant qu'une seule relation).

Puis j'exécuterais une contamination à l'envers:
* à la première génération on commence avec les bords
* à chaque génération on contamine les voisins pas encore contaminés.
* si un noeud n'a aucun voisin à contaminer, il est promu meilleur centre à ce stade.

Code c# :

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
var bords = noeuds.Filter(noeud => noeud.Voisins.Count == 0)
 
var contaminés = bords;
foreach (var contaminé in contaminés) contaminé.EstContaminé = true;
 
Noeud centre = null;
while (contaminés .Count != 0)
{
    var nouveauxContaminés = new List<Noeud>();
 
    foreach (var contaminé in contaminés ) 
    {
          if (!ContaminerVoisins(contaminé, nouveauxContaminés)) centre = contaminé;
    }
 
    contaminés = nouveauxContaminés;
}
 
 
bool ContaminerVoisins(Noeud contaminé, List<NoenouveauxContaminés)
{
     var voisinContaminé = false
     foreach(var voisin in contaminé.voisins)
     {
          if (voisin.EstContaminé) continue;
          voisin.EstContaminé = true;
          voisinContaminé = true;
          nouveauxContaminés.Push(voisin);
     }
     return voisinContaminé
}

[FR119492]

Salut!

l'allocation en mémoire de la matrice est de plusieurs Gigas

Est-ce que la matrice est pleine ou creuse?
Jean-Marc Blanc

[souviron34]

Dans ce cas, mon algorithme ne fonctionne plus, rien que l'allocation en mémoire de la matrice est de plusieurs Gigas.

Si ton exemple est bon, cela veut dire que tu as des valeurs entières. Mais même si ce n'est pas le cas et que ce sont des réels, y-a-t-il un "range" de valeur ?

Si oui, tu peux alors faire une "compression" du style GIF, une table indexée : la liste de tes valeurs, et enuite la vraie matrice, mais n'ayant besoin que de N bits (suffisant pour réprésenter les valeurs différentes)..

Passer d'un entier 32 bits à un entier 8 bit, ça gagne pas mal. Encore plus si c'est du 64....

[ToTo13]

+1 avec DonQuiche, je ferai l'équivalent d'un érodé ultime : tu pars des bords et tu vas vers le centre.
Attention qu'il peut alors y avoir plusieurs maxima.

[DonQuiche]

+1 avec DonQuiche, je ferai l'équivalent d'un érodé ultime : tu pars des bords et tu vas vers le centre.
Attention qu'il peut alors y avoir plusieurs maxima.

J'avais songé au problème et conclu qu'en fait il ne pouvait y avoir que deux maximas et forcément contigus.

J'avais tort et cela met à mal cette méthode. Si on considère le graphe suivant :

Code :

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

1
2
3
o     o     o
o     o     o
oooXoooooXooo

X sont les deux centres produits. Et aucun des deux n'est le centre. Je présume qu'en relançant l’algorithme avec une contamination depuis les centres trouvés plutôt que les bords tant qu'on n'a pas un unique centre ou deux centres contigus on finira par obtenir le vrai centre mais on doit pouvoir faire mieux.

[kolodz]

Question stupide :

As-tu penser à faire une simplification du problème par création de custer ?

Je m'explique :
Si tu pars de tes 200 000 nœuds, il n'y a aucune chance que tu arrive à faire tout les calculs proprement.
Cependant, si tu fait des clusters regroupant une centaines de nœuds et que tu calcule la contaminations sur ces clusters. Cela fait revenir ton problème dans ta zone des 3000 éléments à contaminer.
La construction des clusters devra cependant être un minimum intelligente ! Une fois que tu as trouver le cluster à contaminer en premier tu peux trouver le nœud dans ce cluster à contaminer. Normalement, tu ne trouvera pas le nœud optimal, mais l'un des ses voisins.

Cordialement,
Patrick Kolodziejczyk.