Generating an edge graph using four values a,b,c,d in c++

Question

I'm having a trouble solving a question which asks me to generate an edge graph using 4 random numbers a,b,c,d , so the formula is as follows , to generate the nodges of the graph we'll use variable d , if we divide d with 3 and we get a remainder of 0 then 10 nodges are generated , if d/3 = 1 then 11 nodges if d/3 = 2 then 12 nodges are generated , as for the edges we have the following formula (i,j) ∈ U <-> ((ai+bj)/c) / d ≤ 1 , basically the edge will connect the nodge of i with the nodge of j if the formula after dividing by d gives a remainder smaller or equal to 1. Can someone tell me what's the problem with the code below ?

Here is the code :

#include <iostream>
#include <vector>
using namespace std;
struct Edge {
    int src, dest;
};
class Graph
{
public:
    vector<vector<int>> adjList;
    Graph(vector<Edge> const& edges, int N)
    {
        adjList.resize(N);
        for (auto& edge : edges)
        {
            adjList[edge.src].push_back(edge.dest);
        }
    }
};
void printGraph(Graph const& graph, int N)
{
    for (int i = 0; i < N; i++)
    {
        cout << i << " ——> ";
        for (int v : graph.adjList[i])
        {
            cout << v << " ";
        }
        cout << endl;
    }
}
int main()
{
    vector<Edge> edges;
    int a, b, c, d,remainder,Nodges,result;
    cout << "Enter 4 values : \n";
    cin >> a >> b >> c >> d;
    remainder = d % 3;
    if (remainder == 0)
    {
        Nodges = 10;
    }
    else if (remainder == 1)
    {
        Nodges = 11;
    }
    else if (remainder == 2)
    {
        Nodges = 12;
    }
    for (int i = 0; i < Nodges; i++)
    {
        for (int j = 0; j < Nodges; j++)
        {
            result = ((a * i + b * j) / c) % d;
            if (result <= 1)
            {
                edges =
                {
                    {i,j}
                };
            }
        }
    }
    Graph graph(edges, Nodges);
    printGraph(graph, Nodges);
    return 0;
}

Suggestion: Using an input set known to cause failure, step through the program with a debugger and keep an eye out for the unexpected, for example the wrong path take or the wrong value stored. The unexpected is almost always a bug. The rest of the time its because of incorrect expectations, and those are just as bad. — user4581301, May 20 '21 at 21:29
Proper indentation makes the code much more readable, as you your code blocks get optically visible at once (I changed that for you already, compare before vs. after). — Aconcagua, May 25 '21 at 06:13
About [`using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). — Aconcagua, May 25 '21 at 06:14
Correct type for providing sizes is `std::size_t`, not `int`. — Aconcagua, May 25 '21 at 06:24

Aconcagua · Accepted Answer · 2021-05-25T06:47:43.883

At first you do not handle the case of d being outside of desired range. If d is e. g. 37, then you leave Nodges uninitialised, invoking undefined behaviour afterwards by reading it. You might add a final else to catch that case, printing some representation for an empty graph or a message and then return, so that you do not meet the for loops at all.

Simpler, though:

if(remainder < 3)
{
    nodes = 10 + remainder;

    // your for loops here
}

If you want to create an empty graph anyway, then don't forget to initialise nodes to 0; otherwise you should include the graph code in the if block above, too.

The main point your code fails is the following, though:

edges =
{
    {i,j}
};

That way, you create a new vector again and again, always containing a single element, and the old one is replaced by that.

You actually need:

edges.emplace_back(i, j);

Finally: Get used to always check the stream's state after input operation. Users tend to provide invalid input, if you do not catch that you might get inexpected and actually undefined behaviour (such as dividing by 0).

if(std::cin >> a >> b >> c >> d)
{
    /* your code */
}
else
{
    // handle invalid input, e. g. by printing some message

    // if you want to go on reading the stream:
    // clears the error flags:
    std::cin.clear();
    // clears the stream's buffer yet containing the invalid input:
    std::cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

Generating an edge graph using four values a,b,c,d in c++

1 Answers1