CODEWITHSUNDEEP
c++vectorgraph
Andreas T
Andreas T

Reputation: 753

Vector of vectors is not copied correctly (C++)

I am trying to write a class for directed graphs with very simple functionality like adding and removing edges. For some reason the default-copy constructor does not do its job and I wonder why.

main.cpp:

#include <iostream>
#include "Graph.h"

using namespace std;


int main()
{
    Graph g1(1);
    g1.insertEdge(0, 0);
    Graph g2(g1);

    cout << (g1 == g2) << endl; // false
    return 0;
}

Graph.h:

#ifndef GRAPH_H_INCLUDE
#define GRAPH_H_INCLUDE

#include <vector>

class Graph
{
public:
    typedef unsigned int vertex_t;
    typedef std::vector< std::vector<bool> > edges_set_t;

    vertex_t vertices;
    edges_set_t edges;

    Graph(vertex_t vertices = 0)
        : vertices(vertices)
    {
        initEdges();
    }

    void insertEdge(vertex_t v, vertex_t w)
    {
        edges[v][w] = 1;
    }

    bool hasEdge(vertex_t v, vertex_t w) const
    {
        return edges[v][w];
    }


private:
    void initEdges()
    {
        edges = std::vector< std::vector<bool> >(vertices);
        while (edges.size() < vertices)
            edges.push_back(std::vector<bool>(vertices));
    }
};



bool operator==(const Graph& g, const Graph& h)
{
    if (g.vertices != h.vertices)
        return false;

    for (Graph::vertex_t v = 0; v < g.vertices; ++v)
        for (Graph::vertex_t w = 0; w < g.vertices; ++w)
            if ((g.hasEdge(v, w) && !h.hasEdge(v, w)) || (!g.hasEdge(v, w) && h.hasEdge(v, w)))
                return false;

    return true;
}





#endif

In my main function, I create a graph with a single vertex and add a self-loop onto it. I then try to copy it using the default copy constructor, which somehow gives me a graph with the correct number of vertices but no edges at all.

The same is true if I use this constructor:

Graph(const Graph& other)
{
    vertices = other.vertices;
    initEdges();
    edges = other.edges;
}

However, it works correctly with this, for some reason I cannot find:

Graph(const Graph& other)
{
    vertices = other.vertices;
    initEdges();
    for (Graph::vertex_t v = 0; v < vertices; ++v) // no idea why a manual implementation is necessary
        for (Graph::vertex_t w = 0; w < vertices; ++w)
            if (other.hasEdge(v, w))
                insertEdge(v, w);
}

Upvotes: 2

Views: 121

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726499

This loop

while (edges.size() < vertices)

never gets entered, because the constructor you call adds empty vectors for each element of the vector. To make sure that you get a square matrix, use

edges = std::vector< std::vector<bool> >(vertices, std::vector<bool>(vertices));

This can be moved into member intialization list of Graph, rendering initEdges() unnecessary.

Moreover, you can drop vertices variable, because it is always equal to edges.size().

Your comparison operator does this:

if ((g.hasEdge(v, w) && !h.hasEdge(v, w)) || (!g.hasEdge(v, w) && h.hasEdge(v, w)))

The condition is equivalent to

if (g.hasEdge(v, w) != h.hasEdge(v, w))

Since std::vector provides operator == which compares the size, you can rewrite your comparison operator as follows:

bool operator==(const Graph& g, const Graph& h) {
    return g.edges == h.edges;
}

Demo.

Upvotes: 2

Related Questions