Unknown Error While Writing An Adjacent List Graph

Question

I was writing an adjacent list-based graph with weighted edges. My goal is to implement a graph to test the Djikstra's shortest path algorithm. I came to a bummer when I was implementing the removeEdge function. I looked at the build messages but I didn't have a clue as in what the errors below are about.

There are a few warnings before this one below but they are minor as it compiled and ran ok.

c:\program files (x86)\codeblocks\mingw\bin..\lib\gcc\mingw32\4.7.1\include\c++\bits\list.tcc||In instantiation of 'void std::list<_Tp, _Alloc>::remove(const value_type&) [with _Tp = Edge; _Alloc = std::allocator; std::list<_Tp, _Alloc>::value_type = Edge]':|

This is the error generated.

c:\program files (x86)\codeblocks\mingw\bin..\lib\gcc\mingw32\4.7.1\include\c++\bits\list.tcc|249|error: no match for 'operator==' in '__first.std::_List_iterator<_Tp>::operator*() == __value'|

Now, the code:

#ifndef WEIGHTED_ADJACENT_LIST_GRAPH_H
#define WEIGHTED_ADJACENT_LIST_GRAPH_H

#include <list>
#include <forward_list>
#include <stack>
#include <string>

using namespace std;

typedef int Weight;


class Edge;

class Vertex {
    friend class Edge;
    int num;
    string name;

public:

    Vertex();
    Vertex(int n, string v_name){
        num = n;
        name = v_name;
    }

    int getNum() const{
        return num;
    }

    string getName() const{
        return name;
    }

    void setNum(int new_num){
        num = new_num;
    }

    void setName(string new_name){
        name = new_name;
    }
};

class Edge {
    Weight weight;
    Vertex src;
    Vertex dest;

public:
    Edge();
    Edge(Vertex s, Vertex d, Weight w):src(s), dest(d),weight(w){}
    /*
    Edge(Vertex s, Vertex d, Weight w){
        src = s;
        dest = d;
        weight = w;
    }
    */

    Weight getWeight() const{
        return weight;
    }

    int getSrcNum() const{
        return src.num;
    }

    int getDestNum() const{
        return dest.num;
    }
};

class AdjacentList{
    int num_Vertices;
    list<Edge> *adj;

public:
    AdjacentList();

    AdjacentList(int n){
        num_Vertices = n;
    }

    void addEdge(Vertex &i, Edge &j){
        adj[i.getNum()].push_back(j);
    }

    void removeEdge(Vertex &i, Edge j){
        if(!adj[i.getNum()].empty())
        {
            adj[i.getNum()].remove(j);
        }
        else{
            cerr<<"Adjacent list underflow in removeEdge function"<<endl;
        }
    }
};

#endif

Please be noted that this graph is incomplete. A lot functions still need to be implemented there. Does anyone know what's wrong with this data structure code?

Tangential at best, but **PLEASE** don't put `using namespace std` in a header file, especially if it will be commonly used! — user3288829, Aug 23 '15 at 04:18
@user3288829 Thanks for pointing that out. I understand that we should avoid including different header files with the same name multiple times. But why should we avoid including a standard package multiple times? Is it because some programmers explicitly avoid to use the standard package? — VequalsIR, Aug 24 '15 at 00:10
Namespaces provide scope resolution, so multiple different libraries can have functions with the same name and it is still clear which is being called. `using namespace` imports all functions from that namespace into the global namespace, and can cause ambiguity. Since `#include` pastes the contents of the header into the .cpp file, if your header was included in a lot of files in a large project (directly, or by being included by another common header), the compilation would break and the errors would not point directly to the problem. — user3288829, Aug 24 '15 at 02:23
Using the standard library is great, almost always preferred, but it's better to use the scope resolution operator `::` than `using namespace`, especially in a header file. See the top two answers of http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice for more complete explanations (But thanks for wanting to understand why!) — user3288829, Aug 24 '15 at 02:25

score 0 · Accepted Answer · answered Aug 23 '15 at 04:19

0

You haven't provided an operator== for Edge, I have no idea exactly how you want to specify which Edges are equal but you'll need something like the following defined before you use remove

bool operator==(Edge const& lhs, Edge const& rhs)
{
  return
  lhs.getWeight()  == rhs.getWeight() &&
  lhs.getSrcNum()  == rhs.getSrcNum() &&
  lhs.getDestNum() == rhs.getDestNum();
}

answered Aug 23 '15 at 04:19

user657267

20,568
5
58
77

Thanks for your answer. I prefer to compare _this_ with the Edge _j_. So, I wrote `bool operator==(const Edge &j) const` for the function declaration. – VequalsIR Aug 24 '15 at 00:26
@VequalsIR fair enough, although non-member comparison operators can be [more useful](http://stackoverflow.com/questions/32108610/overload-greater-than-operator-with-or-without-friend/32109546#32109546) if your class has non-`explicit` conversion constructors. – user657267 Aug 24 '15 at 00:36

Unknown Error While Writing An Adjacent List Graph

1 Answers1