Andreas T - 1 year ago 35

C++ Question

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);

}

Answer Source

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;
}
```