Discussion :

[kader58]

Je voudrais résoudre le système d'équations décrit dans le fichier en attachement, il s'agit d'un graphe orienté dont il faut trouver la fonction de distribution du flot au niveau de chaque noeud.
Pour router un flot à travers tous les chemins sortants on calcule une fonction de distribution pour chacun de ces chemins. Au début en suppose que tous les poids des liens sont égaux à 1.
Pourriez-vous me dire si la matrice est bien construite?
Merci

Code java :

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
       public double[][] trafficDistribution(double[][] linkweights) throws IOException, InvalidDomainException{
           System.out.println("T R A F F I C D I S T R I B U T I O N \n");
           String fileName = "test-domain1.xml";
           Domain domain = (Domain) DomainFactory.loadDomain(fileName);
           SimplifiedDomain sDomain = SimplifiedDomainBuilder.build((be.ac.ulg.montefiore.run.totem.domain.model.Domain) domain);
//           In in = buildSPInputFile(sDomain);
//           EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
 
           /**
            * allSp represents all-pairs shortest paths in edge-weighted digraphs
            *  where the edge weights are nonnegative.
            */
 
           DijkstraAllPairsSP allSp = new DijkstraAllPairsSP(G);
 
           double h[][][] = new double [G.V()][G.V()][G.V()];
           double[] distTo = new double[G.E()];
           for (int v = 0; v < G.V(); v++)
               distTo[v] = Double.POSITIVE_INFINITY;
           double shortestPathGap;
           /*
            * get all shortest paths
            */
           DijkstraSP[] all = allSp.getAll();
 
 
           for(int i = 0;i<G.V();i++)
               for(int j = 0;j<G.V();j++)
                   for(int l = 0;l<G.V();l++)
                       h[i][j][l]=Double.POSITIVE_INFINITY;
//           compute distance gap for every edge
           /**
             * Computes a shortest paths tree from <tt>s</tt> to every other vertex in
             * the edge-weighted digraph <tt>G</tt>.
             * 
             **/
 
 
           /**
            * ici on calcul h pour chaque noeud
            */
           for (int u = 0; u < G.V(); u++) {
 
 
                for (int t = 0; t<G.V(); t++){
                   //                   StdOut.printf("%d to %d (%.2f)  ", u, t, all[u].distTo(t));
 
                   for(int v=0; v<G.V(); v++){
                       /**
                        * t est le voisin direct de v
                        */
 
  //                       if(isIncidentTo(G.adj(u), v)){
//                           h[u][v][t]=getWeight(all[v], all[t]);
                           h[u][v][t]=all[v].distTo(t) + getWeight(all[u], v) - all[u].distTo(t);
 
//                       }
                   }
               }
           }
           //           StdOut.println();
 
           }
 
           // en final
           /**
            * G.V() nombre de noeuds
            */
           // loop over t
           double[][][] gamma = new double[G.V()][G.V()][G.V()];
           double[][] equivalent_number = new double[G.V()][G.V()];
           for (int t = 0; t < G.V(); t++) {
               double matrix [][] = new double[G.V()][G.V()];
               final double[] constants = new double[(G.V())];
               for (int row=0; row < G.V(); row++) {
                   for (int col=0; col < G.V(); col++) {
                       matrix[row][col] = 0;
                   }
               }       
               for (int u = 0; u<G.V(); u++){
                   if(t == u){
                       constants[u] = 1;
                   }
                   else{
                       constants[u] = 0;
                   }
                   //                   StdOut.print(" "+constants[u]+" \n");
                   if (u==t){
                       matrix[u][t]=1;
                       continue;
                   }
                   for (int v = 0; v < G.V(); v++) {
                       if(u==v)
                           matrix[u][v] = -1;
                       else   
                           matrix[u][v]=Math.exp(-h[u][v][t]);
 
                   }
               }
               final RealVector vector = new ArrayRealVector(constants);
               RealMatrix m = new Array2DRowRealMatrix(matrix);
 
               DecompositionSolver solver = new org.apache.commons.math3.linear.LUDecomposition(m).getSolver();
               RealVector solution = solver.solve(vector);
               for (int k = 0; k < vector.getDimension(); k++) {
                   //                       System.out.println("entry"+k + ":"+solution.getEntry(k) + " \n");
               }
               //              System.out.println("SOLVE SYSTEM \n");
               for (int u = 0; u<G.V(); u++){
                   //                   StdOut.print(" ENTRY "+t+"->"+u);
                   equivalent_number[u][t]=solution.getEntry(t);
                   //                   StdOut.print(" " + solution.getEntry(t)+" ");
               }
               //               StdOut.println();
           }
           for (int u = 0; u<G.V(); u++){
               for (int t = 0; t<G.V(); t++){
                   for (int v = 0; v<G.V(); v++){
 
                       //                       if(all[u].distTo(t) > all[v].distTo(t))
                       gamma[u][v][t] = equivalent_number[v][t]*Math.exp(-h[u][v][t]) ;
                       //                       else
                       //                           gamma[u][v][t] = 0;
                       StdOut.print(" "+gamma[u][v][t]+ " ");
 
                   }
 
               }
 
           }
        }

[kolodz]

Bonjour,

Tu aurai dû poster ce message dans la section Java. Car cela est plus lié à la justesse de ton implémentation qu'une question d'algorithme pur.

Personnellement, je n'ai rien vue de choquant dans ton implémentation. Cependant, il serai bon d'avoir des cas de test pour vérifier ton implémentation. Avec quelques test unitaire tu devrais avoir une confiance suffisante dans ton code. Pour Java, utilise JUnit. (Il y a des tutoriels sur le site au besoin.)


Cordialement,
Patrick Kolodziejczyk.

Note : Sachant que tu n'es justement pas dans la section Java, il est nécessaire d'indiquer le langage utilisé quand tu utilise la balise [code] de la manière suivante [code=java]

[kader58]

Merci patrick pour ta réponse