c++ - BOOST图cc1plus : out of memory allocating

Question

我正在使用 BOOST 解决图形挖掘问题，但是当我编译它时出现了这个错误:

cc1plus: out of memory allocating 1677721600 bytes after a total of 6270976 bytes

我该如何解决？以及如何改进此代码以使其更快并避免内存问题？

代码如下:

#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.
}

Answer 1

这是对 Coliru 上实时所需内存量下限的估计:

• 16 megabytes:

  g++: internal compiler error: Killed (program cc1plus)
  libbacktrace could not find executable to open
  Please submit a full bug report,
  with preprocessed source if appropriate.
  See <http://gcc.gnu.org/bugs.html> for instructions.
  

• 32 megabytes:

  /usr/local/libexec/gcc/x86_64-unknown-linux-gnu/4.9.2/cc1plus: error while loading shared libraries: libc.so.6: failed to map segment from shared object: Cannot allocate memory
  

• 64 megabytes:

  virtual memory exhausted: Cannot allocate memory
  

• 128 megabytes:

  virtual memory exhausted: Cannot allocate memory
  

• 256 megabytes:

  virtual memory exhausted: Cannot allocate memory
  

• 512 megabytes:

  graphconnexe?1
  verticeexist?0verticeexist?0verticesareneighbours?0
  verticesareneighbours?0
  edgeexist?0
  edgeexist?0
  edgesareneighbours?1
  FILE Contains 1 graphs.
  TIME: 0s
  

看来512兆应该问题不大。修复你的编译器设置

• 有足够资源的电脑
• 合理更新的编译器
• 检查标志(尝试更多和更少的优化、调试信息等)

在我的系统上，带有 -std=c++11 -Wall -pedantic -g -O0 -m32 的 gcc 4.9 从 32 兆字节开始工作:

$ bash -c '{ ulimit -v $((1024*32));制作-Bsn； }'/usr/lib/gcc-snapshot/bin/g++ -std=c++11 -Wall -pedantic -g -O0 -m32 -isystem/home/sehe/custom/boost -march=native test.cpp -o测试