CODEWITHSUNDEEP
c++pointersstl
Alex Haldeman
Alex Haldeman

Reputation: 25

Getting a segmentation fault when trying to add vertex to custom Graph data structure?

I am trying to create a custom Graph data structure in C++. I am using std::set to keep track of the vertices. I check the set when I insert a new vertex to make sure it is not already in the graph. My experience with C++ is minimal, so I am having trouble implementing this properly. The problem seems to be with the contains function. Here is the code for the graph:

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#ifndef GRAPH_H
#define GRAPH_H

/*
Graph - Templated graph class
*/

template <typename T>
struct AdjListNode {
    T data;
    int index;
    struct AdjListNode<T> *next;
};

template <typename T>
struct AdjList {
    struct AdjListNode<T> *head;
};


template <class T>
class Graph {
    private:
        std::vector< AdjList<T>* > m_adj_list; //Adjacency list
        std::set<T> m_node_set;
        std::map<T, int> m_index_map; 
        int m_num_vertices;
        bool m_is_directed;
        void addDirectedEdge(T src, T dest);
        bool contains(T vertex);

    public:
        Graph(bool isDirected=true);
        bool isDirected();
        int numVertices();
        bool addVertex(T vertex);
        void addEdge(T src, T dest);
        std::string printGraph();
        AdjListNode<T>* getAdjacent(T vertex);
};

#endif

CPP file:

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include "Graph.h"

template <class T>
Graph<T>::Graph(bool is_directed) {
    m_num_vertices = 0;
    m_is_directed = is_directed;
}

template <class T>
bool Graph<T>::isDirected() {
    return m_is_directed;
}

template <class T>
int Graph<T>::numVertices() {
    return m_num_vertices;
}

template <class T>
bool Graph<T>::addVertex(T vertex) {
    //check to make sure node is not in graph
    if (contains(vertex)) { //segfault occurs here
         AdjListNode<T> *newNode = new AdjListNode<T>;
         newNode->index = m_adj_list.size();
         AdjList<T> *newAdjList = new AdjList<T>;
         newAdjList->head = newNode;
         m_adj_list.push_back(newAdjList);
         m_num_vertices++;
        return true;
    } else {
        return false;
    }
}

template <class T>
void Graph<T>::addDirectedEdge(T src, T dest) {
    if (contains(src)) {
        AdjListNode<T> *newNode = new AdjListNode<T>;
        newNode->data = dest;
        newNode->next = NULL;
        AdjList<T> *list = m_adj_list[m_index_map[src]];
        AdjList<T> *currentNode = list->head;
        while (currentNode->next != NULL) {
            currentNode = currentNode->next;
        }
        //insert at the end of adjacency list
        currentNode->next = newNode;
    }
}

template <class T>
bool Graph<T>::contains(T vertex) {
    return m_node_set.find(vertex) == vertex;
}

template <class T>
void Graph<T>::addEdge(T src, T dest) {
    addDirectedEdge(src, dest);
    if (!m_is_directed) {
        addDirectedEdge(dest, src);
    }
}

template <class T>
std::string Graph<T>::printGraph() {
    return "";
}

template <class T>
AdjListNode<T>* Graph<T>::getAdjacent(T vertex) {
    if (*m_node_set.find(vertex) == vertex) {
        AdjListNode<T>* list = m_adj_list[m_index_map[vertex]];
        return list->head->next;
    } else {
        return NULL;
    }
}

Can anyone point me in the right direction to fix this issue? Thanks.

Upvotes: 0

Views: 77

Answers (1)

mask
mask

Reputation: 549

In the contains method, shouldn't it be

return (m_node_set.find(vertex) != m_node_set.end());

Upvotes: 1

Related Questions