free() invalid size très bizarre

Bonjour,

Merci par avance à tous ceux qui essaieront de m'aider, je vous poste le code et je vous dis ce qui se passe !

Code:

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
#ifndef JOHNSON_P
#define JOHNSON_P
 
#include "preprocesscl.hpp"
#include "bellmanfordcl.hpp"
#include "dijkstracl.hpp"
 
#include <vector>
#include <iostream>
 
/*
    This module provides an implementation of the Johnson's algorithm for computing
    all shortest-paths in a graph that does not contain any negative-weight cycle
*/
 
template<typename Tvertex, typename Tweight>
std::vector<Tweight> reweight(std::vector<std::vector<Tweight>>& my_graph);
/*
    Aim : compute new weights for the graph in order to later apply Dijkstra's algorithm
    Args : the graph
    Return value : none
    Complexity : O(nm)    (reduces to one invocation of Bellman-Ford algorithm)
*/
 
template<typename Tvertex, typename Tweight>
std::vector<std::vector<Tweight>> johnson(graph<Tvertex, Tweight>& my_graph);
/*
    Aim : compute all shortest-paths between all pairs of vertices of the graph
    Args : a graph
    Return value : a 2D vector that contains all shortest-paths
    Complexity : O(nmlog(n))
*/
 
// OpenCL version, kind of have to specify the parameters for the template
//void johnson(cl::CommandQueue &cmdQueue, cl::Program &prog, const int n_nodes, cl::Buffer &my_graph, cl::Buffer &distances);
 
template<typename Tvertex, typename Tweight>
std::vector<Tweight> reweight(std::vector<std::vector<Tweight>>& my_graph){
 
    std::vector<std::vector<Tweight>> copy_graph = my_graph;           // so that we do not consider all fictitious edges after this function
 
    // we add a fictitious vertex   
 
    std::vector<Tweight> fictitious_edges(std::vector<Tweight>(my_graph.size()));
    copy_graph.push_back(fictitious_edges);
    for(size_t i = 0; i < my_graph.size(); i++)
        copy_graph[i][my_graph.size()] = std::numeric_limits<double>::max() /2 ;
 
    std::vector<Tweight> new_weights = bellman_ford(copy_graph, copy_graph.size()-1); // apply bellman-ford on the graph using the fictitious vertex
                                                                                        // as the source
    for(size_t i = 0; i < my_graph.size(); i++){
        for(size_t j = 0; j < my_graph.size(); j++){
            my_graph[i][j] += new_weights[i] - new_weights[j]; // update the edges
        }
    }
 
    return new_weights;
}
 
template<typename Tvertex, typename Tweight>
std::vector<std::vector<Tweight>> johnson(std::vector<std::vector<Tweight>>& my_graph){
 
    std::vector<std::vector<Tweight>> distances(my_graph.size(), std::vector<Tweight>(my_graph.size(), std::numeric_limits<Tweight>::max()));
 
    std::vector<Tweight> weights = reweight<Tvertex, Tweight>(my_graph);
 
    for(size_t i = 0; i < my_graph.size(); i++){
        std::vector<Tweight> shortest_paths_from_i = dijkstra<Tvertex, Tweight>(my_graph, i);
        for(size_t j = 0; j < my_graph.size(); ++j){
            std::cout << "i : " << i << " j  " << j << std::endl;
            //if(shortest_paths_from_i[j] == std::numeric_limits<Tweight>::max())
            //    distances[i][j] = shortest_paths_from_i[j];
            //else
            //    distances[i][j] = shortest_paths_from_i[j] + weights[j] - weights[i];
        }
    }
 
    return distances;
}
/*
void johnson(cl::CommandQueue &cmdQueue, cl::Program &prog, const int n_nodes, cl::Buffer &my_graph, cl::Buffer &distances){
 
    cl::Kernel kernel(prog, "johnson");
    kernel.setArg(0, (cl_uint) n_nodes);
    kernel.setArg(1, my_graph);
    kernel.setArg(2, distances);
    size_t group_size = 16;
    cl::NDRange local(group_size, group_size);
    cl::NDRange global((n_nodes + group_size - 1) / group_size * group_size,
                       (n_nodes + group_size - 1) / group_size * group_size);
    cmdQueue.enqueueNDRangeKernel(kernel, cl::NullRange, global, local);
 
}
 */
#endif

Code:

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
#include "preprocesscl.hpp"
#include "bellmanfordcl.hpp"
#include "johnsoncl.hpp"
#include "dijkstracl.hpp"
#include <chrono>
//#include <omp.h>
 
 
//#include "boost/graph/johnson_all_pairs_shortest.hpp"
 
#include <iostream>
 
int main(int argc, char* argv[]){
/*
    std::vector<std::vector<double>> my_graph = parse_graph<long unsigned int, double>(argv[1]);
 
    std::vector<double> distances = bellman_ford<long unsigned int, double>(my_graph, 0);
 
    std::vector<double> new_w = reweight<long unsigned int, double>(my_graph);
 
    for(size_t k = 0 ; k < new_w.size(); k++)
        std::cout << new_w[k] << " " ;
    std::cout << std::endl << std::endl;
 
    std::vector<double> distances_d = dijkstra(my_graph, 0);
 
    for(size_t i = 0; i < distances_d.size(); i++){
        std::cout << distances_d[i] << " " ;
    }
 
    std::cout << std::endl;
*/
 
    std::vector<std::vector<double>> my_graph = parse_graph<long unsigned int, double>(argv[1]);
 
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
 
    std::vector<std::vector<double>> distances = johnson<long unsigned int, double>(my_graph);
 
    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
 
    std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
 
    std::cout << time_span.count();
    std::cout << std::endl;
 
 
    return 0;
 
}

Code:

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
#ifndef DIJKSTRA_P
#define DIJKSTRA_P
 
#include <iostream>
#include <vector>
#include "heap_generic.hpp"
#include "preprocesscl.hpp"
#include <limits>
#include <omp.h>
 
/*
 
std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
 
std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
 
        std::cout << time_span.count();
        std::cout << std::endl;
*/
template<typename Tnode, typename Tweight>
struct dijkstra_pair {
    Tnode pivot;
    Tweight key;
 
    bool operator<(dijkstra_pair &other_pair){
        return key < other_pair.key;
    }
 
    bool operator>(dijkstra_pair &other_pair){
        return key > other_pair.key; 
    }
};
 
template<typename Tnode, typename Tweight>
std::ostream& operator<<(std::ostream& out, const dijkstra_pair<Tnode, Tweight>& pair){
    out << "Vertex : " << pair.pivot << ", key : " << pair.key << std::endl;
    return out;
}
 
template<typename Tnode, typename Tweight>
std::vector<Tweight> dijkstra(const std::vector<std::vector<Tweight>>& my_graph, const Tnode node);
/*
    Aim : compute the shortest distances from source to every other vertex
    Args : the graph, represented as defined in preprocess.hpp and a source vertex
    Return value : a 1D array that contains the shortest distances
    Complexity : O(mlog(n))
*/
 
template<typename Tnode, typename Tweight>
std::vector<Tweight> initialize_distances(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source);
/*
    Aim : initialize the shortest paths, a shortest path is equal to the value of the edge between source and vertex if it exists, 0 between source
          and source, infinity represented as numeric_limits<Tweight>::max() otherwise
    Args : a graph and a source node
    Return value : a 1D array containing all initialized distances
    Complexity : O(n)
*/
 
template<typename Tnode, typename Tweight>
std::vector<Tweight> dijkstra(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source){
 
    //to store our computed distances
    std::vector<Tweight> distances = initialize_distances(my_graph, source);
 
 
    std::vector<bool> in_heap(my_graph.size(), false);                  // to keep track of nodes in the heap
    std::vector<bool> processed(my_graph.size(), false);                // to keep track of processed nodes
 
    std::vector<dijkstra_pair<Tnode, Tweight>> heap = create_heap<dijkstra_pair<Tnode, Tweight>>();        // our amazing heap for BLAZINGLY FAST
                                                                                                           // implementation
 
    insert(heap, {source, 0});             // insert the source and mark it as "in the heap"
    in_heap[source] = true;
 
    while(size_heap(heap) != 1){
 
        dijkstra_pair<Tnode, Tweight> new_pair = pop(heap);
        in_heap[new_pair.pivot] = false;                             // old min is not in the heap anymore
        processed[new_pair.pivot] = true;                            // old min is now processed           
        distances[new_pair.pivot] = new_pair.key;                    // the old key is the permanent distance between source and associated node
 
        for(size_t i = 0; i < my_graph.size(); i++){          // we check all outgoing edges of the new added vertex
 
            edge<Tnode, Tweight> current_edge{new_pair.pivot, i, my_graph[new_pair.pivot][i]};
            Tnode current_node = current_edge.head_;                                 // the head of an outgoing edge whose tail is the new added vertex
 
             // if already in the heap we update its key
            if(in_heap[current_node]){                                              
 
                Tweight old_key = delete_element(heap, current_node).key;
                Tweight new_key = std::min(old_key, distances[new_pair.pivot] + current_edge.weight_);
                insert(heap, {current_node, new_key});
            }
 
            else if(!processed[current_node]){   
 
                // otherwise we compute its key and insert it
                //Tweight new_key = compute_key(my_graph, current_node, in_heap, distances);
                Tweight new_key = distances[new_pair.pivot] + current_edge.weight_;
                insert(heap, {current_node, new_key});
 
                in_heap[current_node] = true;
            }
        }
    }
 
    return distances;
}
 
template<typename Tnode, typename Tweight>
std::vector<Tweight> initialize_distances(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source){
    std::vector<Tweight> distances(my_graph.size(), std::numeric_limits<Tweight>::max()/2);                  // std::numeric_limits<int> causes dist[smth] 
                                                                                    // + stuff to be -X which is always less than current key
    distances[source] = 0;
    for(size_t i = 0; i < my_graph.size(); i++)
        distances[my_graph[source][i]] = my_graph[source][i];
 
    return distances;
}
 
#endif

Le premier fichier contient deux fonctions une fonction qui permet de calculer des valeurs pour la deuxième qui perform l'algorithme de johnson.

Le main qui ne fait qu'appeler johnson et qui record le temps que ça prend :).

Le troisième qui contient la fonction qui perform l'algorithme de dijkstra.

Voici l'erreur qui me rend fou : free(): invalid next size (fast): 0x0000000001d3e840 ***

Le plus dingue : l'erreur intervient dans la boucle :

Code:

1
2
3
4
5
6
7
8
9
10
for(size_t i = 0; i < my_graph.size(); i++){
        std::vector<Tweight> shortest_paths_from_i = dijkstra<Tvertex, Tweight>(my_graph, i);
        for(size_t j = 0; j < my_graph.size(); ++j){
            std::cout << "i : " << i << " j  " << j << std::endl;
            //if(shortest_paths_from_i[j] == std::numeric_limits<Tweight>::max())
            //    distances[i][j] = shortest_paths_from_i[j];
            //else
            //    distances[i][j] = shortest_paths_from_i[j] + weights[j] - weights[i];
        }
    }

Lorsque i = 3. Cependant (oui vous allez voir c'est marrant), si à la place de i je mets 0 tout va bien (j'applique my_graph.size() l'algo de dijkstra avec le node 0 comme node source, vu que c'est pas celui là qui plantait ça me emble logique). Si à la place je mets 1 ça fonctionne, si à la place je mets 2 ça fonctionne une fois puis au second appel de dijkstra ça plante (alors que à la base c'est pas l'itération pour i = 2 qui plante), si je mets 3 ça fonctionne (c'est l'itération qui plantait...). Si je mets 4 5 6 ou 7 ça marche (mon petit exemple ne contient que 8 nodes).

Quelq'un a t-il une idée de ce qu'il se passe ? J'ai lu sur le forum et ailleurs que cette erreur survient lors de dépassements de mémoire, de double free, de tentative d'accès à de la mémoire non allouée...

Cependant ici l'itération qui plante de base c'est lorsque j'appelle dijkstra<Tvertex, Tweight>(my_graph, 3), qui ne plante pas dans si j'écris dans ma boucle dijkstra<Tvertex, Tweight>(my_graph, 1 ou 2 ou 3 jusqu'à 7)

Donc je me dis, peut-être que mes itérations 0 ou 1 ou 2 provoquent des choses qui font que pour i = 3 ça plante (raison pour laquelle si je commence par la 3 ça ne plante pas par exemple). Cependant ma fonction dijkstra ne touchent pas à ses arguments déclarés "const" elle ne fait que retourner un std::vector<Tweight> (vous pouvez penser Tweight = double si vous voulez), du coup j'ai pas la moindre idée de ce qu'il se passe...

Merci encore à tous

Je vois des tailles employées qui ne correspondent pas à celles de l'objet manipulé. Pour moi que la matrice soit carrée mérite un assert pour le clarifier.

Sinon, ton problème est un boulot pour valgrind, ou mieux le mode sanatize=address de clang (les derniers gcc l'ont aussi maintenant). Passer ta SL en mode checké peut être pas mal aussi.

Bonsoir et merci Monsieur Hermitte, des tailles employées qui ne correspondent pas à l'objet manipulé ? Puis-je savoir où ? car c'est le premier truc que j'ai cherché à vérifier, j'ai tout print avant la dernière boucle que j'ai montré (celle dans laquelle on appelle dijkstra) et jusque là le graphe contient exactement ce qu'il doit contenir, il fait une taille de 8 par 8. Est-ce que vous avez un tuto simple pour valgrind ? Je suis assez pressé avec ce projet je voudrais bien trouver l'erreur rapidement.

Merci encore

Typiquement, entre la ligne 46 et 47 du premier fichier, cela mérite un

Code:

assert(copy_graph[i].size() > my_graph.size());

Je n'ai pas tout regardé, mais s'il doit y avoir d'autres "évidences" du genre, les énoncer clairement n'est jamais une perte de temps -- un collègue avait des problèmes similaires il y a une 10aines de jours, et ... il a pu constater l'efficacité du bestio pour trouver l'endroit où ce qu'il croyait être vrai ne l'était pas.

Et si c'est évident, raison de plus pour l'affirmer. En tant que relecteur qui ne connait rien au problème voir une taille sortie de nulle part utilisée ailleurs choque. BTW, si l'objectif est de changer le dernier élément de la colonne, un

Code:

copy_graph[i].back() = k_half;

suffirait.

Pour valgrind, il suffit de le lancer et de traiter les problèmes dans l'ordre. Si le programme se lançait avec "./prog param1 -o param2", il suffit de faire "valgrind ./prog param1 -o param2". C'est déjà un bon début (on peut aussi lui dire de s'arrêter à la première erreur rencontrée et de passer en debugage à ce moment là). Mais si c'est bien un problème d'écriture hors bornes (ce que je soupçonne vu que je ne vois pas de trace de pointeur brut dans le code donné), le mode sanatize=address peut être bien plus riche en info.

Et ne pas négliger la 3e alternative qui consiste à passer la STL en mode checké. J'insiste. Valgrind, tout le monde en parle. Mais ça génère beaucoup de bruit, les contextes ne sont jamais clairs si on ne force pas le debug à la première erreur trouvée, et ça peut être bien trop lent. Alors qu'il y a des outils qui vont faire du failfast et permettre de disposer simplement du contexte lors de l'exécution (typiquement un coredump)

Rebonsoir, j'ai commencé par tester ton assert et tu avais raison, ça a pété. Je ne sais pas trop pourquoi sans doute je m'y suis mal pris. Ca ne change pas vraiment la dernière colonne, ça en rajoute une. Donc comme back() ça touche à la dernière colonne existante je crois pas que ça va marcher. Mais merci :)

Pour rajouter une colonne, c'est push_back() alors.