IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

BOOST graph cc1plus: out of memory allocating


Sujet :

C++

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2011
    Messages
    338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2011
    Messages : 338
    Points : 0
    Points
    0
    Par défaut BOOST graph cc1plus: out of memory allocating
    Bonjour, je travail avec BOOST pour un problème de data mining.
    donc après la lecture d'un fichier qui contient des graphes (de ce type
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    t # 0
    v 0 5
    v 1 9
    v 2 8
    v 3 7
    v 4 2
    e 0 1 4
    e 1 2 68
    e 1 4 12
    e 3 2 18
    ) je passe a la création et l'insertion des graphes dans un vecteur, ce vecteur sera par la suite utilisé pour faire des tests.
    bref, voila le code source :
    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
    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
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    #include <boost/graph/adjacency_list.hpp>
    #include <boost/graph/vf2_sub_graph_iso.hpp>
    #include <boost/algorithm/string/split.hpp>
    #include <boost/algorithm/string/classification.hpp>
    #include <fstream>
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <ctime>
    #include <queue> // std::queue
    // for mmap:
    #include <sys/mman.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    using namespace std;
    using namespace boost;
     
    //==========STRUCTURES==========
    // vertex
    struct VertexProperties {
        int id;
        int label;
        VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
    };
     
    // edge
    struct EdgeProperties {
        unsigned id;
        unsigned label;
        EdgeProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
    };
     
    // Graph
    struct GraphProperties {
        unsigned id;
        unsigned label;
        GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
    };
     
    // adjency list
    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
                                  GraphProperties> Graph;
     
    // descriptors
     
    typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
    // iterators
    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    typedef graph_traits<Graph>::edge_iterator edge_iter;
    typedef std::pair<edge_iter, edge_iter> edge_pair;
    //=================callback used fro subgraph_iso=================================================================
    struct my_callback {
        template <typename CorrespondenceMap1To2, typename CorrespondenceMap2To1>
        bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const {
            return false;
        }
    };
     
    //==========handle_error==========
    void handle_error(const char *msg) {
        perror(msg);
        exit(255);
    }
    //============READ ALL THE FILE AND RETURN A STRING===================
    const char *readfromfile(const char *fname, size_t &length) {
        int fd = open(fname, O_RDONLY);
        if (fd == -1)
            handle_error("open");
     
        // obtain file size
        struct stat sb;
        if (fstat(fd, &sb) == -1)
            handle_error("fstat");
     
        length = sb.st_size;
     
        const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
        if (addr == MAP_FAILED)
            handle_error("mmap");
     
        // TODO close fd at some point in time, call munmap(...)
        return addr;
    }
     
    //==========SPLIT THE STRING BY NEWLINE (\n) ==========
    vector<string> splitstringtolines(string const& str) {
        vector<string> split_vector;
        split(split_vector, str, is_any_of("\n"));
     
        return split_vector;
    }
     
    //============Get a string starting from pos============
    string getpos(int const& pos, string const& yy) {
        size_t i = pos;
        string str;
        for (; yy[i] != ' ' && i < yy.length(); i++)
            str += yy[i];
        return str;
    }
    //==================read string vector and return graphs vector===================
    std::vector<Graph> creategraphs(std::vector<string> const& fichlines) {
        std::vector<Graph> dataG;
        int compide = 0; // compteur de id edge
        for (string yy : fichlines) {
            switch (yy[0]) {
            case 't': {
                string str2 = getpos(4, yy);
                unsigned gid = atoi(str2.c_str());
                dataG.emplace_back(GraphProperties(gid, gid));
                compide = 0;
            } break;
            case 'v': {
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false
                // cout<<yy<<endl;
                int vId, vLabel;
                string vvv = getpos(2, yy);
                vId = atoi(vvv.c_str());
                string vvvv = getpos((int)vvv.length() + 3, yy);
                // cout<<vvvv<<endl;
                vLabel = atoi(vvvv.c_str());
                boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
            }
     
            break;
     
            case 'e': { // cout<<yy<<endl;
                assert(!dataG.empty()); // assert will terminate the program  if its argument turns out to be false
     
                int fromId, toId, eLabel;
                string eee = getpos(2, yy);
                // cout<<eee<<endl;
                fromId = atoi(eee.c_str());
                string eee2 = getpos((int)eee.length() + 3, yy);
                // cout<<eee2<<endl;
                toId = atoi(eee2.c_str());
                int c = (int)eee.length() + (int)eee2.length() + 4;
                //    cout<<c<<endl;
                string eee3 = getpos(c, yy);
                //  cout<<eee3<<endl;
                eLabel = atoi(eee3.c_str());
                boost::add_edge(fromId, toId, EdgeProperties(compide, eLabel), dataG.back());
                compide++;
            } break;
            }
        }
     
        return dataG;
    }
    //============test if the graph connectivity========================================================
    bool graphconnexe(Graph const& g) { 
        return num_edges(g) >= num_vertices(g) - 1; 
    }
    //====================print the graph information========================================================
    void printgraph(Graph const& gr) {
        typedef std::pair<edge_iter, edge_iter> edge_pair;
     
        std::cout << " contains " << num_vertices(gr) << " vertices, and " << num_edges(gr) << " edges " << std::endl;
        if (graphconnexe(gr)) {
     
            // Vertex list
            if (num_vertices(gr) != 0) {
                std::cout << "  Vertex list: " << std::endl;
                for (size_t i = 0; i < num_vertices(gr); ++i) // size_t vertice number in the graph
                {
                    std::cout << "   v[" << i << "]   ID: " << gr[i].id << ", Label: " << gr[i].label << std::endl;
                }
            }
            // Edge list
            if (num_edges(gr) != 0) {
                std::cout << "  Edge list: " << std::endl;
                edge_pair ep;
                for (ep = edges(gr); ep.first != ep.second; ++ep.first) // ep edge number
                {
                    vertex_t from = source(*ep.first, gr);
                    vertex_t to = target(*ep.first, gr);
                    edge_t edg = edge(from, to, gr);
                    std::cout << "   e(" << gr[from].id << "," << gr[to].id << ")   ID: " << gr[edg.first].id
                              << " ,  Label: " << gr[edg.first].label << std::endl;
                }
            }
            std::cout << "\n\n" << std::endl;
        } else {
            cout << "Please check this graph connectivity." << endl;
        }
    }
     
    //=========================================================
    /*bool gUe(Graph &g, edge_iter ep, Graph t) {
     
        vertex_t from = source(*ep, t);
        vertex_t to = target(*ep, t);
     
        Graph::edge_descriptor copied_edge = boost::add_edge(from, to, t[*ep], g).first;
     
        g[source(copied_edge, g)] = t[from];
        g[target(copied_edge, g)] = t[to];
     
        if (graphconnexe(g) && graphconnexe(t)) {
            return vf2_subgraph_iso(g, t, my_callback());
        } else {
            return false;
        }
    }*/
    //=================test if the given vertice exist in the graph=========================
    bool verticeexist(Graph const& g, int const& vId, int const& vlabel) {
        int cpt = 0;
        if (num_edges(g) != 0) {
            for (size_t i = 0; i < num_vertices(g); ++i) // size_t vertice number in the graph
            {
                if ((g[i].id == vId) && (g[i].label == vlabel)) {
                    cpt++;
                }
            }
        }
        return cpt != 0;
    }
    //=============test if the given edge exist in the graph===========================
    bool edgeexist(Graph const& g, int const& fromid, int const& toid, unsigned const& elabel) {
        int bn = 0;
        if (graphconnexe(g)) {
            if (num_edges(g) != 0) {
                edge_pair ep;
                for (ep = edges(g); ep.first != ep.second; ++ep.first) // ep edge number
                {
                    vertex_t from = source(*ep.first, g);
                    vertex_t to = target(*ep.first, g);
                    edge_t edg = edge(from, to, g);
     
                    if ((g[from].id == fromid) && (g[to].id == toid) && (g[edg.first].label == elabel)) {
                        bn++;
                    }
                }
            }
        }
     
        return (bn != 0);
    }
     
    // =============test if thoses vertices are neighbours============================
    bool verticesareneighbours(Graph const& g, int const& a, int const& b) {
        int bn = 0;
        if (graphconnexe(g)) {
     
            if (num_edges(g) != 0) {
                edge_pair ep;
                for (ep = edges(g); ep.first != ep.second; ++ep.first) // ep edge number
                {
                    vertex_t from = source(*ep.first, g);
                    vertex_t to = target(*ep.first, g);
     
                    if (((g[from].id == a) || (g[to].id == a)) && ((g[from].id == b) || (g[to].id == b))) {
                        bn++;
                    }
                }
            }
        }
     
        return (bn != 0);
    }
    //=============test if those edges are neighbours=============================
        template <typename Graph, typename E = typename boost::graph_traits<Graph>::edge_descriptor>
        bool edgesareneighbours(Graph const& g, E e1, E e2) {
     
            std::set<vertex_t> vertex_set { 
                source(e1, g), target(e1, g),
                source(e2, g), target(e2, g),
            };
     
            return graphconnexe(g) && vertex_set.size() < 4;
        }
    //===============if the graph is empty add the edge with vertices===========================
    void emptygraphaddedge(Graph &g, int fromId, int toId, int eLabel) {
        if (num_edges(g) == 0) {
            boost::add_edge(fromId, toId, EdgeProperties(num_edges(g) + 1, eLabel), g);
        }
    }
     
    //==============================M A I N   P R O G R A M =======================================
    int main() {
        clock_t start = std::clock();
        size_t length;
     
        std::vector<Graph> dataG = creategraphs(splitstringtolines(readfromfile("testgUe.txt", length)));
     
        typedef std::pair<edge_iter, edge_iter> edge_pair;
     
          if (!dataG.empty()) {
     
            cout<<"graphconnexe?"<<graphconnexe(dataG[0]))<<endl;
            cout<<"verticeexist?"<<verticeexist(dataG[0],1,4);
            cout<<"verticeexist?"<<verticeexist(dataG[0],4,2);
            cout<<"verticesareneighbours?"<<verticesareneighbours(dataG[0],1,4))<<endl;
            cout<<"verticesareneighbours?"<<verticesareneighbours(dataG[0],4,2))<<endl;
            cout<<"edgeexist?"<<edgeexist(dataG[0],1,4,16)<<endl;
            cout<<"edgeexist?"<<edgeexist(dataG[0],1,4,12)<<endl;
     
            edge_pair ep = edges(dataG[0]);
     
            if (size(ep) >= 2) {
                 Graph::edge_descriptor e1 = *ep.first++;
                 Graph::edge_descriptor e2 = *ep.first++;                                                    
                 cout << "edgesareneighbours?" << edgesareneighbours(dataG[0], e1, e2) << endl;
     
            }
        }
     
        // end and time
        cout << "FILE Contains " << dataG.size() << " graphs.\nTIME: " << (std::clock() - start) / (double)CLOCKS_PER_SEC
             << "s" << endl; // fin du programme.
    }
    lorsque je compile ce programme j'ai un erreur du type:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    cc1plus: out of memory allocating 1677721600 bytes after a total of 6270976 bytes
    Comment faire pour améliorer le programme (la rapidité d'exécution et l'allocation de mémoire) et régler ce problème svp!

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Février 2005
    Messages
    5 059
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Conseil

    Informations forums :
    Inscription : Février 2005
    Messages : 5 059
    Points : 12 095
    Points
    12 095
    Par défaut
    Utilisez un débuggeur, votre taille d'allocation semble absurde.

  3. #3
    Membre éprouvé
    Profil pro
    Inscrit en
    Juillet 2009
    Messages
    307
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2009
    Messages : 307
    Points : 983
    Points
    983
    Par défaut
    Surprenant comme message 1.6go de malloc c'est énorme, si tu découpes en petits fichiers avec une seule fonction est ce que ca passe ?

  4. #4
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2011
    Messages
    338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2011
    Messages : 338
    Points : 0
    Points
    0
    Par défaut
    Citation Envoyé par bacelar Voir le message
    Utilisez un débuggeur, votre taille d'allocation semble absurde.
    Désolé, j'ai pas compris. comment le débuggeur peut réglé ça !

  5. #5
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    Il te dira comment ca se fait que tu demandes 1,6 Go sur un seul malloc.
    Que tu fasses un million de malloc, ca peut être de la négligence.

    Mais tu te vois écrire new int[400000000]?
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  6. #6
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2011
    Messages
    338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2011
    Messages : 338
    Points : 0
    Points
    0
    Par défaut
    Citation Envoyé par leternel Voir le message
    Il te dira comment ca se fait que tu demandes 1,6 Go sur un seul malloc.
    Que tu fasses un million de malloc, ca peut être de la négligence.

    Mais tu te vois écrire new int[400000000]?
    d'accord comment faire ça avec dbg sur UBUNTU 14.04LTS 32bits ?

  7. #7
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    En lisant la documentation de gdb, parce que pour le coup, je n'en sais rien.
    A chaque fois, c'est ce que je fais.

    Sinon, tu cherches des new ou mallocs dans ton code, et tu regardes leurs arguments.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  8. #8
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2011
    Messages
    338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2011
    Messages : 338
    Points : 0
    Points
    0
    Par défaut
    Citation Envoyé par leternel Voir le message
    En lisant la documentation de gdb, parce que pour le coup, je n'en sais rien.
    A chaque fois, c'est ce que je fais.

    Sinon, tu cherches des new ou mallocs dans ton code, et tu regardes leurs arguments.
    J'ai pas utilisé des new ou mallocs dans mon code

  9. #9
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 186
    Points : 17 126
    Points
    17 126
    Par défaut
    Utilise gdb, pour savoir dans quelle fonction il plante. Ca doit être les commandes start, run et stacktrace, à vérifier toutefois.

    Ma première candidate serait mmap, parce que length serait négative et donc un très très grand unsigned.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

Discussions similaires

  1. Fatal error: Out of memory (allocated 30408704) (tried to al
    Par kate59 dans le forum PHP & Base de données
    Réponses: 1
    Dernier message: 25/01/2012, 15h06
  2. [pb mémoire] out of memory d'eclipse
    Par Casp dans le forum Eclipse Java
    Réponses: 2
    Dernier message: 12/05/2005, 17h39
  3. conctruction de la librairie boost graph
    Par jiim dans le forum Bibliothèques
    Réponses: 1
    Dernier message: 10/03/2005, 23h30
  4. Out of memory
    Par shurato dans le forum ANT
    Réponses: 1
    Dernier message: 10/11/2004, 17h19
  5. [JBuilder 8] Out of memory problem ...
    Par keros dans le forum JBuilder
    Réponses: 2
    Dernier message: 08/09/2003, 20h03

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo