Operator error and edge insertion problem in an unweighted, undirected graph

Question

I've got several problems with my adjacency graph in C++. I fixed some of the main errors, but still can run and test the program. I'm not sure if the newEdge() method is working properly, if the vector in the vector is right created, and most importantly how to display the edges in the graph.

There is the code and I marked the lines with errors with "!":

#include <iostream>
#include <algorithm>
#include <fstream> 
#include <vector>


using namespace std;


struct Edge
{
    int begin;
    int end;
};

class Graph
{
private:

    int numOfNodes;
    vector<vector<Edge>> baseVec;

public:

    Graph(int numOfNodes)
    {   
        baseVec.resize(baseVec.size() + numOfNodes);
    }

    void newEdge(Edge edge)
    {
        if (edge.begin >= numOfNodes-1 || edge.end >= numOfNodes-1 || edge.begin < 0 || edge.end < 0)
        {
            cout << "Invalid edge!\n";
        }
        baseVec[edge.begin].emplace_back(edge.end); !!
        baseVec[edge.end].emplace_back(edge.begin); !!
    }
    void display()
    {
        for (int i = 0; i < baseVec.size(); i++)
        {
            cout << "\n Adjacency list of vertex " << i << "\n head "; !!!
            for (int j = 0; j < baseVec[i].size(); j++)  !!!
            {
                cout << baseVec[i][j] << " "; !!!!!!!
                cout << endl;
            }
        }
    }

};

std::ostream &operator<<(std::ostream &os, Edge const &m)
{
    return os << m.begin << m.end;
}

int main()
{
    int vertex, numberOfEdges, begin, end;
    cout << "Enter number of nodes: ";
    cin >> vertex;
    numberOfEdges = vertex * (vertex - 1);

    Edge edge;
    Graph g1(vertex);
    for (int i = 0; i < numberOfEdges; i++)
    {
        cout << "Enter edge ex.1 2 (-1 -1 to exit): \n";
        cin >> edge.begin >> edge.end;
        if ((begin == -1) && (end == -1))
        {
            break;
        }
        g1.newEdge(edge);
    }
    g1.display();
    return 0;
}

I overloaded the << operator, not sure if it's right and the two errors I have in Visual Studio are:

'<': signed/unsigned mismatch

binary '<<': no operator found which takes a right-hand operand of type '_Ty' (or there is no acceptable conversion)

This is a new version of my prior question.

score 1 · Accepted Answer · answered Nov 16 '18 at 05:59

I am assumming your Graph is a model over an undirected graph with a fixed number of nodes, based your program logic.

Your program has quite a few problems.

First, in member function Graph::newEdge, the precondition is wrong,

edge.source >= numOfNodes - 1 || edge.target >= numOfNodes - 1

It should be,

edge.source >= numOfNodes || edge.target >= numOfNodes

More importantly, if the precondition fails, newEdge function should return immediately, instead of adding the edge.

Second problem is with constructor Graph::Graph. 1) private member variable numOfNodes is not initialized. 2) There is no need to call baseVec.resize(). A vector of a given size can be created directly. 3) Member initializer list should be preferred.

Graph(int numOfNodes) : numOfNodes(numOfNodes), baseVec(num0fNodes) {}

Third problem is with member variable Graph::baseVec.

vector<vector<Edge>> baseVec;

Suppose your have a graph of 4 nodes, with edges inserted with the following sequence, (0, 1), (0, 2), (0, 3), (1, 2), (2, 3). The process should be,

step 1: (0, 1)

0: 1
1: 0

step 2: (0, 2)

0: 1 2
1: 0
2: 0

step 3: (0, 3)

step 4: (1, 2)

step 5: (2, 3)

What is stored into baseVec is not of type Edge, but int. The source is the row index and the target is column index. With that, the output operator for struct Edge isn't necessary.

At last, in main function, the assignment on numOfEdges isn't necessary. I guess your logic is the maximum number of edges on the graph is vertex * (vertex - 1), but newEdge member function does not check for duplicate edges. You have to modify the member function to make it useful.

See the full demo on wandbox.

Operator error and edge insertion problem in an unweighted, undirected graph

1 Answers1