0

I was trying to implement Prim's algorithm(eager) which requires to keep a track of best incoming edge(least cost) to a vertex. For this I use stl map as:

std::map<int, Edge*> bestEdgeFor;

However when I try to assign an edge to some key, what is actually stored is an edge with garbage values for the data members. As such I get some random edges as output. However when I assign a new instance of Edge class with same data, it works correctly.

bestEdgeFor[destNode] = &e; //Doesn't work
bestEdgeFor[destNode] = new Edge(e.from,e.to,e.cost); // Works

Here is the Edge class definition:

class Edge {
public:
    int from;
    int to;
    int cost;
};

What exactly is the problem I am not able to figure out. Is it that we can't directly assign an object of a class? Please excuse my naivety.

This is the Graph class and I am doing the assignment operation in a member function of this class. e comes from the adjList. Is the scope valid?

class Graph {
    int V;
    std::map<int, std::list<Edge>> adjList;
    map<int, Edge*> bestEdgeFor;
public:
    void relaxEdgesAtNode(int currentNode, MinIndexedPQ&  ipq, int* visited){
        visited[currentNode] = 1;
        for(Edge e : adjList[currentNode]) {
            int destNode = e.to;

            if(visited[destNode]){
                continue;
            }

            if(!ipq.contains(destNode)) {
                ipq.insert(destNode,e.cost);

                // bestEdgeFor[destNode] = &e // Don't work
                bestEdgeFor[destNode] = new Edge(e.from,e.to,e.cost); // Works
            } else {
                if(e.cost < ipq.keyOf(destNode)) {
                    ipq.decreaseKey(destNode,e.cost);
                    // bestEdgeFor[destNode] = &e // Don't work
                    bestEdgeFor[destNode] = new Edge(e.from,e.to,e.cost);
                }
            }
        }
    }

    std::vector<Edge*> primsMST() {
        int s = 0; //choosing the starting node
        int* visited = new int[V]{0};
        MinIndexedPQ ipq(V);
        visited[s] = 1; // marking the starting node visited

        int m = V - 1;
        int edgeCount = 0, mstCost = 0;
        std::vector<Edge*> mstEdges; // This is the return value in case the mst exists

        // Call the problematic function
        relaxEdgesAtNode(s, ipq, visited);

        // Here, the values are garbage, and the printing code prints garbarge
    }
};
Guillaume Racicot
  • 39,621
  • 9
  • 77
  • 141
ANKIT CHOUDHARY
  • 58
  • 2
  • 9
  • What's the scope of `e`? It MUST be at least as broad as `bestEdgeFor` or it'll be destroyed and leave the pointer dangling. – user4581301 Aug 13 '21 at 00:50
  • 1
    `for(Edge e : adjList[currentNode]){` copied the `Edge` so `bestEdgeFor[destNode]` would wind up pointing at a local variable. ``for(Edge & e : adjList[currentNode]){`` allows s you to use the `Edge` in the `list`. `list` has very forgiving [Iterator Invalidation Rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) so you should get away with this. so long as you don't remove the object from the `list`. – user4581301 Aug 13 '21 at 01:15
  • I am using Edge* so that I can keep NULL for the singleton nodes of the graph. – ANKIT CHOUDHARY Aug 13 '21 at 01:16
  • @user4581301 Got it. By `for(Edge & e : adjList[currentNode]){` we get reference of actual edge in the adjacency list. Thanks for the help. – ANKIT CHOUDHARY Aug 13 '21 at 01:26
  • 1
    @ANKITCHOUDHARY My pleasure. Also notice that I added the missing `std::`. [Don't do `using namespace std::`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Have a nice day! – Guillaume Racicot Aug 13 '21 at 01:56
  • 1
    @ANKITCHOUDHARY It looks like you are familiar with other object-oriented languages. The main issue I see in general is that the other languages you may have used are automatically reference-based. This is *not* the case for C++ as C++ is value based, meaning by default, copies of objects are made, not references of objects being copied back and forth. Forget about how those other languages handled objects, C++ is a different animal altogether. – PaulMcKenzie Aug 13 '21 at 02:02
  • @ANKITCHOUDHARY `int* visited = new int[V]{0};` -- In addition, if you're going to use ``, be familiar with a code smell like this. That line of code is the reason why `std::vector` exists. There is no need to use `new[]` here: `std::vector visited(V);` would have been the better option, as you do not get a chance to introduce a memory leak. – PaulMcKenzie Aug 13 '21 at 02:04
  • So `visited` persists in the memory while it would had been erased had it been `vector visited` instead? – ANKIT CHOUDHARY Aug 13 '21 at 02:07
  • 1
    @ANKITCHOUDHARY -- Yes, that memory would have been automatically freed due to `std::vector` destructor being invoked. Right now, your code has a memory leak. As a matter of fact, a good code-reviewer is looking for traces of `new[]` in a program, and there better be a very good reason for it to be in a modern C++ module (maybe **very** old legacy code might have it, but anything in the last 20 years, there should be minimal usage of it). – PaulMcKenzie Aug 13 '21 at 02:08
  • @PaulMcKenzie thanks for the suggestions, can you recommend some c++ learning resources? – ANKIT CHOUDHARY Aug 13 '21 at 02:13
  • 1
    [Try this](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) – PaulMcKenzie Aug 13 '21 at 02:24
  • @PaulMcKenzie can you help me on [this](https://stackoverflow.com/questions/68776694/unable-to-update-referenced-members-data-members)? – ANKIT CHOUDHARY Aug 13 '21 at 18:11

2 Answers2

7

This is the Graph class and I am doing the assignment operation in a member function of this class. e comes from the adjList. Is the scope valid?

Normally, yes. This is because objects in linked list have stable address. As long as they are in the list, you can take their addresses and put the pointer in a map without problems.

Now let's look at your assignment:

Is the scope valid?

bestEdgeFor[destNode] = &e; //Doesn't work

But what is e? How do you initialize it? Let's see:

for (Edge e : adjList) {
     // ... much code ...
     bestEdgeFor[destNode] = &e;
}

In this code, e is a local variable in the scope of the loop that you copy initialize from the value in your list.

e comes from the adjList

This is not true. e don't comes from adjList. As seen in your code, e is a local variable inside your loop, that has a value copied from elsewhere, and in your case, the list. You take the address of a local variable that is going to die after the loop iteration.

What you want to do is most likely this:

// something similar to this
for (Edge& e : adjList) {
     // ... much code ...
     bestEdgeFor[destNode] = &e;
}

Now e is a reference to a variable inside the list. When you take the address of e, you take a pointer to an element of the list.

However, be mindful that taking pointers from elements in a list require a special attention. As soon as you remove elements from it, you have to update the map and erase all pointers referring to that removed element.

Guillaume Racicot
  • 39,621
  • 9
  • 77
  • 141
3

By default, C++ doesn't manage object lifetimes. If you do

bestEdgeFor[destNode] = &e;

You must make sure that e doesn't get destroyed. In you case, when the function returns, e gets destroyed and the map contains an invalid pointer, yielding undefined behaviour.

You can either store objects in your map, instead of pointers:

map<int,Edge>

Or store shared_ptrs, or manage lifetimes yourself. Which you would do with new, but you'll need a delete somewhere.

Jeffrey
  • 11,063
  • 1
  • 21
  • 42