2

So I'm working on a network flow problem and have to be able to delete the right half of my bipartite graph in order to deal with multiple graphs at once. Here's how I have my node and edge classes set up:

class Node {
public:
    Node();
    int id;
    int visited;
    Node_Type type;
    vector <bool> letters;
    vector <class Edge *> adj; // Adjacency list
    class Edge *backedge;
};

class Edge {
public:
    Node *to;
    Node *from;
    Edge *reverse; // Edge with opposite to/from
    int original; // 1 on normal
    int residual; // 0 on normal
};

And a potential graph can be seen in this image:

Graph image

Where my goal is to delete all edges and nodes to the right of the second column.

I have all my nodes organized in a vector of Node pointers, indexed from left to right/top to bottom, and I'm trying to traverse that vector and delete any edges contained in a node's adjacency list that are within the second and third columns or the third and fourth columns. After which I'll traverse backwards and delete the sink node as well as the third column's nodes, then finally resize the nodes vector to only accommodate the first two columns of nodes.

Here's how I'm doing that:

void DeleteHalfGraph() {
    int i, j;

    // Delete all edges between dice, words, and the sink
    for(i = 1; i < nodes.size(); i++) {
        if(nodes[i]->type == DICE) { // DICE refers to the second column of nodes
            for(j = 0; j < nodes[i]->adj.size(); j++) {
                if(nodes[i]->adj[j]->to->type == WORD) {
                // WORD refers to the third column of nodes
                    delete nodes[i]->adj[j];
                }
            }
        }
        else if(nodes[i]->type == WORD || nodes[i]->type == SINK) {
        // SINK refers to the 4th column of nodes
            for(j = 0; j < nodes[i]->adj.size(); j++) {
                delete nodes[i]->adj[j];
            }
        }
    }

    // Delete all nodes now not connected to edges
    // minNodes = 5, size of the vector without the 3rd/4th columns
    for(i = nodes.size() - 1; i >= minNodes; i--) {
        if(nodes[i]->backedge != NULL) delete nodes[i]->backedge;
        delete nodes[i];
    }

    nodes.resize(minNodes);
}

The error I'm getting when compiling is:

*** Error in `./worddice': malloc(): memory corruption (fast): 0x0000000000c69af0 ***

I very well just may not be understanding my pointers correctly as I haven't dealt with deallocating memory like this recently. Regardless, where am I going wrong? Any help is greatly appreciated.

Toy_Reid
  • 69
  • 1
  • 6
  • An error like that often means you did some undefined behavior at some point earlier in the program, which wasn't detected until now. A tool like valgrind can help identify such bugs. – aschepler Apr 13 '17 at 22:49
  • I am seeing a lot of deleting, but no new-ing... then again, I guess it may have been pointless to paste that part... – Evan Carslake Apr 13 '17 at 22:49
  • @EvanCarslake So that's something that I saw when I was trying to look up similar problems. I do all my new-ing in main and then call this function, which is actually a member of the Graph class (I removed that for the sake of simplicity in my question). I'm planning on trying to transfer all the news to a Graph class constructor but I figured I'd just try it like this first. Do they news/deletes both have to be contained in the same class? I was under the impression that you can delete the memory from any pointer that points to it. – Toy_Reid Apr 13 '17 at 22:53
  • @Toy_Reid yeah, anything that you "newed" you can delete it by the pointer to it, anywhere, once. – Evan Carslake Apr 13 '17 at 22:54
  • You might be deleting the same pointer twice. Maybe you should use a smart pointer instead of regular pointers? – Barmar Apr 13 '17 at 23:06
  • @Barmar The professor is asking us to compile for C++98, unfortunately, so smart pointers are a no go. I have no clue how to use them regardless. – Toy_Reid Apr 13 '17 at 23:08
  • Add reference counters to your nodes. – Barmar Apr 13 '17 at 23:12
  • @Barmar Isn't that a C++11 and beyond thing? – Toy_Reid Apr 13 '17 at 23:14
  • 1
    @Toy_Reid he's suggesting you make your own poor-man's smart pointer: When you are considering `delete`ing a Node, decrement and check the counter. If zero, proceed with `delete`. Of course that means you have to increment the counter whenever you assign the `Node`. This is a perfect opportunity to [practice RAII](http://stackoverflow.com/questions/2321511/what-is-meant-by-resource-acquisition-is-initialization-raii) and [the Rule of Three](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) and wrap the `Node` pointer in a counter object and pass around the counter object. – user4581301 Apr 13 '17 at 23:49
  • Hi folks (@Toy_Reid and @user4581301)! I hope I have not passed over the question too fast and may have missed the point. But, maybe the path of minimal effort (considering C++98) may be setting the variables to NULL (= 0) after deletion, and checking if variables are not NULL (!= 0) before deleting them. For example: #define NULL 0 if(nodes[i]->adj[j]) { delete nodes[i]->adj[j]; nodes[i]->adj[j] = NULL ; } – diogoslima Apr 14 '17 at 00:15
  • @diogoslima That doesn't help because there can be multiple pointers to the same node. Setting one pointer to `NULL` doesn't affect the other pointers. – Barmar Apr 14 '17 at 00:34
  • @diogoslima You can safely `delete` NULL. It checks for you. Your approach works to prevent some double deletes, but still leaves a minefield of other nodes who may try to traverse to that deleted node because they have not been unhooked and still expect it to be there. You do not want to `delete` the node until no one is linked to it, with deference to the risk of leaving a cycle of nodes cut of from the rest of the graph. – user4581301 Apr 14 '17 at 00:35
  • Thank you guys for all the feedback! Won't let me mention each of you for some reason (I'm fairly new to StackOverflow). The solution actually ended up being pretty simple: I wasn't resizing my adjacency list after deleting edges from it, so when I went to go add new edges to the vector for the next graph, the empty pointers would still be left sitting there. Removing those from my adjacency vector fixed the problem :) – Toy_Reid Apr 14 '17 at 02:26

1 Answers1

0

The solution actually ended up being pretty simple: I wasn't resizing my adjacency list after deleting edges from it, so when I went to go add new edges to the vector for the next graph, the empty pointers would still be left sitting there (which I tried accessing in other parts of my program). Removing those from my adjacency vector fixed the problem.

Toy_Reid
  • 69
  • 1
  • 6