1

I'm trying to build a graph class where the graph is represented by adjacency lists. The graph itself is a vector of pointers where each pointer points to a linked list of nodes. For whatever reason, when I use the print graph function the program outputs nothing. Can anyone show me what I am doing wrong and perhaps where my misunderstanding of pointers is? Thanks in advance!

#include <array>
#include <vector>
#include <tuple>
#include <unordered_map>

class Node
{
    public:

    int vertex;
    int value;
    Node* next;

    Node(int ver)
    {
        vertex = ver;
    };
};

class Graph
{
    public:

    int n_nodes;
    std::unordered_map<int,Node*> graph;
    
    Graph(int n)
    {   
        n_nodes = n;
        for(int i=0;i<n;i++)
        {
            graph.insert({i,nullptr});
        };
    };

    void add_edge(int src,int des,int val)
    {
        Node node_des = Node(des);
        node_des.value = val;
        node_des.next = graph[src];
        graph[src] = &node_des;

        Node node_src = Node(src);
        node_src.value = val;
        node_src.next = graph[des];
        graph[des] = &node_src;
    };

    void print_graph()
    {
        for(int i =0; i<n_nodes;i++)
        {
            std::string str = "Head "+std::to_string(i);
            Node node = *graph[i];
            while (&node != nullptr)
            {
                str=str+" -> "+std::to_string(node.vertex);
                node = *(node.next);
            };

            std::cout<<str<<std::endl;
        };
    };
};

int main()
{
    Graph g = Graph(6);
    g.add_edge(0,1,3);
    g.add_edge(2,1,4);
    g.add_edge(0,4,1);
    g.add_edge(4,5,6);
    g.add_edge(5,3,2);
    g.add_edge(4,3,3);
    g.add_edge(3,2,5);
    g.add_edge(4,1,1);
    g.add_edge(3,1,2);

    g.print_graph();
    return 0;
}```
Boyang Zhang
  • 117
  • 7
  • 1
    `Node node = *graph[i];` then `while (&node != nullptr)` ? Node is a local variable (on the stack) it can't be a nullptr ever. – drescherjm Jul 11 '20 at 18:45
  • 1
    `graph[des] = &node_src;` once the scope ends the `node_src` no longer exists and you have a dangling pointer. You can not store the address of a local variable in a structure that exists longer than the local variable. – drescherjm Jul 11 '20 at 18:47
  • man, there's a lot I have to learn about c++ I guess. Thanks for your help, I will re-evaluate my code more carefully. – Boyang Zhang Jul 11 '20 at 18:50
  • Related to my second comment: [https://stackoverflow.com/questions/4643713/c-returning-reference-to-local-variable](https://stackoverflow.com/questions/4643713/c-returning-reference-to-local-variable) – drescherjm Jul 11 '20 at 18:50
  • 1
    In fact, `(&(`anything`) != nullptr)` is always true. There's no expression whose address might be null. – aschepler Jul 11 '20 at 18:50
  • 1
    ***I will re-evaluate my code more carefully.*** You most likley for this assignment have to use Node* and `new` instead of Node and &someLocal variable. – drescherjm Jul 11 '20 at 18:51
  • Also, if this is for some other use, rather than just the exercise of implementing a graph, check out Boost.Graph. – aschepler Jul 11 '20 at 18:51
  • @aschepler This is just me trying to learn C++. My first language was Python, which you'd imagine didn't really teach me about any of these lower-level concepts. Thanks for the suggestion though, I'll for sure check that out as well. – Boyang Zhang Jul 11 '20 at 18:53
  • I had a feeling that you learned some other language and that was causing the confusion here because of the different behavior. – drescherjm Jul 11 '20 at 18:55
  • @drescherjm __You most likley for this assignment have to use Node* and new instead of Node and &someLocal variable. __ That worked! But is the reason that it worked due to now explicitly setting a pointer as the target instead of &node_src? So if I have created the pointer in the local scope it'll still carry over to the bigger scope of the class instance? Sorry I'm still a bit confused :P. – Boyang Zhang Jul 11 '20 at 19:08
  • 1
    With `new` you create a pointer to memory where you control its duration instead of a local variable that goes out of scope. – drescherjm Jul 11 '20 at 19:12
  • does that mean with `new` I'm no longer creating a local variable? – Boyang Zhang Jul 11 '20 at 19:15
  • 1
    **Creates and initializes objects with dynamic storage duration, that is, objects whose lifetime is not limited by the scope in which they were created.** Found that on cppreference.com. Sometimes I get into the habit of just asking instead of a quick google search :P. – Boyang Zhang Jul 11 '20 at 19:18

2 Answers2

1

If it´s possible, you may just use vector of vector instead of linked lists and not use pointers at all. Because memory cache some insertions in vectors operations may be faster than linked lists, a structure like :

struct Node2 {
    int vertex; 
    int value;
};

struct Edge2 {
    int src, des, value;
};

struct Graph2 {
    int n_nodes;
    std::vector<std::vector<Node2>> graph; 

    void add_edge(Edge2 edge) {
        graph[edge.src].emplace_back(edge.des, edge.value);
        graph[edge.des].emplace_back(edge.src, edge.value);
    }

    void add_edge(std::initializer_list<Edge2> edges)
    {
        std::for_each(edges.begin(), edges.end(), [this](auto &e) { add_edge(e); });
    };
}

Endup bening easier and faster than linked lists;

https://quick-bench.com/q/cmX2-2IYA873TR4qn5aV4ijjUQo

Cleiton Santoia Silva
  • 473
  • 2
  • 7
  • Thanks! The linked list implementation will end up with less memory complexity though right? – Boyang Zhang Jul 12 '20 at 17:51
  • 1
    Assyntoticly speaking, no, it stil O(n) in the number of edges. Pratically well, depends, but mostly no also. The size of each Node2 is smaller then Node, and all of them are concatenated inside a vecor, so the only possible point of less memory efficiency is the spare capacity of the vecor itself, so you may use shrink_to_fit(). – Cleiton Santoia Silva Jul 13 '20 at 02:16
  • That makes sense. Though I thought the indexing/iterability of the vector adds to the memory requirement, but I'm probably confusing them with python lists. – Boyang Zhang Jul 13 '20 at 03:04
0

Made these changes thanks to @drescherjm. The issue was that I had created a local variable and referenced its address instead of explicitly creating a pointer and setting it to a new node instance where the object's lifetime is dynamically controlled.

#include <bits/stdc++.h> 
#include <array>
#include <vector>
#include <tuple>
#include <unordered_map>

class Node
{
    public:

    int vertex;
    int value;
    Node* next;

    Node(int ver)
    {
        vertex = ver;
    };
};

class Graph
{
    public:

    int n_nodes;
    std::unordered_map<int,Node*> graph;
    
    Graph(int n)
    {   
        n_nodes = n;
        for(int i=0;i<n;i++)
        {
            graph.insert({i,nullptr});
        };
    };

    void add_edge(int src,int des,int val)
    {
        Node * node_des = new Node(des);
        node_des->value = val;
        node_des->next = graph[src];
        graph[src] = node_des;

        Node * node_src = new Node(src);
        node_src->value = val;
        node_src->next = graph[des];
        graph[des] = node_src;
    };

    void print_graph()
    {
        for(int i =0; i<n_nodes;i++)
        {
            std::string str = "Head "+std::to_string(i);
            Node * node_ptr = graph[i];
            while (node_ptr != nullptr)
            {
                str=str+" -> "+std::to_string(node_ptr->vertex);
                node_ptr = node_ptr->next;
            };
            std::cout<<str<<std::endl;
        };
    };
};

int main()
{
    Graph g = Graph(6);
    g.add_edge(0,1,3);
    g.add_edge(2,1,4);
    g.add_edge(0,4,1);
    g.add_edge(4,5,6);
    g.add_edge(5,3,2);
    g.add_edge(4,3,3);
    g.add_edge(3,2,5);
    g.add_edge(4,1,1);
    g.add_edge(3,1,2);

    g.print_graph();
    return 0;
}
Boyang Zhang
  • 117
  • 7