Function to generate a random weighted graph freezes after a certain threshold edges

Question

So I'm trying to generate a random graph with n nodes and n*4 edges by having the nodes 1, 2, 3, ..., n and the edges being an array of triples which stores endpoint of edge 1, endpoint of edge 2 and the weight of the edge:

struct edge{
    int endpoint1;
    int endpoint2;
    int weight;
};

This is the function to generate the array of edges (of triples):

edge* generateRandomGraph(int nrOfNodes)
{
    int adjMatrix[nrOfNodes+1][nrOfNodes+1] = {0};

    int nrOfEdges = nrOfNodes*4 ;

    edge *edges = new edge[nrOfNodes+1];
    
    int counter = 0;

    while(counter < nrOfEdges)
    {
        int a = 1 + rand() % nrOfNodes;
        int b = 1 + rand() % nrOfNodes;

        if(a != b)
        if(adjMatrix[a][b] == 0)
        {
            adjMatrix[a][b] = 1;
            adjMatrix[b][a] = 1;
            edges[counter].endpoint1 = a;
            edges[counter].endpoint2 = b;
            edges[counter].weight = rand() % 100;
            counter++;
        }
    }
                        
    return edges;
}

It functions properly until one point, at element edges[31] when it freezes. What could be the problem? Debugger does not specify any error, but when I try to print the values it breaks. Maybe some segmentation fault because the filling of the array is based on the rand()?

`int adjMatrix[nrOfNodes+1][nrOfNodes+1] = {0};` is invalid because [C++ doesn't have variable-length arrays](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). Use `std::vector` instead. — Some programmer dude, Dec 09 '22 at 21:20

score 2 · Answer 1 · answered May 03 '23 at 11:05

This doesn't work for two reasons.

There are no variable length arrays in c++. But you might get this to work using custom extensions in your compiler. Anyhow, you shouldn't do this, because if the memory is alloca'd, a medium sized graph will likely destroy your stack.
Your edges array is allocated to hold numberOfNodes+1 elements, but it should hold numberOfEdges. You have a memory overrun and from that point forward you are in UB-land.

For both problems, use an std::vector which you can pre-allocate to the size you need. Thanks to move semantics, you can just return the vector object without loss of performance.

  std::vector<edge> edges;
  edges.reserve(numberOfEdges); // not +1

  // ... later ...

    edges.push_back(edge{a, b, weight});

  // ...

  return edges;

Also, I would strongly recommend not to use rand() but std::mt19937.

Function to generate a random weighted graph freezes after a certain threshold edges

1 Answers1